Comment les tables de hashage gérer les collisions?

Question

J'ai entendu dans mon degré de classes que d'une table de hachage place une nouvelle entrée dans le "prochain" seau si la nouvelle Clé d'entrée en collision avec un autre.

Comment l' HashTable toujours retourner la Valeur correcte si cette collision se produit lors de l'appel pour un retour à la collision de la clé?

Je suis en supposant que l' Keys sont String type et l' hashCode() renvoie la valeur par défaut généré par dire Java.

Si j'ai appliquer ma propre fonction de hachage et de l'utiliser dans le cadre d'une look-up table (c'est à dire une table de hachage ou un Dictionnaire), quelles stratégies existent pour traiter les collisions?

C'est fait à l'aide de nombres premiers? L'Information n'est pas si clair de recherche Google..

Answer 1

Les tables de hachage de gérer les collisions dans l'une des deux façons.

Option 1: En fait, pour chaque seau contient une liste chaînée d'éléments qui sont hachés à ce compartiment. C'est pourquoi une mauvaise fonction de hachage peut faire des recherches dans les tables de hachage très lent.

Option 2: Si la table de hachage entrées sont tous plein puis la table de hachage peut augmenter le nombre de compartiments que l'on a et puis de redistribuer tous les éléments dans le tableau. La fonction de hachage renvoie un entier et d'une table de hachage doit prendre le résultat de la fonction de hachage et de la défense contre la taille de la table de cette façon, il peut être sûr qu'il va obtenir dans le seau. donc, en augmentant la taille, il sera réchauffé et exécuter les calculs modulo qui, si vous êtes chanceux, peut envoyer des objets à compartiments différents.

Java utilise à la fois des options 1 et 2 dans la table de hachage des implémentations.

Answer 2

Quand vous avez parlé de "Table de Hachage place une nouvelle entrée dans le "prochain" seau si la nouvelle Clé d'entrée en collision avec un autre.", vous parlez de l' abordant la stratégie de résolution de Collision de la table de hachage.

---

Il existe plusieurs stratégies pour table de hachage pour résoudre collision.

Premier type de grand méthode nécessite que les clés (ou pointeurs) être stockés dans la table, avec les valeurs associées, qui comprend en outre:

• Le chaînage séparé

• En abordant

• Conflué de hachage
• Coucou hachage
• Robin des bois de hachage
• 2-choix de hachage
• La marelle de hachage

---

Une autre méthode importante pour gérer la collision est par un redimensionnement Dynamique, qui dispose en outre de plusieurs façons:

• Redimensionnement par la copie de tous les bulletins de participation
• Différentiels de redimensionnement
• Monotone clés

---

EDIT: ci-dessus sont empruntés à la wiki_hash_table, où vous devez aller pour avoir un coup d'oeil pour obtenir plus d'infos.

Answer 3

Je vous suggère fortement de lire ce blog, qui est apparu sur HackerNews récemment: Comment HashMap fonctionne en Java

En bref, la réponse est

Ce qui va se passer si les deux Table de hachage de la clé objets ont la même hashcode?

Ils seront stockés dans le même seau, mais pas de nœud suivant de la liste liée. Et les touches méthode equals () sera utilisée pour identifier corriger la valeur de la clé de la paire dans HashMap.

Answer 4

J'ai entendu dans mon cours qu'un degré Table de hachage place une nouvelle entrée dans le le "prochain" seau si la nouvelle Entrée de clé entre en collision avec un autre.

Ce n'est effectivement pas vrai, au moins pour l'Oracle JDK (c' est un détail d'implémentation qui pourrait varier entre les différentes implémentations de l'API). Au lieu de cela, chaque seau contient une liste d'entrées.

alors comment la table de hachage encore de retour de la Valeur correcte, si ce une collision se produit lors de l'appel pour un de retour à la collision de la clé?

Il utilise l' equals() à trouver l'entrée correspondante.

Si j'ai appliquer ma propre fonction de hachage et de l'utiliser dans le cadre d'une look-up table) (c'est à dire une table de hachage ou un Dictionnaire), ce qui des stratégies existent pour traiter les les collisions?

Il existe différents collision de la manipulation des stratégies avec des avantages et des inconvénients. Wikipedia inscription sur les tables de hachage donne un bon aperçu.

Answer 5

Il va utiliser la méthode equals pour voir si la clé est présente, même et surtout s'il y a plus d'un élément dans le même seau.