Comment les HashTables traitent-ils les collisions?

J’ai entendu dans mes cours de degré qu’un HashTable placera une nouvelle entrée dans le HashTable «next available» si la nouvelle entrée de clé se heurte à une autre.

Comment le HashTable toujours la valeur correcte si cette collision se produit lors de l’appel de la clé de collision?

Je suppose que les Keys sont de type Ssortingng et que le hashCode() renvoie la valeur par défaut générée par Java.

Si HashMap ma propre fonction de hachage et que je l’utilise dans le cadre d’une table de HashMap (c.-à-d. Un HashMap ou un Dictionary ), quelles stratégies existent pour gérer les collisions?

J’ai même vu des notes relatives aux nombres premiers! Informations pas si claires de la recherche Google.

Les tables de hachage traitent les collisions de deux manières.

Option 1: Chaque compartiment doit contenir une liste liée d’éléments regroupés dans ce compartiment. C’est pourquoi une mauvaise fonction de hachage peut ralentir les recherches dans les tables de hachage.

Option 2: Si les entrées de la table de hachage sont toutes remplies, la table de hachage peut augmenter le nombre de compartiments qu’elle contient, puis redissortingbuer tous les éléments de la table. La fonction de hachage retourne un nombre entier et la table de hachage doit prendre le résultat de la fonction de hachage et le modifier en fonction de la taille de la table de manière à ce qu’il soit sûr de parvenir à bucket. Ainsi, en augmentant la taille, le programme modifie et exécute les calculs modulo qui, si vous êtes chanceux, peuvent envoyer les objects à différents compartiments.

Java utilise les options 1 et 2 dans ses implémentations de table de hachage.

Lorsque vous parlez de “Hash Table placera une nouvelle entrée dans le compartiment” next available “si la nouvelle entrée Key entre en collision avec une autre.”, Vous parlez de la stratégie d’adressage Open de Résolution de collision de la table de hachage.


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

Le premier type de grande méthode exige que les clés (ou les pointeurs vers elles) soient stockées dans la table, avec les valeurs associées, qui incluent en outre:

  • Chaînage séparé

entrer la description de l'image ici

  • Adressage ouvert

entrer la description de l'image ici

  • Hachage coalescent
  • Coucou
  • Robin Hood
  • Hachage à 2 choix
  • Hachage à la marelle

Le redimensionnement dynamic est une autre méthode importante pour gérer les collisions:

  • Redimensionnement en copiant toutes les entrées
  • Redimensionnement incrémentiel
  • Touches monotones

EDIT : ce qui précède est emprunté à wiki_hash_table , où vous devriez aller pour avoir plus d’informations.

Je vous suggère fortement de lire cet article paru récemment sur HackerNews: Comment HashMap fonctionne-t-il en Java?

En bref, la réponse est

Que se passera-t-il si deux objects clés HashMap différents ont le même code de hachage?

Ils seront stockés dans le même compartiment mais pas dans le prochain nœud de la liste chaînée. Et la méthode keys equals () sera utilisée pour identifier la paire de valeurs de clé correcte dans HashMap.

Il existe plusieurs techniques disponibles pour gérer les collisions. Je vais en expliquer quelques uns

Chaînage: En chaînage, nous utilisons des index de tableau pour stocker les valeurs. Si le code de hachage de la deuxième valeur pointe également vers le même index, nous remplaçons cette valeur d’index par une liste liée et toutes les valeurs pointant vers cet index sont stockées dans la liste liée et l’index de la table liée. Mais si un seul code de hachage pointe vers un index de tableau, la valeur est directement stockée dans cet index. La même logique est appliquée lors de la récupération des valeurs. Ceci est utilisé dans Java HashMap / Hashtable pour éviter les collisions.

Sondage linéaire: Cette technique est utilisée lorsque nous avons plus d’index dans la table que les valeurs à stocker. La technique de sondage linéaire travaille sur le concept de l’incrémentation continue jusqu’à ce que vous trouviez l’emplacement vide. Le pseudo-code ressemble à ceci ..

