Quelle est la différence entre une carte et un dictionnaire?

Je sais qu'une carte est une structure de données qui mappe les clés aux valeurs. Un dictionnaire n'est-il pas pareil? Quelle est la différence entre une carte et un dictionnaire ¹ ?

_{1. Je ne demande pas comment ils sont définis en langage X ou Y (ce qui semble être ce que généralement les gens demandent ici sur SO), je veux savoir quelle est leur différence en théorie.}

Deux termes pour la même chose:

• "Map" est utilisé par Java, C ++
• "Dictionary" est utilisé par .Net, Python
• "Tableau associatif" est utilisé par PHP

"Carte" est le terme mathématique correct, mais il est évité car il a une signification distincte dans la programmation fonctionnelle .

Certaines langues utilisent encore d'autres termes ("Object" en Javascript, "Hash" en Ruby, "Table" en Lua) , mais ils ont tous des significations distinctes en programmation aussi, donc je les éviterais.

Voir ici pour plus d'informations.

L'un est un terme plus ancien pour l'autre. Généralement, le terme "dictionnaire" était utilisé avant que le terme mathématique "carte" ne prenne racine. De plus, les dictionnaires ont tendance à avoir un type de chaîne clé, mais ce n'est pas vrai à 100% partout.

Mes 2 cents.

Dictionary est une classe abstraite en Java alors que Map est une interface. Étant donné que Java ne prend pas en charge plusieurs héritages, si une classe étend Dictionary, elle ne peut pas étendre une autre classe.

Par conséquent, l'interface Carte a été introduite.

La classe de dictionnaire est obsolète et l'utilisation de Map est préférable.

La réponse à cette question est compliquée par le fait que les programmeurs ont vu les termes donnés des significations plus spécifiques dans des langages ou des systèmes particuliers qu'ils ont utilisés, mais la question demande une comparaison indépendante du langage "en théorie", ce que je veux dire en termes de science informatique .

La terminologie expliquée

Le Oxford University Dictionary of Computer Science répertorie:

dictionnaire toute structure de données représentant un ensemble d'éléments pouvant prendre en charge l'insertion et la suppression d'éléments ainsi que tester l'appartenance

• Par exemple, nous avons un ensemble d'éléments {A, B, C, D ...} que nous avons pu insérer et commencer à supprimer, et nous pouvons interroger "est-ce que C est présent?" .

La notion de carte de la science informatique est basée sur la cartographie des termes linguistiques mathématiques , que le dictionnaire Oxford définit comme:

mapping Opération qui associe chaque élément d'un ensemble donné (le domaine) à un ou plusieurs éléments d'un deuxième ensemble (la plage).

• En tant que telle, une structure de données de carte permet de passer des éléments d'un ensemble donné - connus sous le nom de " clés " de la carte à un ou plusieurs éléments du deuxième ensemble - connus sous le nom de " valeur (s) " associée (s) .
• L' aspect "... ou plusieurs éléments du deuxième ensemble" peut être pris en charge par une implémentation de deux manières distinctes:
  • De nombreuses implémentations de mappage imposent l'unicité des clés et permettent à chaque clé d'être associée à une seule valeur, mais cette valeur peut être une structure de données contenant elle-même de nombreuses valeurs d'un type de données plus simple, par exemple {{1, {"one" , "ichi"}, {2, {"two", "ni"}}} illustre des valeurs constituées de paires de chaînes.
  • D'autres implémentations de cartes permettent de dupliquer des clés chaque mappant à des valeurs identiques ou différentes - ce qui satisfait fonctionnellement le cas "associe ... chaque élément [clé] ... à ... plus [qu'un] élément [de valeur]". Par exemple, {{1, "one"}, {1, "ichi"}, {2, "two"}, {2, "ni"}}.

Dictionnaire et carte contrastés

Ainsi, en utilisant la terminologie stricte de Comp Sci ci-dessus, un dictionnaire n'est qu'une carte si l'interface prend en charge des opérations supplémentaires non requises pour chaque dictionnaire:

• la capacité de stocker des éléments avec des composants clés et de valeur distincts

• la possibilité de récupérer la (les) valeur (s) avec uniquement la clé

Une torsion triviale:

• une interface de carte peut ne pas prendre directement en charge un test pour savoir si une paire {clé, valeur} se trouve dans le conteneur, ce qui est pédantiquement une exigence d'un dictionnaire où les éléments se trouvent être des paires {clé, valeur}; une carte peut même ne pas avoir de fonction pour tester une clé, mais au pire, vous pouvez voir si une tentative de récupération de valeur par clé réussit ou échoue, alors si vous vous en souciez, vous pouvez vérifier si la clé a récupéré une valeur attendue.

Communiquez sans ambiguïté à votre public

⚠ Malgré tout ce qui précède, si vous utilisez un dictionnaire dans le sens strict de la science informatique expliqué ci-dessus, ne vous attendez pas à ce que votre public vous suive au début, ou ne soit pas impressionné lorsque vous partagez et défendez la terminologie. Les autres réponses à cette question (et leurs votes positifs) montrent à quel point il est probable que "dictionnaire" sera synonyme de "carte" dans l'expérience de la plupart des programmeurs. Essayez de choisir une terminologie qui sera comprise plus largement et sans ambiguïté: par exemple

• conteneur associatif : tout conteneur stockant des paires clé / valeur avec récupération de valeur et effacement par clé
• carte de hachage : une implémentation de table de hachage d'un conteneur associé
• ensemble de hachage application de clés uniques : une implémentation de table de hachage d'un dictionnaire stockant un élément / des valeurs sans les traiter comme contenant des composants de clé / valeur distincts, dans lequel des doublons des éléments ne peuvent pas être insérés
• équilibrer la carte d'arbre binaire prenant en charge la clé en double : ...

