En interne, comment les hachages recherchent-ils la clé pour obtenir la valeur?

Question

En interne, comment les hachages recherchent-ils la clé pour obtenir la valeur?

Serait-ce le tri des bacs?

Answer 1

Un dictionnaire utilise le hashcode pour calculer le numéro du compartiment dans lequel l'entrée est stockée. Le nombre de compartiments est choisi pour être un nombre premier et le numéro de compartiment pour une clé spécifique est calculé comme le code de hachage de la clé modulo le nombre de compartiments. Comme plusieurs objets peuvent avoir le même code de hachage et que plusieurs codes de hachage peuvent atterrir dans le même compartiment, lorsqu'une clé est trouvée dans un compartiment, elle doit également être comparée pour l'égalité afin de s'assurer qu'elle est la bonne. Si une clé incorrecte est trouvée dans le compartiment, le membre next de la mauvaise entrée est utilisé pour trouver l'emplacement suivant pour rechercher la clé souhaitée. Le résultat de cet algorithme est que lorsqu'il n'y a pas de collisions, le bon compartiment peut être trouvé très rapidement - O (1), mais dans le pire des cas, il peut prendre un temps linéaire dans le nombre d'entrées stockées dans le dictionnaire. Je suppose ici que le code de hachage d'un objet peut être calculé en temps constant.

Le code réel dans la mise en œuvre .NET peut être vu en téléchargeant la référence source de mise en œuvre, ou en utilisant réflecteur .NET:

private int FindEntry(TKey key) 
{ 
    if (key == null) 
    { 
     ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); 
    } 
    if (this.buckets != null) 
    { 
     int num = this.comparer.GetHashCode(key) & 0x7fffffff; 
     for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next) 
     { 
      if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key)) 
      { 
       return i; 
      } 
     } 
    } 
    return -1; 
} 

Answer 2

Un hachage est juste une course d'algorithme contre une clé qui crée (je l'espère) une valeur unique qui pointe vers quel compartiment stocker un élément. Ainsi, lorsque vous calculez la valeur pour essayer de récupérer cet élément, vous espérez que le hachage vous dirigera vers l'objet que vous avez enregistré précédemment. Sinon, il devrait y avoir un pointeur sur l'endroit où chercher l'objet suivant qui partage cette valeur de hachage. Lorsque vous trouvez votre article, il reviendra. Si la fin de la chaîne est atteinte, votre article ne peut pas être trouvé.

Voir Hash Tables et Hash Function pour une définition plus complète du hachage.