Comment fonctionne le processus de hachage dans le Dictionary<TKey, TValue> ?

Question

Comment fonctionne le processus de hachage dans le Dictionnaire ? J'ai lu que l'utilisation du dictionnaire permettait une recherche plus rapide. Mais je n'ai pas compris comment ? Comment se déroulent le hachage et la mise en correspondance avec un index ? Je n'ai pas trouvé de bonne référence.

EDIT : Comment l'emplacement réel de la mémoire où l'objet est stocké est-il obtenu à partir du résultat de la fonction de hachage ?

Answer 1

Une table de hachage ou un dictionnaire est une structure de données qui stocke des paires clé-valeur. L'avantage de la table de hachage est qu'à partir d'une clé, la recherche de la valeur correspondante est assez rapide. Pour simplifier, le temps nécessaire pour trouver une paire clé-valeur dans la table de hachage ne dépend pas de la taille de la table. Comparez cela au stockage des paires clé-valeur dans une liste ou un tableau. Pour trouver une paire clé-valeur, vous devez parcourir la liste depuis le début jusqu'à ce qu'une clé correspondante soit trouvée. Plus la liste est longue, plus il faut de temps pour trouver la paire clé-valeur. En utilisant la notation big-O, on peut dire que la recherche d'une clé dans une table de hachage est d'ordre O(1) alors que la recherche d'une clé dans une liste en utilisant la recherche linéaire est d'ordre O(N) (simplifié).

Pour insérer une paire clé-valeur dans la table de hachage, vous devez d'abord calculer le code de hachage de la clé. En .NET, tous les objets ont une méthode nommée GetHashCode qui renvoie un code de hachage (entier de 32 bits) pour cet objet particulier. Il est important que des objets identiques renvoient le même code de hachage, mais il est également très utile que des objets différents renvoient des codes de hachage différents. Attention à l'idée fausse selon laquelle des objets différents ne peuvent pas renvoyer le même code de hachage. collision (voir ci-dessous).

Prenons l'exemple des codes de hachage de deux chaînes de caractères :

"Boo" 0x598FD95A
"Foo" 0x598FD8DE

Bien que les chaînes soient très similaires, elles ont des codes de hachage différents.

Je simplifie un peu les choses ici pour me concentrer sur les aspects importants d'une table de hachage. Dictionary<TKey, TValue> stocke les paires clé-valeur dans un tableau. Pour localiser l'index de ce tableau où la paire clé-valeur sera stockée, vous devez calculer le code de hachage de la clé modulo la taille du tableau. Supposons que la taille du tableau soit de 5 :

Index("Boo") = 0x598FD95A % 5 = 4
Index("Foo") = 0x598FD8DE % 5 = 0

Il en résulte une table de hachage interne :

+---+---------+
| 0 | "Foo"   |
+---+---------+
| 1 | (empty) |
+---+---------+
| 2 | (empty) |
+---+---------+
| 3 | (empty) |
+---+---------+
| 4 | "Boo"   |
+---+---------+

La recherche d'une entrée dans la table de hachage est très rapide. Il suffit de calculer le code de hachage de la clé modulo la taille du tableau interne et de récupérer la chaîne à cet index.

Considérons maintenant la clé "Zoo" :

Index("Zoo") = 0x598FDC62 % 5 = 0

Elle a le même index que la clé "Foo". Il en résulte ce que l'on appelle un collision . Une implémentation correcte d'une table de hachage devra gérer les collisions et il existe des différentes stratégies pour y parvenir . En outre, au fur et à mesure que le tableau interne se remplit, il y aura de moins en moins d'éléments vides dans le tableau, ce qui entraînera un nombre croissant de collisions. Les facteur de charge est le rapport entre les éléments utilisés et le nombre total d'éléments dans le tableau interne. Dans l'exemple ci-dessus, le facteur de charge est de 2/5 = 0,4. La plupart des implémentations de tables de hachage augmentent la taille du tableau interne lorsque le facteur de charge dépasse un certain seuil.

Si vous souhaitez en savoir plus sur certains de ces concepts, vous devrez étudier certaines des ressources plus complètes mentionnées dans d'autres réponses.

Answer 2

Le processus de hachage dans un dictionnaire utilise une technique appelée chaînage. Avec le chaînage, une structure de données secondaire est utilisée pour contenir les collisions. Plus précisément, chaque emplacement dans le dictionnaire possède un tableau d'éléments qui correspondent à un seau. En cas de collision, l'élément qui entre en collision est ajouté à la liste du seau.

Véase cette sur MSDN pour plus de détails.

Answer 3

En utilisant un concept informatique appelé Carte de hachage . Cette méthode est plus rapide que la recherche dans une liste. En effet, la recherche n'a pas besoin d'itérer dans une liste jusqu'à ce qu'elle trouve une correspondance. Au lieu de cela, la clé est " haché "et utilisé comme index dans une liste. Cette fonction de hachage est presque toujours plus rapide que la recherche dans la liste (itération avec comparaisons multiples).

Answer 4

Généralement, en prenant la valeur de hachage % taille du tableau, ce qui peut produire une collision.

Answer 5

Le dictionnaire utilise des clés hachées pour la recherche, comme j'ai essayé de l'expliquer dans le document ma réponse à votre autre question . Ainsi, si vous avez un type d'objet personnalisé comme clé, tout dépend de GetHashCode() de votre objet personnalisé.