Cross-referencing Comp Sci terminology with specific implémentations

Bibliothèque standard C ++

• cartes: map, multimap, unordered_map,unordered_multimap
• d' autres dictionnaires: set, multiset, unordered_set,unordered_multiset
• Note: avec itérateurs ou std::findvous pouvez effacer un élément et un test d'adhésion à array, vector, list, dequeetc, mais les interfaces conteneurs ne supportent pas directement parce que la recherche d' un élément est spectaculairement inefficace à O (N), dans certains cas , insertion / effacement est inefficace, et la prise en charge de ces opérations sape l'API délibérément limitée que le conteneur implique - par exemple, les deques ne devraient prendre en charge l'effacement / pop à l'avant et à l'arrière et non en termes de clé. Devoir faire plus de travail dans le code pour orchestrer la recherche encourage doucement le programmeur à passer à une structure de données de conteneur avec une recherche plus efficace.

... peut ajouter d'autres langues ultérieurement / n'hésitez pas à modifier en ...

En règle générale, je suppose qu'une carte est soutenue par une table de hachage; il évoque un magasin non ordonné. Les dictionnaires désignent un magasin commandé.

Il existe un dictionnaire arborescent appelé Trie .

En Lisp, cela pourrait ressembler à ceci:

(a (n (d t)) n d )

Qui résume les mots:

• une
• et
• fourmi
• une
• un d

La traversée du haut vers la feuille donne un mot.

Pas vraiment la même chose. Les cartes sont un sous-ensemble de dictionnaire. Le dictionnaire est défini ici comme ayant les fonctions d'insertion, de suppression et de recherche. Carte utilisée par Java (selon cette ) est un dictionnaire avec l'exigence que les clés mappées aux valeurs soient strictement mappées comme une fonction un-à-un. Un dictionnaire peut avoir plusieurs mappages de clés pour une valeur ou un mappage de clés pour plusieurs valeurs (comme l'enchaînement dans une table de hastht), par exemple les recherches de hashtag Twitter.

À titre d'exemple plus «réel», la recherche d'un mot dans un dictionnaire peut nous donner un certain nombre de définitions pour le même mot, et lorsque nous trouvons une entrée qui nous pointe vers une autre entrée (voir un autre mot), un certain nombre de mots pour la même liste de définitions. Dans le monde réel, les cartes sont beaucoup plus larges, nous permettant d'avoir des emplacements pour les noms ou les noms pour les coordonnées, mais nous pouvons également trouver un voisin le plus proche ou d'autres attributs (populations, etc.), donc à mon humble avis, il pourrait y avoir un argument pour une plus grande expansion de le type de carte peut éventuellement avoir des implémentations basées sur un graphique, mais il serait préférable de toujours supposer uniquement la paire clé-valeur, d'autant plus que le plus proche voisin et d'autres attributs de la valeur pourraient tous être simplement des membres de données de la valeur.

Les cartes java, malgré l'exigence d'un à un, peuvent implémenter quelque chose de plus comme un dictionnaire généralisé si la valeur est généralisée en tant que collection elle-même, ou si les valeurs sont simplement des références à des collections stockées ailleurs.

N'oubliez pas que les responsables Java ne sont pas les responsables des définitions ADT et que les décisions Java sont spécifiquement pour Java.

Autres termes assez courants pour ce concept: tableau associatif et hachage.

Oui, ce sont les mêmes, vous pouvez ajouter "Associative Array" au mix.

l'utilisation Hashtable ou un Hashofter fait référence à l'implémentation.

donc à un niveau purement théorique.

Un dictionnaire est une valeur qui peut être utilisée pour localiser une valeur liée. Une carte est une valeur qui fournit des instructions sur la façon de localiser une autre valeur

toutes les collections qui permettent un accès non linéaire (c'est-à-dire uniquement obtenir le premier ou obtenir le dernier) sont une carte, car même un simple tableau a un index qui correspond à la valeur correcte. Ainsi, alors qu'un dictionnaire est un type de carte, les cartes offrent un éventail beaucoup plus large de fonctions possibles.

En pratique, c'est généralement la fonction de mappage qui définit le nom, donc un HashMap est une structure de données mappée qui utilise un algorithme de hachage pour lier la clé à la valeur, alors qu'un dictionnaire ne spécifie pas comment les clés sont liées à une valeur pourrait donc être stocké via une liste chaînée, un arbre ou tout autre algorithme. du point de vue de l'utilisation, vous ne vous souciez généralement pas de ce que l'algorithme fonctionne uniquement, vous utilisez donc un dictionnaire générique et ne passez à l'une des autres structures que lorsque vous devez appliquer le type d'algorithme

Ce sont deux termes différents pour le même concept.
Hashtableet HashMapse réfèrent également au même concept.

La principale différence est qu’une carte requiert que toutes les entrées (valeur et paire de clés) aient une clé unique. Si des collisions se produisent, c'est-à-dire lorsqu'une nouvelle entrée a la même clé qu'une entrée déjà dans la collection, alors la gestion des collisions est requise.

Habituellement, nous gérons les collisions à l'aide de chaînage séparé . Ou palpage linéaire .

Un dictionnaire permet de lier plusieurs entrées à la même clé.

Lorsqu'une carte a implémenté un chaînage séparé, elle a tendance à ressembler à un dictionnaire.