HashMap interne en Java

[note de l'auteur de la traduction] La traduction a été faite pour ses propres besoins, mais si elle s'avère utile à quelqu'un, alors le monde est devenu au moins un peu, mais mieux! Article d'origine - Fonctionnement interne de HashMap en Java

Dans cet article, nous verrons comment les méthodes get et put dans la collection HashMap fonctionnent en interne. Quelles opérations sont effectuées. Comment le hachage se produit. Comment la valeur est récupérée par clé. Comment les paires clé-valeur sont-elles stockées?

Comme dans l' article précédent , HashMap contient un tableau de Node et Node peut représenter une classe contenant les objets suivants:

1. int - hachage
2. K est la clé
3. V est la valeur
4. Noeud - élément suivant

Nous allons maintenant voir comment tout cela fonctionne. Tout d'abord, nous allons examiner le processus de hachage.

Hachage

Le hachage est le processus de conversion d'un objet en une forme entière, effectué à l'aide de la méthode hashCode (). Il est très important d'implémenter correctement la méthode hashCode () pour garantir les meilleures performances de la classe HashMap.

Ici, j'utilise ma propre classe Key et de cette façon, je peux remplacer la méthode hashCode () pour illustrer divers scripts. Ma classe de clé:

//   Key    hashCode() //  equals() class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public boolean equals(Object obj) { return key.equals((String)obj); } } 

Ici, la méthode hashCode () substituée renvoie le code ASCII du premier caractère de la chaîne. Ainsi, si les premiers caractères de la chaîne sont identiques, les codes de hachage seront les mêmes. N'utilisez pas de logique similaire dans vos programmes.

Ce code est uniquement à des fins de démonstration. Étant donné que le HashCode accepte une clé nulle, le code de hachage nul sera toujours 0.

Méthode HashCode ()

La méthode hashCode () est utilisée pour obtenir le code de hachage de l'objet. La méthode hashCode () de la classe Object renvoie une référence de mémoire entière (code de hachage d'identité ). La signature de la public native hashCode() . Cela suggère que la méthode est implémentée comme native, car en java il n'y a pas de méthode pour obtenir une référence à l'objet. Il est autorisé de définir votre propre implémentation de la méthode hashCode (). Dans la classe HashMap, la méthode hashCode () est utilisée pour calculer le compartiment et donc calculer l'index.

Méthode Equals ()

La méthode equals est utilisée pour tester l'égalité de deux objets. La méthode est implémentée dans la classe Object. Vous pouvez le remplacer dans votre propre classe. Dans la classe HashMap, la méthode equals () est utilisée pour vérifier l'égalité des clés. Si les clés sont égales, la méthode equals () renvoie true, sinon false.

Paniers

Bucket est le seul élément du tableau HashMap. Il est utilisé pour stocker des nœuds (Nodes). Deux nœuds ou plus peuvent avoir le même compartiment. Dans ce cas, une structure de données de liste liée est utilisée pour lier les nœuds. La capacité des godets diffère (propriété de capacité). La relation entre le compartiment et la capacité est la suivante:

 capacity = number of buckets * load factor 

Un compartiment peut avoir plusieurs nœuds, cela dépend de l'implémentation de la méthode hashCode (). Mieux votre méthode hashCode () est implémentée, meilleur sera votre bucket.

Calcul de l'indice HashMap

Le code de hachage de clé peut être suffisamment grand pour créer un tableau. Le code de hachage généré peut être dans la plage d'un type entier et si nous créons un tableau de cette taille, nous pouvons facilement obtenir une exception outOfMemoryException. Par conséquent, nous générons un index pour minimiser la taille du tableau. En substance, l'opération suivante est effectuée pour calculer l'indice:

 index = hashCode(key) & (n-1). 

où n est égal au nombre de compartiments ou à la valeur de la longueur du tableau. Dans notre exemple, je considère n comme la valeur par défaut de 16.

• initialement hashMap vide: ici la taille du hashmap est 16:

 HashMap map = new HashMap(); 

HashMap:

• insérer des paires Clé - Valeur: ajouter une paire clé - valeur à la fin du HashMap

 map.put(new Key("vishal"), 20); 

Étapes:

1. Calculez la valeur clé {"vishal"}. Il sera généré sous la forme 118.

   
   

2. Calculez l'indice en utilisant la méthode de l' index , qui sera 6.

   
   

