Comment fonctionne HashMap en Java

La plupart d’entre vous conviendront que HashMap, aujourd’hui, c’est le sujet de discussion préféré lors des entretiens. Parfois, j’avais des discussions similaires avec mes collègues et cela m’a vraiment aidé. Maintenant, je vais avoir une telle discussion avec vous. Je suppose que si vous êtes intéressé par les composants internes et le fonctionnement de HashMap, alors vous connaissez déjà les bases de HashMap , je vais donc sauter cette partie. Mais si vous êtes nouveau dans ce domaine, je vous suggère de vous rendre sur le site Java Docs . Avant de continuer, je vous recommande fortement de consulter mon article précédent : Travailler avec hashCode et la méthode égale en Java. Contenu de cet article :

1. La seule réponse possible.
2. Qu'est-ce que le hachage.
3. Un peu sur la classe Entry.
4. Que fait le put().
5. Comment fonctionne la méthode get().
6. Remarques

La seule réponse possible

Si quelqu'un me demande d'expliquer " Comment fonctionne HashMap ?" », je répondrai simplement : « Selon les principes du Hashing ». Cela ne pourrait pas être plus simple. Pour comprendre cela et obtenir une réponse détaillée, vous devez être sûr de connaître les bases du hachage. Droite?

Qu'est-ce que le hachage

Le hachage dans sa forme la plus simple est un moyen de convertir n'importe quelle variable/objet en un code unique après avoir appliqué une formule/un algorithme à leurs propriétés. Une véritable fonction de hachage doit suivre la règle suivante : une fonction de hachage doit renvoyer le même code de hachage chaque fois qu'elle est appliquée à des objets identiques ou égaux. En d’autres termes, deux objets identiques doivent renvoyer tour à tour les mêmes codes de hachage. Vous pouvez en savoir plus à ce sujet ici : Travailler avec la méthode hashCode et égal à Java

Un peu sur la classe d'entrée

Par définition, une carte est « un objet qui stocke des valeurs et des clés par paires ». Assez simple, non ? Donc, il doit y avoir une sorte de mécanisme dans HashMap qui stocke des paires de valeurs et de clés ? Réponse - Oui. HashMapa une classe interne Entryqui ressemble à ceci :

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

Naturellement, la classe Entrya une clé et une valeur stockées comme attributs. La clé est marquée comme finalet nous voyons également deux champs supplémentaires : nextet hash. Nous essaierons de comprendre l’utilité de ces champs au fur et à mesure de l’avancement de l’article.

Que fait la méthode Java put() ?

Avant de plonger dans l'implémentation de la méthode put(), il est très important de comprendre que les instances d'une classe Entrysont stockées dans un tableau. La classe HashMap définit cette variable comme :

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Jetez maintenant un œil au code d’implémentation de la méthodeput() :

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

Voyons cela étape par étape :

• Tout d'abord, nous vérifions si la clé existe. Si la clé n'existe pas ( null), la valeur est placée dans le tableau à la position zéro car le code de hachage de la valeur est null, это – всегда 0.


• À l'étape suivante, la valeur de hachage est calculée à l'aide du code de hachage de la clé obtenu en appelant la méthode hashCode(). Cette valeur de hachage est utilisée pour calculer la position dans le tableau où l'objet sera placé Entry. Les concepteurs du JDK ont supposé qu'une fonction mal écrite hashCode()pouvait renvoyer une valeur de hachage trop élevée ou trop faible. Pour résoudre ce problème, ils ont introduit une autre hash()fonction et y ont transmis la valeur de hachage d'un objet pour que la valeur de hachage corresponde à la taille du tableau.


• La fonction est maintenant appelée indexFor(hash, table.length)pour calculer la position exacte où l'objet sera placé Entry.


• C'est ici que commence la partie principale. Maintenant, sur la base de ce que nous savons : deux objets inégaux peuvent avoir des codes de hachage égaux, nous posons la question : deux objets différents seront-ils placés à la même position dans le tableau [bucket] ? La réponse est LinkedList. Si vous vous en souvenez, la classe Entrya un attribut " next". Cet attribut pointe toujours vers l'objet suivant de la chaîne. C'est exactement le comportement LinkedList.

Ainsi, les objets Entrysont stockés sous la forme LinkedList. Lorsqu'un objet Entrydoit être placé à un emplacement spécifique, HashMap vérifie s'il existe déjà une entrée à cet emplacement. S'il n'y a aucune entrée, alors l'objet est placé à cette position. Toutefois, si un objet se trouve déjà à cette position, l'attribut suivant est vérifié. S'il revient nullet que l'objet actuel Entrydevient le lien suivant dans le fichier LinkedList. Si la variable suivante ne l'est pas null, la procédure est répétée pour la suivante jusqu'à ce qu'elle soit trouvée null. Et si on mettait un autre objet avec une valeur différente mais avec la même clé qu'avant ? Logiquement, cela devrait entraîner le remplacement de l'ancienne valeur. Comment cela peut-il arriver? En général, après avoir déterminé la position d'un objet Entry, lors du déplacement LinkedListvers la position calculée, HashMapil appelle la méthode de comparaison clé pour chaque objet Entry. Tous ces Entryobjets LinkedListpeuvent avoir des codes de hachage similaires, mais la méthode equals()vérifiera la véritable similitude. Cela remplacera uniquement la valeur dans le Entry. Ainsi, HashMap garantit l'unicité de toutes les clés.

Comment fonctionne la méthode Java get() ?

Nous avons maintenant une idée de la façon dont les paires clé-valeur sont stockées dans HashMap. La prochaine grande question est : que se passe-t-il lorsqu'un objet est passé d'un HashMap à une méthode get()? Comment est déterminée la valeur d’un objet ? Nous devrions déjà connaître la réponse, car la manière dont l'unicité d'une clé est déterminée dans la méthode put()a la même logique que celle appliquée par la méthode get(). Une fois qu'il HashMapa déterminé la clé de l'objet passé en argument, il renvoie simplement la valeur du Entry. Si aucune correspondance n’est trouvée, la méthode get()renverra null. Jetons un coup d'œil au code :

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>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;
}

Le code ci - dessus est similaire à la méthode put()jusqu'à présent if (e.hash == hash && ((k = e.key) == key || key.equals(k))). Après cela, il renvoie simplement la valeur de l'objet.

Remarques

• La structure de données à stocker dans un objet Entryest un tableau avec un nom tableet un type Entry.
• Chaque position individuelle du tableau est appelée compartiment car elle peut contenir le premier élément LinkedListdes objets Entry.
• hashCode()La clé est nécessaire pour calculer la position de l'objet Entry.
• equals()La clé est utilisée pour vérifier l'unicité de la clé dans la map( map).
• hashCode()et equals()les valeurs ne sont pas utilisées dans les méthodes get()et set()dans HashMap.
• Le code de hachage pour les clés avec une valeur nullest toujours 0. Et un tel objet Entrysera toujours stocké à la position zéro du tableau.

J'espère avoir correctement exprimé mes pensées dans cet article. Si vous trouvez des erreurs ou avez des questions, veuillez les laisser dans les commentaires. Bon apprentissage!