Worldlex Wiki Le problème du dictionnaire est le problème classique de la conception de structures de données efficaces implémentant des tableaux associatifs. Les deux principales solutions au problème du dictionnaire sont les tables de hachage et les arbres de recherche . Il est parfois également possible de résoudre le problème en utilisant des tableaux à accès direct , des arbres binaires de recherche ou d'autres structures plus spécialisées.
De nombreux langages de programmation intègrent les tableaux associatifs comme types de données primitifs , tandis que d'autres proposent des bibliothèques logicielles les prenant en charge. La mémoire adressable par contenu (CAM) constitue une forme de support matériel direct pour les tableaux associatifs.
Les tableaux associatifs ont de nombreuses applications, notamment dans des modèles de programmation fondamentaux comme la mémoïsation et le modèle décorateur . Leur nom ne provient pas de la propriété associative mathématique, mais plutôt de l'association de valeurs à des clés. Il ne faut pas les confondre avec les processeurs associatifs .
une clé et une valeur est souvent appelée « mappage » ; le même mot peut également être utilisé pour désigner le processus de création d'une nouvelle association.Les opérations généralement définies pour un tableau associatif sont :
- Insérer ou mettre
- Ajoute une nouvelle paire à la collection, en associant la clé à sa nouvelle valeur. Toute association existante sera écrasée. Les arguments de cette opération sont la clé et la valeur.
- Supprimer ou effacer
- Supprime une paire de la collection en dissociant une clé donnée de sa valeur. L'argument de cette opération est la clé.
- Rechercher, trouver ou obtenir
- Cette fonction recherche la valeur (le cas échéant) associée à une clé donnée. Elle prend la clé comme argument et renvoie la valeur correspondante. Si aucune valeur n'est trouvée, certaines fonctions lèvent une exception , tandis que d'autres renvoient une valeur par défaut (comme zéro, null ou une valeur spécifique passée au constructeur).
Les tableaux associatifs peuvent également inclure d'autres opérations, comme la détermination du nombre d'associations ou la construction d'un itérateur pour parcourir toutes les associations. Pour ces opérations, l'ordre de retour des associations est généralement défini par l'implémentation.
Une multimap généralise un tableau associatif en permettant d'associer plusieurs valeurs à une seule clé. Une map bidirectionnelle est un type de données abstrait apparenté dans lequel les mappages fonctionnent dans les deux sens : chaque valeur doit être associée à une clé unique, et une seconde opération de recherche prend une valeur comme argument et recherche la clé associée à cette valeur.
Propriétés
Les opérations du tableau associatif doivent satisfaire diverses propriétés :
lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)lookup(k, new()) = fail, oùfailest une exception ou une valeur par défautremove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))remove(k, new()) = new()
où ket jsont des clés, vest une valeur, Dest un tableau associatif, et new()crée un nouveau tableau associatif vide.
Exemple
Supposons que l'ensemble des prêts effectués par une bibliothèque soit représenté par une structure de données. Chaque livre peut être emprunté par un seul usager à la fois. Cependant, un même usager peut emprunter plusieurs livres. Par conséquent, les informations relatives aux livres empruntés et aux usagers peuvent être représentées par un tableau associatif, où les livres sont les clés et les usagers les valeurs. En utilisant la notation de Python ou de JSON , la structure de données serait la suivante :
Une recherche sur la clé « Great Expectations » renverrait « John ». Si John rend son livre, cela entraînerait une suppression, et si Pat emprunte un livre, cela entraînerait une insertion, aboutissant à un état différent.
Mise en œuvre
Pour les dictionnaires comportant très peu d'associations, il peut être judicieux d'implémenter le dictionnaire à l'aide d'une liste d'associations , c'est-à-dire une liste chaînée d'associations. Avec cette implémentation, le temps d'exécution des opérations de base sur le dictionnaire est linéaire par rapport au nombre total d'associations. De plus, elle est facile à implémenter et les facteurs constants de son temps d'exécution sont faibles.
Une autre technique d'implémentation très simple, utilisable lorsque les clés sont restreintes à une plage étroite, consiste à accéder directement à un tableau : la valeur d'une clé k donnée est stockée dans la cellule A [ k ] du tableau, ou, s'il n'existe aucune correspondance pour k , la cellule stocke une valeur sentinelle spéciale indiquant l'absence de correspondance. Cette technique est simple et rapide, chaque opération sur le dictionnaire s'effectuant en temps constant. Cependant, l'espace mémoire requis par cette structure correspond à la taille de l'espace de clés entier, ce qui la rend impraticable sauf si l'espace de clés est petit.
Les deux principales approches pour implémenter des dictionnaires sont une table de hachage ou un arbre de recherche .
Implémentations de tables de hachage
L'implémentation la plus courante d'un tableau associatif est la table de hachage : un tableau associé à une fonction de hachage qui répartit chaque clé dans un « compartiment » distinct. Le principe de base d'une table de hachage est que l'accès à un élément du tableau par son index est une opération simple et en temps constant. Par conséquent, le coût moyen d'une opération sur une table de hachage se limite au calcul du hachage de la clé et à l'accès au compartiment correspondant dans le tableau. De ce fait, les tables de hachage s'exécutent généralement en temps constant (O(1)) et sont généralement plus performantes que les autres implémentations.
Les tables de hachage doivent pouvoir gérer les collisions : l’association, par la fonction de hachage, de deux clés différentes au même emplacement du tableau. Les deux approches les plus courantes pour résoudre ce problème sont le chaînage séparé et l’adressage ouvert . Dans le chaînage séparé, le tableau ne stocke pas la valeur elle-même, mais un pointeur vers un autre conteneur, généralement une liste d’associations , qui stocke toutes les valeurs correspondant au hachage. En revanche, dans l’adressage ouvert, si une collision de hachage est détectée, la table recherche un emplacement libre dans le tableau pour y stocker la valeur de manière déterministe, généralement en examinant l’élément immédiatement suivant dans le tableau.
L'adressage ouvert présente un taux d' échecs de cache inférieur à celui du chaînage séparé lorsque la table est presque vide. Cependant, à mesure que la table se remplit, les performances de l'adressage ouvert se dégradent de façon exponentielle. De plus, le chaînage séparé utilise généralement moins de mémoire, sauf si les entrées sont très petites (moins de quatre fois la taille d'un pointeur).
Implémentations arborescentes
Comparées aux tables de hachage, ces structures présentent des avantages et des inconvénients. Les performances dans le pire des cas des arbres binaires de recherche auto-équilibrés sont nettement meilleures que celles d'une table de hachage, avec une complexité temporelle de O(log n ) en notation grand O. Ceci contraste avec les tables de hachage, dont les performances dans le pire des cas impliquent que tous les éléments partagent un même compartiment, ce qui entraîne une complexité temporelle de O( n ). De plus, comme tous les arbres binaires de recherche, les arbres binaires de recherche auto-équilibrés conservent leurs éléments ordonnés. Ainsi, le parcours de leurs éléments suit un parcours du plus petit au plus grand, tandis que le parcours d'une table de hachage peut aboutir à un ordre apparemment aléatoire des éléments. Du fait de cet ordre, les structures arborescentes peuvent également satisfaire des requêtes par intervalle (trouver toutes les valeurs comprises entre deux bornes), alors qu'une table de hachage ne peut trouver que des valeurs exactes. Cependant, les tables de hachage ont une complexité temporelle moyenne bien meilleure que celle des arbres binaires de recherche auto-équilibrés (O(1)), et leurs performances dans le pire des cas sont très improbables lorsqu'une fonction de hachage performante est utilisée.
Un arbre binaire de recherche auto-équilibré peut être utilisé pour implémenter les compartiments d'une table de hachage utilisant le chaînage séparé. Ceci permet une recherche constante en moyenne, tout en garantissant une performance dans le pire des cas de O(log n ). Cependant, cela introduit une complexité supplémentaire dans l'implémentation et peut entraîner des performances encore plus faibles pour les petites tables de hachage, où le temps passé à insérer des données dans l'arbre et à l'équilibrer est supérieur au temps nécessaire pour effectuer une recherche linéaire sur tous les éléments d'une liste chaînée ou d'une structure de données similaire.
Autres arbres
Les tableaux associatifs peuvent également être stockés dans des arbres binaires de recherche non équilibrés ou dans des structures de données spécialisées pour un type de clé particulier, telles que les arbres radix , les tries , les tableaux de Judy ou les arbres de van Emde-Boas . Cependant, les performances relatives de ces implémentations varient. Par exemple, les arbres de Judy se sont avérés moins performants que les tables de hachage, tandis que des tables de hachage soigneusement sélectionnées sont généralement plus performantes que les arbres radix adaptatifs, avec des restrictions potentiellement plus importantes quant aux types de données qu'elles peuvent gérer. L'avantage de ces structures alternatives réside dans leur capacité à gérer des opérations supplémentaires sur les tableaux associatifs, comme la recherche de l'association dont la clé est la plus proche d'une clé recherchée lorsque cette dernière est absente de l'ensemble des associations.
Comparaison
| Structure de données sous-jacente | Recherche ou suppression | Insertion | Ordonné | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| moyenne | pire des cas | moyenne | pire des cas | |||||||||||||||||
| Table de hachage | O(1) | Sur ) | O(1) | Sur ) | Arbre de recherche binaire auto-équilibré | O(log n ) | O(log n ) | O(log n ) | O(log n ) | arbre binaire de recherche déséquilibré | O(log n ) | Sur ) | O(log n ) | Sur ) | paires clé-valeur (par exemple, liste d'associations ) | Sur ) | Sur ) | O(1) | O(1) | .NET Framework , ainsi que LinkedHashMapdans Java et Python . Cette dernière méthode est la plus courante. De tels dictionnaires ordonnés peuvent être implémentés à l'aide d'une liste d'associations , en superposant une liste doublement chaînée à un dictionnaire normal, ou en déplaçant les données réelles hors du tableau creux (non ordonné) et dans un tableau dense ordonné par insertion. Soutien linguistiqueEn Smalltalk , Objective-C , .NET , Python , REALbasic , Swift , VBA et Delphi on les appelle dictionnaires ; en Perl et Ruby, tables de hachage ; en C++ , C# , Java , Go , Clojure , Scala , OCaml et Haskell , maps (voir map (C++) , unordered_map (C++) et stockage permanentPour les programmes manipulant de très grands ensembles de données, ce type de stockage individuel de fichiers est inadapté et un système de gestion de base de données (SGBD) est nécessaire. Certains SGBD stockent nativement des tableaux associatifs en sérialisant les données, puis en stockant ces données sérialisées ainsi que la clé. Les tableaux individuels peuvent ensuite être chargés ou enregistrés dans la base de données à l'aide de leur clé. Ces systèmes de stockage clé-valeur sont utilisés depuis de nombreuses années et ont une histoire aussi longue que celle des bases de données relationnelles (SGBDR) plus courantes. Cependant, un manque de standardisation, entre autres raisons, a limité leur utilisation à des cas spécifiques. Les SGBDR étaient généralement privilégiées pour ces cas, bien que l'enregistrement d'objets dans une SGBDR puisse s'avérer complexe, un problème connu sous le nom d'incompatibilité d'impédance objet-relationnelle . Après 2010 environ, le besoin de bases de données hautes performances adaptées au cloud computing et reflétant plus fidèlement la structure interne des programmes les utilisant a engendré un regain d'intérêt pour les systèmes de stockage clé-valeur. Ces systèmes permettent de stocker et de récupérer des tableaux associatifs de manière native, ce qui améliore considérablement les performances des flux de travail web courants. |