J'ai une table de hachage. Par exemple, j'ai deux entités comme

john = { 1stname: jonh, 2ndname: johnson },
eric = { 1stname: eric, 2ndname: ericson }

Ensuite, je les mets en hashtable:

ht["john"] = john;
ht["eric"] = eric;

Imaginons qu'il y ait une collision et que la table de hachage utilise le chaînage pour la corriger. En conséquence, il devrait y avoir une liste liée avec ces deux entités comme celle-ci entrez la description de l'image  ici Comment hashtable comprend-il quelle entité doit être retournée pour la clé? Les valeurs de hachage sont les mêmes et il ne sait rien de la structure des entités. Par exemple, si j'écris ceci var val = ht["john"]; comment la table de hachage (n'ayant que la valeur de la clé et son hachage) découvre que la valeur doit être john record et non eric .

11
mtkachenko 17 janv. 2017 à 15:27

2 réponses

Meilleure réponse

Je pense que ce que vous êtes confus, c'est ce qui est stocké à chaque emplacement dans la liste adjacente de la table de hachage. Il semble que vous supposiez que seule la valeur est stockée. En fait, les données de chaque nœud de liste sont un tuple (clé, valeur).

Une fois que vous avez demandé ht['john'], la table de hachage trouve la liste associée à hash('john') et si la liste n'est pas vide, elle recherche la clé 'john' dans la liste. Si la clé est trouvée en tant que premier élément du tuple, la valeur (deuxième élément du tuple) est renvoyée. Si la clé n'est pas trouvée, cela signifie que l'élément n'est pas dans la table de hachage.

Pour résumer, la clé de hachage est utilisée pour identifier rapidement la cellule dans laquelle l'élément doit être stocké s'il est présent. L ' égalité de clé réelle est testée pour déterminer si la clé existe ou non.

16
George Octavian Rabanca 17 janv. 2017 à 16:33

Est-ce ce que vous demandez? J'ai déjà mis cela dans les commentaires mais il me semble que vous n'avez pas suivi le lien

Résolution de collision dans la classe Hashtable

Rappelez-vous que lors de l'insertion d'un élément dans ou de la récupération d'un élément d'une table de hachage, une collision peut se produire. Lors de l'insertion d'un élément, un emplacement ouvert doit être trouvé. Lors de la récupération d'un élément, l'élément réel doit être trouvé s'il ne se trouve pas à l'emplacement prévu. Auparavant, nous avons brièvement examiné deux stratégies de résolution de collusion:

  • Palpage linéaire
  • Sondage quadratique

La classe Hashtable utilise une technique différente appelée rehasing. (Certaines sources appellent le rehashing le double hachage.)

Rehasing fonctionne comme suit: il existe un ensemble de fonctions de hachage différentes, H1 ... Hn, et lors de l'insertion ou de la récupération d'un élément de la table de hachage, la fonction de hachage H1 est initialement utilisée. Si cela conduit à une collision, H2 est essayé à la place, puis jusqu'à Hn si nécessaire. La section précédente n'a montré qu'une seule fonction de hachage, qui est la fonction de hachage initiale (H1). Les autres fonctions de hachage sont très similaires à cette fonction, ne se différenciant que par un facteur multiplicatif. En général, la fonction de hachage Hk est définie comme:

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

Note mathématique Avec la remise en forme, il est important que chaque emplacement dans la table de hachage soit visité exactement une fois lorsque le nombre de hachage de sondes est effectué. Autrement dit, pour une clé donnée, vous ne voulez pas que Hi et Hj hachent le même emplacement dans la table de hachage. Avec la formule de rehachage utilisée par la classe Hashtable, cette propriété est conservée si le résultat de (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) et hashsize sont relativement premiers. (Deux nombres sont relativement premiers s'ils ne partagent pas de facteurs communs.) Ces deux nombres sont garantis relativement premiers si la taille de hachage est un nombre premier. Le rehasing offre une meilleure évitement des collisions que le palpage linéaire ou quadratique.

sources ici

2
a-man 17 janv. 2017 à 13:01