table[indexFor(hash, table.length)] est le HashMap du HashMap qui peut contenir la clé que nous recherchons (si elle est présente dans la Map ).

Cependant, chaque compartiment peut contenir plusieurs entrées (soit des clés différentes ayant le même hashCode() , soit des clés différentes avec un hashCode() qui rest mappé au même compartiment), vous devez donc parcourir ces entrées jusqu’à ce que vous trouviez la clé sont en train de chercher.

Étant donné que le nombre d’entrées attendu dans chaque compartiment doit être très petit, cette boucle est toujours exécutée dans le temps O(1) attendu.

Si vous voyez le fonctionnement interne de la méthode get de HashMap.

 public V get(Object key) { if (key == null) return getForNullKey(); int hash = 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.equals(k))) return e.value; } return null; } 

• Tout d’abord, il obtient le code de hachage de l’object clé qui est transmis et trouve l’emplacement du compartiment.
• Si le bon compartiment est trouvé, il renvoie la valeur (valeur e.value)
• Si aucune correspondance n’est trouvée, il renvoie null.

Parfois, il peut y avoir des risques de collision avec Hashcode et pour résoudre cette collision, Hashmap utilise equals (), puis stocke cet élément dans LinkedList dans le même compartiment.

Prenons l’exemple:

Récupère les données pour la clé vaibahv: map.get (new Key (“vaibhav”));

Pas:

1. Calculez le code de hachage de la clé {«vaibhav»}. Il sera généré en tant que 118.

2. Calculez l’index en utilisant la méthode d’indexation.

3. Aller à l’index 6 du tableau et comparer la clé du premier élément avec la clé donnée. Si les deux sont égaux, renvoyez la valeur, sinon vérifiez l’élément suivant s’il existe.

4. Dans notre cas, il n’est pas trouvé en tant que premier élément et le prochain object du noeud n’est pas nul.

5. Si next of node est null, retournez null.

6. Si next of node n’est pas null, passez au second élément et répétez le processus 3 jusqu’à ce que la clé ne soit pas trouvée ou que next ne soit pas null.

Pour ce processus de récupération pour la boucle sera utilisé. Pour plus de référence, vous pouvez vous référer à cette

Pour l’enregistrement, dans java-8, ceci est également présent (en quelque sorte, car il ya aussi des TreeNode s):

 if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } 

Fondamentalement (pour le cas où le bac n’est pas un Tree ), effectuez une itération complète du bac jusqu’à ce que vous trouviez l’entrée que vous recherchez.

En regardant cette implémentation, vous comprendrez peut-être pourquoi fournir un bon hachage est une bonne chose – de sorte que toutes les entrées ne se retrouvent pas dans le même compartiment, ce qui augmente le temps de recherche.

Je pense que @Eran a déjà bien répondu à votre question et que @Prashant a également fait une bonne tentative avec d’autres personnes qui ont répondu, alors laissez-moi vous expliquer en utilisant un exemple pour que ce concept devienne très clair .

Les concepts

Fondamentalement, ce que @Eran essaie de dire, c’est que dans un compartiment donné (essentiellement à un index donné du tableau), il est possible qu’il y ait plus d’une entrée (rien que l’object Entry ) et que mais donnez le même emplacement index / seau.

Maintenant, pour mettre l’entrée dans le hashmap, c’est ce qui se passe à un niveau élevé ( lisez attentivement parce que j’ai fait un effort supplémentaire pour expliquer certaines bonnes choses qui ne font normalement pas partie de votre question ):

• Obtenir le hachage: ce qui se passe ici est que le premier hachage est calculé pour une clé donnée (notez que ce n’est pas un hashCode , un hachage est calculé à l’aide du hashCode et atténue le risque d’une fonction de hachage mal écrite).
• Obtenir l’index: il s’agit essentiellement de l’index du tableau ou, en d’autres termes, du compartiment. Maintenant, pourquoi cet index est-il calculé au lieu d’utiliser directement le hachage comme index parce que pour réduire le risque que le hachage dépasse la taille du hashmap, cette étape de calcul d’index garantit que l’index sera toujours inférieur à la taille du hachage hashmap.