3. Créez un objet nœud.

   
   

    { int hash = 118 // {"vishal"}  ,  //   Key Key key = {"vishal"} Integer value = 20 Node next = null } 

   
   

4. Placez l'objet en position avec l'index 6, si l'espace est libre.

   
   

HashMap ressemble maintenant à ceci:

• ajout d'une autre paire valeur / clé: ajoutez maintenant une autre paire

 map.put(new Key("sachin"), 30); 

Étapes:

1. Calculez la valeur clé {"sachin"}. Il sera généré sous la forme 115.

   
   

2. Calculez l'indice en utilisant la méthode de l' index , qui sera 3.

   
   

3. Créez un objet nœud.

   
   

    { int hash = 115 Key key = {"sachin"} Integer value = 30 Node next = null } 

   
   

4. Placez l'objet en position avec l'index 3, si l'espace est libre.

   
   

HashMap ressemble maintenant à ceci:

• en cas de collision: ajoutez maintenant une autre paire

 map.put(new Key("vaibhav"), 40); 

Étapes:

1. Calculez la valeur de clé {"vaibhav"}. Il sera généré sous la forme 118.

   
   

2. Calculez l'indice en utilisant la méthode de l' index , qui sera 6.

   
   

3. Créez un objet nœud.

   
   

    { int hash = 118 Key key = {"vaibhav"} Integer value = 20 Node next = null } 

   
   

4. Placez l'objet en position avec l'index 6, si l'espace est libre.

   
   

5. Dans ce cas, un autre objet existe déjà à la position d'indice 6, ce cas est appelé collision.

   
   

6. Dans ce cas, vérifie avec les méthodes hashCode () et equals () que les deux clés sont identiques.

   
   

7. Si les clés sont identiques, remplacez la valeur actuelle par une nouvelle.

   
   

8. Sinon, liez les objets nouveaux et anciens à l'aide de la structure de données "liste liée" en spécifiant un lien vers l'objet suivant dans l'objet actuel et enregistrez-les tous les deux sous l'index 6.

   
   

HashMap ressemble maintenant à ceci:

[note de l'auteur de la traduction] L'image est tirée de l'article d'origine et contient initialement une erreur. La référence à l'objet suivant dans l'objet vishal avec l'index 6 n'est pas nulle, elle contient un pointeur vers l'objet vaibhav.

• nous obtenons la valeur par la clé sachin:

 map.get(new Key("sachin")); 

Étapes:

1. Calculez le code de hachage de l'objet {{sachin »}. Il a été généré en tant que 115.

   
   

2. Calculez l'indice en utilisant la méthode de l' index , qui sera 3.

   
   

3. Allez à l'index 3 et comparez la clé du premier élément avec la valeur existante. S'ils sont égaux, tournez la valeur; sinon, recherchez l'élément suivant, s'il existe.

   
   

4. Dans notre cas, l'élément est trouvé et la valeur de retour est 30.

   
   

• nous obtenons la valeur par la clé vaibahv:

 map.get(new Key("vaibhav")); 

Étapes:

1. Calculez le code de hachage de l'objet {"vaibhav"}. Il a été généré en 118.

   
   

2. Calculez l'indice en utilisant la méthode de l' index , qui sera 6.

   
   

3. Allez à l'index 6 et comparez la clé du premier élément avec la valeur existante. S'ils sont égaux, tournez la valeur; sinon, recherchez l'élément suivant, s'il existe.

   
   

4. Dans ce cas, il n'a pas été trouvé et l'objet nœud suivant n'est pas nul.

   
   

5. Si l'objet nœud suivant est null, retournez null.

   
   

6. Si l'objet nœud suivant n'est pas nul, accédez-y et répétez les trois premières étapes jusqu'à ce que l'élément soit trouvé ou que l'objet nœud suivant soit nul.

   
   

 // Java    //   HashMap import java.util.HashMap; class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key)obj).key); } } // Driver class public class GFG { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); } } 

Conclusion:

 hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40 

Changements dans Java 8

Comme nous le savons déjà en cas de collision, l'objet nœud est stocké dans la structure de données «liste liée» et la méthode equals () est utilisée pour comparer les clés. Ce sont des comparaisons pour trouver la bonne clé dans une liste chaînée - une opération linéaire et, dans le pire des cas, la complexité est O (n) .

Pour résoudre ce problème dans Java 8, après avoir atteint un certain seuil, des arborescences équilibrées sont utilisées à la place des listes liées. Cela signifie que le HashMap au début enregistre les objets dans une liste chaînée, mais une fois que le nombre d'éléments dans le hachage atteint un certain seuil, une transition vers des arbres équilibrés se produit. Ce qui améliore les performances dans le pire des cas de O (n) à O (log n).

Point important

1. La complexité des opérations get () et put () est presque constante jusqu'à ce que le hachage soit effectué.
2. En cas de collisions, si les indices de deux ou plusieurs objets nœuds sont identiques, les objets nœuds sont connectés à l'aide d'une liste chaînée, c'est-à-dire le lien vers le deuxième objet nœud est stocké dans le premier, vers le troisième dans le second, etc.
3. Si la clé donnée existe déjà dans le HashMap, la valeur est remplacée.
4. Le code de hachage nul est 0.
5. Lorsqu'un objet est obtenu par la clé, des transitions à travers la liste liée se produisent jusqu'à ce que l'objet soit trouvé ou que le lien vers l'objet suivant soit nul.