Quelle est la différence entre un hachage et un dictionnaire?

46

Et quelle est la différence entre Hashet Dictionary?

Venant d'un contexte de script, je pense qu'ils sont similaires, mais je voulais découvrir les différences exactes. Googler ne m'a pas beaucoup aidé.

data-structures hashing dictionary difference hashtable Sairam
la source

Réponses:

92

Hashest une structure de données extrêmement mal nommée dans laquelle le programmeur a confondu l’interface avec l’implémentation ( et était trop paresseuse pour écrire le nom complet, c’est-à-dire qu’elle a HashTableplutôt recours à une abréviation Hash).

Dictionaryest le nom “correct” de l'interface (= the ADT ), c'est-à-dire un conteneur associatif qui associe des clés (généralement uniques) à des valeurs (pas nécessairement uniques).

Une table de hachage est une implémentation possible d'un tel dictionnaire qui fournit d'assez bonnes caractéristiques d'accès (en termes d'exécution) et est donc souvent l'implémentation par défaut.

Une telle implémentation a deux propriétés importantes:

  1. les clés doivent être hashable et l' égalité comparable .
  2. les entrées apparaissent sans ordre particulier dans le dictionnaire.

(Pour qu'une clé soit hashable, cela signifie que nous pouvons calculer une valeur numérique à partir d'une clé qui est ensuite utilisée comme index dans un tableau.)

Il existe d'autres implémentations de la structure de données du dictionnaire qui imposent un ordre aux clés - on parle souvent de dictionnaire trié (et généralement implémenté sous la forme d'un arbre de recherche, bien qu'il existe d'autres implémentations efficaces).

Pour résumer: un dictionnaire est un ADT qui mappe les clés aux valeurs. Il existe plusieurs implémentations possibles de cet ADT, dont la table de hachage . Hashest un abus de langage, mais dans le contexte, il est équivalent à un dictionnaire implémenté en termes de table de hachage.

Konrad Rudolph
la source
4
Pour donner un exemple en C ++, les modèles de conteneur associatif standard ne peuvent pas être implémentés sous forme de hachage, bien que le prochain standard comporte effectivement des tables de hachage. Ils sont appelés unordered_mapà montrer ce qu'ils font plutôt que ce qu'ils sont.
David Thornley
6
“Correct” selon quelle autorité? Dans certaines langues, telles que Ruby et Perl, le nom officiel de ces structures («correct») est «hash».
Nohat
11
@nohat: Notez mon utilisation des guillemets. De plus, je l' ai expliqué pourquoi le nom est mal choisi, non? Donc, si vous avez besoin d'une autorité, je dirai que cela relève de l'autorité de la police informatique théorique.
Konrad Rudolph
9
Il est intéressant de noter qu'en Ruby 1.9, il est en fait impossible d'implémenter la Hashclasse avec une table de hachage, puisque Ruby 1.9 Hashpréserve l'ordre d'insertion, contrairement à la table de hachage. Ainsi, dans Ruby 1.9, le nom Hashne reflète même plus l'implémentation.
Jörg W Mittag
7
@hippietrail Vous vous trompez - d'abord, ce sont des descriptions objectives. Après tout, je qualifie pourquoi la dénomination est pauvre et mal nommée (voir ci-dessous). “Too parzy” est une licence artistique de ma part, mais il reste que la raison pour raccourcir le nom est intrinsèque, c'est-à-dire qu'il n'y a aucune raison d'utiliser un nom abrégé ici autre que de raccourcir le nom. Et vous vous trompez à propos de «dictionnaire»: c'est simplement le nom officiel de la structure de données. Votre définition de «dictionnaire» est fausse dans le contexte de la science informatique et son nom précède Python de plusieurs décennies.
Konrad Rudolph
8

"Dictionnaire" est le nom du concept. Une table de hachage est une implémentation possible.

dan_waterworth
la source
1
Hash est aussi un ADT. HashTable est une implémentation d'un hachage
Sairam Le
3
@Sairam Je pense qu'il est beaucoup plus courant de parler de «hash» plutôt que d'une table de hachage.
jk.
@jk En réalité, le "hachage" est le résultat de l'application d'une "fonction / algorithme de hachage" à une entrée. Une "table de hachage" ou une "carte de hachage" omehoe concerne un objet pouvant être traité avec un objet quelconque (objet sous une forme générique non limitée à la POO)
johannes
Certaines langues utilisent «hachage» pour faire référence à une structure de type dictionnaire plutôt qu'à une simple opération de hachage. Ruby, par exemple .
Sean Burton
7

Un dictionnaire est le terme collectif donné pour toute implémentation de structure de données utilisée pour les recherches / insertions rapides. Ceci peut être réalisé / mis en œuvre en utilisant diverses structures de données telles qu'une table de hachage, des listes de sauts, une arborescence de bases de données, etc. Une table de hachage est une structure de données spécifique utile à de nombreuses fins, notamment la mise en œuvre d'un dictionnaire.

aufather
la source
Hash est aussi un ADT. Existe-t-il une différence spécifique entre Hash et Dictionary ADT?
Sairam
2
@Sairam: Non, un hachage est la sortie d'un certain type d'algorithme (fonction de hachage).
5

Un dictionnaire utilise une clé pour référencer la valeur directement à l'intérieur d'un tableau associatif .

c'est à dire (KEY => VALUE)

Un hachage est plus souvent décrit comme une table de hachage qui utilise une fonction de hachage pour calculer la position en mémoire (ou plus facilement un tableau) où la valeur sera. Le hachage prendra la clé en entrée et donnera une valeur en sortie. Puis connectez cette valeur à la mémoire ou à l’index du tableau.

c'est à dire KEY => HASH FUNCTION => VALUE

Je suppose que l'un est direct tandis que l'autre ne l'est pas. Les fonctions de hachage peuvent ne pas être parfait non plus et peuvent parfois fournir un index référençant la valeur fausse. Mais cela peut être corrigé.

Meilleur endroit à regarder: Wikipedia ( tableau associatif et table de hachage )

Ross
la source