Et quand une situation se produit lorsque 2 clés donnent un hachage différent mais le même index, alors les deux vont aller dans le même compartiment, et c’est la raison pour laquelle la boucle FOR est importante.

Exemple

Voici un exemple simple que j’ai créé pour vous démontrer le concept:

 public class Person { private int id; Person(int _id){ id = _id; } public int getId() { return id; } public void setId(int id) { this.id = id; } @Override public int hashCode() { return id; } } 

Classe de test:

 import java.util.Map; public class HashMapHashingTest { public static void main(Ssortingng[] args) { Person p1 = new Person(129); Person p2 = new Person(133); Map hashMap = new MyHashMap<>(2); hashMap.put(p1, "p1"); hashMap.put(p2, "p2"); System.out.println(hashMap); } } 

Capture d’écran de débogage (veuillez cliquer et zoomer car il est petit):

Notez que, dans l’exemple ci-dessus, les deux objects Person donnent une valeur de hachage différente (respectivement 136 et 140) mais donnent le même index de 0, les deux objects sont donc placés dans le même compartiment. Dans la capture d’écran, vous pouvez voir que les deux objects sont à l’index 0 et que vous avez ensuite un next élément qui pointe essentiellement vers le second object.

Mise à jour: Une autre façon la plus simple de voir plus d’une clé dans le même compartiment est de créer une classe et de remplacer la méthode hashCode pour toujours renvoyer la même valeur int. Maintenant, tous les objects de cette classe donneraient le même emplacement index / bucket, mais comme vous n’avez pas remplacé la méthode equals , ils ne seraient pas considérés comme identiques et formeraient donc une liste à cet emplacement index / bucket.

Une autre torsion de ceci supposerait que vous outrepassiez la méthode equals et que vous compariez tous les objects égaux, alors qu’un seul object sera présent à l’emplacement index / compartiment parce que tous les objects sont égaux.

Alors que les autres réponses expliquent ce qui se passe, les commentaires de l’OP sur ces réponses m’amènent à penser qu’un angle d’explication différent est nécessaire.

Exemple simplifié

Disons que vous allez lancer 10 chaînes dans une carte de hachage: “A”, “B”, “C”, “Hi”, “Bye”, “Yo”, “Yo-yo”, “Z”, “1 “,” 2 ”

Vous utilisez HashMap comme carte de hachage au lieu de créer votre propre carte de hachage (bon choix). Certains des éléments ci-dessous n’utiliseront pas directement l’implémentation de HashMap mais aborderont cette question d’un sharepoint vue plus théorique et abstrait.

HashMap ne sait pas comme par magie que vous allez y append 10 chaînes, ni les chaînes que vous y HashMap plus tard. Il doit fournir des endroits où mettre tout ce que vous pourriez lui donner … tout ce que vous savez, c’est que vous allez mettre 100 000 chaînes – peut-être chaque mot du dictionnaire.

Disons que, à cause de l’argument constructeur que vous avez choisi lors de la création de votre new HashMap(n) , votre carte de hachage contient 20 compartiments . Nous les appellerons bucket[0] travers le bucket[19] .

1. map.put("A", value); Disons que la valeur de hachage pour “A” est 5. La carte de hachage peut maintenant faire bucket[5] = new Entry("A", value);

2. map.put("B", value); Supposons un hachage (“B”) = 3. Donc, bucket[3] = new Entry("B", value);

3. map.put("C"), value); – hash (“C”) = 19 – bucket[19] = new Entry("C", value);

4. map.put("Hi", value); Maintenant, voici où ça devient intéressant. Disons que votre fonction de hachage est telle que le hachage (“Hi”) = 3. Alors maintenant, hash map veut faire un bucket[3] = new Entry("Hi", value); Nous avons un problème! bucket[3] est l’endroit où vous mettez la clé “B”, et “Hi” est certainement une clé différente de “B” … mais ils ont la même valeur de hachage . Nous avons une collision !