index = h (k)

tandis que (val (index) est occupé)

index = (index + 1) mod n

Technique de double hachage: Dans cette technique, nous utilisons deux fonctions de hachage h1 (k) et h2 (k). Si l’emplacement à h1 (k) est occupé, la deuxième fonction de hachage h2 (k) est utilisée pour incrémenter l’index. Le pseudo-code ressemble à ceci ..

index = h1 (k)

tandis que (val (index) est occupé)

index = (index + h2 (k)) mod n

Les techniques de sondage linéaire et de double hachage font partie de la technique d’adressage ouvert et ne peuvent être utilisées que si les créneaux disponibles sont supérieurs au nombre d’éléments à append. Cela prend moins de mémoire que le chaînage car il n’y a pas de structure supplémentaire utilisée ici, mais c’est lent car beaucoup de mouvements se produisent jusqu’à ce que nous trouvions un emplacement vide. De même, dans la technique d’adressage ouvert, lorsqu’un élément est retiré d’un emplacement, nous mettons une pierre tombale pour indiquer que l’élément est retiré d’ici, c’est pourquoi il est vide.

Tiré de http://coder2design.com/hashing/

J’ai entendu dans mes cours de degré qu’un HashTable placera une nouvelle entrée dans le compartiment «next available» si la nouvelle entrée de clé se heurte à une autre.

Ce n’est en fait pas vrai, du moins pour le JDK Oracle (c’est un détail d’implémentation qui peut varier entre les différentes implémentations de l’API). Au lieu de cela, chaque compartiment contient une liste liée d’entrées.

alors comment le HashTable retournerait-il toujours la valeur correcte si cette collision se produit lors de l’appel de la clé de collision?

Il utilise les equals() pour trouver l’entrée correspondant effectivement.

Si j’implémente ma propre fonction de hachage et que je l’utilise dans le cadre d’une table de consultation (c.-à-d. Un HashMap ou un dictionnaire), quelles stratégies existent pour gérer les collisions?

Il existe différentes stratégies de gestion des collisions avec différents avantages et inconvénients. L’entrée de Wikipedia sur les tables de hachage donne un bon aperçu.

Comme il existe une certaine confusion sur l’algorithme utilisé par Java HashMap (dans l’implémentation Sun / Oracle / OpenJDK), voici les extraits de code source pertinents (à partir d’OpenJDK, 1.6.0_20, sur Ubuntu):

 /** * Returns the entry associated with the specified key in the * HashMap. Returns null if the HashMap contains no mapping * for the key. */ final Entry getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } 

Cette méthode (cite des lignes 355 à 371) est appelée lors de la recherche d’une entrée dans la table, par exemple à partir de get() , containsKey() et d’autres. La boucle for passe ici par la liste chaînée formée par les objects d’entrée.

Voici le code des objects d’entrée (lignes 691-705 + 759):

 static class Entry implements Map.Entry { final K key; V value; Entry next; final int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; } // (methods left away, they are straight-forward implementations of Map.Entry) } 

Juste après vient la méthode addEntry() :

 /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } 

Cela ajoute la nouvelle entrée sur le devant du compartiment, avec un lien vers l’ancienne première entrée (ou null, si tel n’est pas le cas). De même, la méthode removeEntryForKey() parcourt la liste et prend soin de supprimer une seule entrée, laissant le rest de la liste intact.

Donc, voici une liste d’entrées liées pour chaque compartiment, et je doute fort que cela soit passé de _20 à _22 , puisque c’était comme ça à partir de 1.2.

(Ce code est (c) 1997-2007 Sun Microsystems, et disponible sous GPL, mais pour copier mieux, utilisez le fichier original, contenu dans src.zip dans chaque JDK de Sun / Oracle et dans OpenJDK.)

