Comment un dictionnaire fait une recherche rapide

Question

Je regarde la source Item[TKey] de Dictionary<TKey,TValue> essayant de comprendre le mécanisme de stockage/récupération dans un dictionnaire, et pourquoi il est plus rapide que de vérifier chaque entrée une par une.

Où je suis confus est dans l'utilisateur des nombres premiers dans le champ buckets et l'interaction avec Entry<TKey,TValue>.next. Est-ce que quelqu'un peut m'expliquer la logique, ou pointer vers une référence où je peux le comprendre.

Merci.

Answer 1

Voir Hash Tables et peut-être this article about using prime numbers in hash table implementations.

Answer 2

Regardez dans hashcodes, ils permettent le dictionnaire de 'seau' clés:

http://msdn.microsoft.com/en-us/library/4yh14awz%28VS.80%29.aspx

Colin E.

Answer 3

Regardez cet article Wikipedia: Hashtable

Un dictionnaire est juste un type fort d implémentation d'une hashtable. Il a un certain nombre de "seaux" où il met les éléments avec leurs clés. Lorsque vous ajoutez un élément à la hashtable, il utilise le hashcode de la clé pour décider dans quel seau il va le mettre (c'est normalement une opération très rapide, appelez GetHashCode et lui appliquer un modulo). Une fois qu'il a le bucket (qui est une sorte de liste), il vérifie si le bucket contient déjà un élément avec la même clé, et l'ajoute si ce n'est pas le cas. Ceci est également très rapide, car chaque compartiment contient seulement un petit sous-ensemble de tous les éléments de la table de hachage. Lorsque vous voulez récupérer un élément en fonction de sa clé, il détermine le compartiment en fonction du code de hachage de la clé et recherche un élément avec cette clé dans le compartiment.

Bien sûr, c'est une description très simpliste ... regardez l'article Wikipedia pour plus de détails.