En raison de cette possibilité, le HashMap n’est pas réellement implémenté de cette manière. Une carte de hachage doit comporter des compartiments pouvant contenir plus d’une entrée. NOTE: Je n’ai pas dit plus d’une entrée avec la même clé , car nous ne pouvons pas l’avoir , mais il doit avoir des compartiments pouvant contenir plus d’une entrée de clés différentes . Nous avons besoin d’un seau pouvant contenir à la fois “B” et “Hi”.

Alors ne faisons pas bucket[n] = new Entry(key, value); , mais à la place, laissez bucket de type Bucket[] au lieu de Entry[] . Alors maintenant, on fait bucket[n].add( new Entry(key, value) );

Alors passons à …

bucket[3].add("B", value);

et

bucket[3].add("Hi", value);

Comme vous pouvez le voir, nous avons maintenant les entrées pour “B” et “Hi” dans le même compartiment . Maintenant, lorsque nous voulons les récupérer, nous devons parcourir tout ce qui se trouve dans le compartiment, par exemple, avec une boucle for .

Donc, le bouclage est présent à cause des collisions . Pas de collision de key , mais des collisions de hash(key) .

Pourquoi utilisons-nous une structure de données aussi folle?

Vous vous demandez peut-être à ce stade: “Attendez, QUOI?!! Pourquoi ferions-nous une chose aussi étrange comme ça ??? Pourquoi utilisons-nous une structure de données aussi compliquée et compliquée ???” La réponse à cette question serait …

Une carte de hachage fonctionne comme cela en raison des propriétés que cette configuration particulière nous fournit en raison de la manière dont les mathématiques fonctionnent. Si vous utilisez une bonne fonction de hachage qui minimise les conflits et si vous HashMap votre HashMap pour avoir plus de HashMap que le nombre d’entrées que vous devinerez , alors vous avez une carte de hachage optimisée qui sera la structure de données la plus rapide pour les insertions et requêtes de données complexes.

Votre HashMap est peut-être trop petit

Comme vous dites que vous voyez souvent ce for-loop être itéré avec plusieurs éléments dans votre débogage, cela signifie que votre HashMap peut-être trop petit. Si vous avez une idée raisonnable du nombre de choses que vous pourriez y mettre, essayez de définir une taille plus grande que celle-ci. Remarquez dans mon exemple ci-dessus que j’inscrivais 10 chaînes mais que je disposais d’une carte de hachage avec 20 seaux. Avec une bonne fonction de hachage, cela donnera très peu de collisions.

Remarque:

Note: l’exemple ci-dessus est une simplification de la question et prend quelques raccourcis pour la brièveté. Une explication complète est même un peu plus compliquée, mais tout ce que vous devez savoir pour répondre à la question posée est ici.

Les tables de hachage ont des compartiments car les hachages d’objects ne doivent pas nécessairement être uniques. Si les hachages d’objects sont égaux, les moyens, probablement, sont égaux. Si les hachages d’objects sont différents, les objects sont exactement différents. Par conséquent, les objects ayant les mêmes hachages sont regroupés dans des compartiments. La boucle for est utilisée pour itérer des objects contenus dans un tel compartiment.

En fait, cela signifie que la complexité algorithmique de la recherche d’un object dans une telle table de hachage n’est pas constante (bien que très proche de celle-ci), mais quelque chose entre logarithmique et linéaire.

Je voudrais le mettre en mots simples. la méthode put possède une boucle FOR pour parcourir la liste des clés qui se trouvent dans le même compartiment de hashCode.

Que se passe-t-il lorsque vous put la paire key-value dans le hashmap:

1. Ainsi, pour chaque key transmise au HashMap , il calculera le hashCode correspondant.
2. Tant de keys peuvent tomber sous le même hashCode . Désormais, HashMap vérifie si la même key est déjà présente ou non dans le même compartiment.
3. Dans Java 7, HashMap conserve toutes les clés du même compartiment dans une liste. Donc, avant d’insérer la clé, elle parcourra la liste pour vérifier si la même clé est présente ou non. C’est pourquoi il existe une boucle FOR.

Donc, en moyenne, sa complexité en temps: O(1) et dans le pire des cas, sa complexité en temps est O(N) .