Il utilisera la méthode des égaux pour voir si la clé est présente même s’il y a plus d’un élément dans le même compartiment.

Mise à jour depuis Java 8: Java 8 utilise un arbre auto-équilibré pour la gestion des collisions, améliorant le cas le plus défavorable de O (n) à O (log n) pour la recherche. L’utilisation d’un arbre auto-équilibré a été introduite dans Java 8 en tant qu’amélioration par rapport au chaînage (utilisé jusqu’à Java 7), qui utilise une liste liée et présente le pire cas de O (n) pour la recherche la liste)

Pour répondre à la deuxième partie de votre question, l’insertion est effectuée en mappant un élément donné sur un index donné dans le tableau sous-jacent du hashmap. Cependant, en cas de collision, tous les éléments doivent toujours être conservés (stockés dans une structure de données secondaire). , et pas seulement remplacé dans le tableau sous-jacent). Cela se fait généralement en faisant de chaque tableau (composant) une structure de données secondaire (alias bucket), et l’élément est ajouté au compartiment résidant sur l’index de tableau donné (si la clé n’existe pas déjà dans le compartiment, dans quel cas il est remplacé).

Au cours de la recherche, la clé est hachée vers son index de tableau correspondant et une recherche est effectuée pour un élément correspondant à la clé (exacte) dans le compartiment donné. Étant donné que le compartiment n’a pas besoin de gérer les collisions (compare directement les clés), cela résout le problème des collisions, mais au prix de l’insertion et de la recherche dans la structure de données secondaire. Le point clé est que, dans un hashmap, la clé et la valeur sont stockées, et même si le hachage se heurte, les clés sont comparées directement pour l’égalité (dans le compartiment) et peuvent donc être identifiées de manière unique dans le compartiment.

La gestion des collisions apporte les performances d’insertion et de recherche les plus défavorables de O (1) en l’absence de gestion des collisions à O (n) pour le chaînage (une liste liée est utilisée en tant que structure de données secondaire) et O (log n) pour arbre auto-équilibré.

Les références:

Java 8 est fourni avec les améliorations / modifications suivantes des objects HashMap en cas de collision importante.

  • La fonction de hachage de chaîne alternative ajoutée à Java 7 a été supprimée.

  • Les compartiments contenant un grand nombre de clés en collision stockeront leurs entrées dans une arborescence équilibrée au lieu d’une liste liée une fois que certains seuils auront été atteints.

Les modifications ci-dessus garantissent les performances de O (log (n)) dans les pires scénarios ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 ).

Il existe différentes méthodes pour la résolution des collisions.

Java utilise le chaînage séparé pour résoudre les collisions dans les tables de hachage.Voici un excellent lien vers ce qui se passe: http://javapapers.com/core-java/java-hashtable/

voici une implémentation de table de hachage très simple en Java. in n’implémente que put() et get() , mais vous pouvez facilement append ce que vous voulez. il repose sur la hashCode() de java implémentée par tous les objects. vous pouvez facilement créer votre propre interface,

 interface Hashable { int getHash(); } 

et le forcer à être implémenté par les touches si vous le souhaitez.

 public class Hashtable { private static class Entry { private final K key; private final V val; Entry(K key, V val) { this.key = key; this.val = val; } } private static int BUCKET_COUNT = 13; @SuppressWarnings("unchecked") private List[] buckets = new List[BUCKET_COUNT]; public Hashtable() { for (int i = 0, l = buckets.length; i < l; i++) { buckets[i] = new ArrayList>(); } } public V get(K key) { int b = key.hashCode() % BUCKET_COUNT; List ensortinges = buckets[b]; for (Entry e: ensortinges) { if (e.key.equals(key)) { return e.val; } } return null; } public void put(K key, V val) { int b = key.hashCode() % BUCKET_COUNT; List ensortinges = buckets[b]; ensortinges.add(new Entry(key, val)); } }