Worldlex Wiki 
Cette opération ajoute une paire à la collection, en associant la clé à sa nouvelle valeur. Toute association existante est écrasée. Les arguments de cette opération sont la clé et la valeur.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
Arbres binaires de recherche auto-équilibrés
Une autre approche courante consiste à implémenter un tableau associatif avec un arbre de recherche binaire auto-équilibré , tel qu'un arbre AVL ou un arbre rouge-noir .
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
Dictionnaire ordonné
La définition de base d'un dictionnaire n'impose pas d'ordre. Pour garantir un ordre d'énumération fixe, on utilise souvent des versions ordonnées du tableau associatif. Il existe deux sens à l'expression « dictionnaire ordonné » :
- L'ordre d'énumération est toujours déterministe pour un ensemble de clés donné par tri. C'est le cas pour les implémentations arborescentes, dont un représentant est le
L'ordre d'énumération est indépendant des clés et repose plutôt sur l'ordre d'insertion. C'est le cas du « dictionnaire ordonné » dans .NET Framework , ainsi queLinkedHashMapdans 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 linguistique
De nombreux programmes utilisant des tableaux associatifs doivent stocker ces données sous une forme plus permanente, par exemple dans un fichier informatique . Une solution courante à ce problème est un concept généralisé appelé archivage ou sérialisation , qui produit une représentation textuelle ou binaire des objets originaux pouvant être écrite directement dans un fichier. Cette fonctionnalité est généralement implémentée dans le modèle objet sous-jacent, comme .NET ou Cocoa, qui inclut des fonctions standard convertissant les données internes en texte. Le programme peut créer une représentation textuelle complète de n'importe quel groupe d'objets en appelant ces méthodes, qui sont presque toujours déjà implémentées dans la classe de base des tableaux associatifs.
Pour 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.