Analyse détaillée de la classe HashMap

Avant de passer à une discussion détaillée du cours, concentrons-nous sur les concepts de base associés aux tables de hachage. Cet article ne discutera pas des méthodes permettant de travailler avec le mappage de hachage. Seules les opérations d'insertion, de recherche et de suppression seront abordées de manière claire et détaillée. Je pense qu'il ne sera pas difficile de lire la description des méthodes disponibles pour HashMap du même Schildt. Peut-être qu'à l'avenir j'écrirai un autre article consacré à de telles méthodes, mais pour l'instant cela est incertain. Par rapport à Java 7, la classe HashMap de Java 8 a subi des changements importants (+1000 lignes de code). Vous pouvez en savoir plus sur l'implémentation dans Java 7 ici (mais ce n'est plus pertinent) : habr Une table de hachage est une structure de données qui implémente l' interface de tableau associatif (modèle abstrait clé-valeur ou entrée), qui permet une insertion et une recherche très rapides : peu importe L'insertion et la recherche (et parfois la suppression) des éléments numériques sont effectuées dans un temps proche d'une constante - O(1). Il s’agit essentiellement d’un tableau régulier dans lequel l’emplacement de l’élément dépend de la valeur de l’élément lui-même. La relation entre la valeur d'un élément et sa position dans la table de hachage est spécifiée par une fonction de hachage. Une fonction de hachage prend une donnée d'entrée, que nous appelons une clé , et en sortie, elle produit un entier appelé valeur de hachage (ou code de hachage) . La valeur de hachage lie ensuite notre clé à un index de table de hachage spécifique. Pour les opérations de base : insertion, recherche et suppression, nous utilisons la même fonction de hachage, ces opérations sont donc effectuées assez rapidement. Pour cette raison, il est important que la fonction de hachage se comporte de manière cohérente et génère le même index pour les mêmes données d'entrée. Il convient de noter que le code de hachage résultant peut être une valeur numérique énorme et que le tableau d'origine est conçu de manière conditionnelle pour seulement 16 éléments. Pourquoi ne pas créer un tableau avec un milliard d’éléments afin d’en ajouter seulement dix ? Par conséquent, nous devons en quelque sorte transformer ce code de hachage en valeurs de 0 à 15 (si la taille du tableau est de 16). Et pour cela, des transformations supplémentaires sont utilisées. Nous générons donc un index pour minimiser la taille du tableau. Par exemple, dans HashMap avant Java 8, cette méthode supplémentaire était utilisée pour trouver la cellule souhaitée :

static int indexFor(int h, int length) {
        return h & (length-1);
}

En entrée, il a pris le code de hachage obtenu grâce au travail hashCode()et la longueur du tableau interne (nombre de cellules). Et il a renvoyé le résultat « code de hachage » -> « ET » au niveau du bit -> (longueur du tableau – 1). La classe HashMaphérite de la classe AbstractMapet implémente les interfaces suivantes : Map, Cloneable, Serializable. La .method est responsable de la fonction de hachage en Java hashCode(). L'implémentation par défaut hashCode()renvoie une valeur appelée code de hachage d'identité . Même si une classe remplace hashCode(), vous pouvez toujours obtenir le hachage de l'ID de l'objet en appelant System.identityHashCode(Object o). L'implémentation par défaut hashCode()dans OpenJDK n'a rien à voir avec l'adresse mémoire, comme on le croit parfois. Plus de détails ici : habr Dans HashMap , la table de hachage est implémentée sur la base d'un tableau (ou, plus précisément, dynamique, puisque la table peut s'étendre) de listes à chaînage unique. Essentiellement, nous obtenons le code de hachage de la clé grâce à la méthode hashCode(), qui est ensuite modifié (comme nous le verrons plus tard), et en interne, à l'aide d'une méthode supplémentaire, les valeurs résultantes sont distribuées aux cellules requises. Les éléments du tableau (cellules) sont également appelés compartiments et sont utilisés pour stocker des nœuds individuels. Chacun des buckets est une collection (liste ou arborescence). Un nœud est un objet d'une classe imbriquée Node(ou TreeNodedans une arborescence). En fait, à l'intérieur de la cellule du tableau se trouve LinkedListuniquement une liste à chaînage unique, ou un arbre rouge-noir, qui sous-tend l'implémentation d'une autre classe - TreeMap. L'option avec un arbre rouge-noir ne se pose pas si souvent (comment, quoi et où - ci-dessous), et cette structure est assez difficile à comprendre, l'accent sera donc mis sur un nœud de type Node. Node est une classe imbriquée à l'intérieur HashMapde laquelle se trouvent les champs suivants :

• final int hash— le hachage de l'élément courant, que nous obtenons en hachant la clé ;
• final K key— la clé de l'élément courant. C'est ici que ce que vous spécifiez comme premier objet de la méthode est écrit put();
• V value— la valeur de l'élément actuel. Et ce que vous spécifiez comme deuxième objet dans la méthode est écrit ici put();
• Node < K, V> next— lien vers le nœud suivant dans le même panier. La liste est connectée, elle a donc besoin d'un lien et non vers le nœud suivant, s'il y en a un.

Regardons maintenant les champs de la classe HashMap elle-même :

• transient Node < K, V> [] table– la table de hachage elle-même, implémentée sur la base d'un tableau, pour stocker des paires clé-valeur sous forme de nœuds. C'est là que nos nœuds sont stockés ;
• transient int size— nombre de paires clé-valeur ;
• int threshold— le nombre maximum d'éléments, après quoi la taille de la table de hachage double. Calculé à l'aide de la formule (capacité * loadFactor) ;
• final float loadFactor— ce paramètre détermine à quel degré de charge la table de hachage actuelle a besoin pour créer une nouvelle table de hachage, c'est-à-dire dès que la table de hachage est remplie à 75%, une nouvelle table de hachage sera créée et les éléments actuels y seront déplacés (opération coûteuse, puisqu'il faut rehacher tous les éléments) ;
• transient Set< Map.Entry< K,V>> entrySet- contient un fichier mis en cache entrySet()avec lequel nous pouvons itérer HashMap.

Et des constantes :

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— capacité de la table de hachage par défaut (16) ;
• static final int MAXIMUM_CAPACITY = 1 << 30— la capacité maximale possible de la table de hachage (environ 1 milliard) ;
• static final float DEFAULT_LOAD_FACTOR = 0.75f— facteur de charge par défaut ;
• static final int TREEIFY_THRESHOLD = 8est le « seuil » du nombre d'éléments dans un compartiment, une fois atteint, la liste chaînée interne sera convertie en une structure arborescente (arbre rouge-noir).
• static final int UNTREEIFY_THRESHOLD = 6— si le nombre d'éléments dans un panier diminue jusqu'à 6, alors une transition inverse d'un arbre vers une liste chaînée se produira ;
• static final int MIN_TREEIFY_CAPACITY = 64— la capacité minimale (nombre de buckets) d'une table de hachage à laquelle une transition vers une structure arborescente est possible. Ceux. S'il y a au moins 64 compartiments dans la table de hachage et 8 éléments ou plus dans un compartiment, une transition vers une structure arborescente se produira.

Constructeurs de classes :

1. public HashMap()— crée un affichage de hachage par défaut : par volume (capacity) = 16et avec facteur de charge (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— crée un mappage de hachage initialisé par les éléments d'un autre mappage donné avec la capacité initiale suffisante pour accueillir les éléments d'un autre mappage ;
3. public HashMap(int initialCapacity)— crée une carte de hachage avec une capacité initiale donnée. Pour que HashMap fonctionne correctement et correctement, la taille du tableau interne doit être une puissance de deux (c'est-à-dire 16, 64, 128, etc.) ;
4. public HashMap(int initialCapacity, float loadFactor)— crée une carte de hachage avec les paramètres spécifiés : capacité initiale et facteur de charge.

Une classe implémente une interface Mapet étend une classe AbstractMapsans ajouter ses propres méthodes. Une carte de hachage ne garantit pas l'ordre de ses éléments. Par conséquent, l’ordre dans lequel les éléments sont saisis dans la carte de hachage n’est pas nécessairement l’ordre dans lequel ils sont récupérés par l’itérateur. Ajout d'objets L'ajout d'une paire clé-valeur se fait à l'aide du put(). Examinons les étapes à suivre lors de l'ajout d'un objet :

1. La valeur de hachage de la clé de l'objet saisi est calculée. Le hachage de clé est calculé par une méthode static final int hash(Object key)qui accède déjà à la hashCode()méthode de clé que nous connaissons. Pour ce faire, soit une méthode surchargée hashCode(), soit son implémentation par défaut est utilisée. Transformations supplémentaires dans la méthode hash():

   static final int hash(Object key) {
           int h;
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

   Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-codeов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Howой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша an object начали вносить коррективы в то, в Howой бакет попадёт an object) и, How следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

   
   i = (n - 1) & hash

   где n – длина массива.

3. Создается an object Node.

4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

   Теперь к очень подробному примеру.

   1. Создадим an object класса HashMap:

      HashMap < String, Integer> map = new HashMap<>();

   2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-meaning»:

      map.put("KING", 100);

      В этот момент внутри вызывается метод putVal().

   3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью

      System.out.println("KING".hashCode());

      Полученный хеш-code модифицируется по формуле: (хеш-code) ^ (хеш-code>>> 16), и в результате получаем окончательный хеш-code – 2306996.

   4. Проверяем таблицу на «пустоту»:

      if ((tab = table) == null || (n = tab.length) == 0)

      где [] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Так How проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса ниHowой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении element. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.

   5. Одновременно вычисляем индекс бакета, куда будет помещен наш an object, и проверяем, а есть ли уже в нем элементы. Вычисляем:

      
      i = (n - 1) & hash
      i = (16 - 1) & 2306996
      i = 4

      проверяем:

      
      if ((p = tab[i = (n - 1) & hash]) == null)

   6. Так How в результате проверки мы получим true (в бакете элементов нет), будет сгенерирован an object Node со следующими полями:

      
      {
      int hash = 2306996 — сгенерированный хеш-code
      String key = {"KING"} — ключ
      Integer value = 100 — meaning
      Node next = null — link на следующий узел
      }

      Наш сформированный an object Node будет добавлен в бакет под индексом [4]:

      tab[i] = newNode(hash, key, value, null);
      tab[4] = newNode(2306996, “KING”, 100, null);

      newNode() — это метод, который просто возвращает an object класса Node.

   7. После добавления будет произведена проверка не превышает ли текущее количество элементов параметр threshold:

      if (++size > threshold)
          resize();

      Если превышает, тогда будет вызван метод resize() для увеличения размера хеш-таблицы.

      На этом метод putVal() (соответственно и put()) завершит свою работу.

      Графически полученный результат изобразить можно так:

      Так в общем случае выглядит добавление Node (пара «ключ-meaning») в хеш-таблицу, если нужный бакет оказывается пуст. Теперь попробуем добавить такой элемент, который приведет к коллизии (когда в одном бакете оказывается более одного element).

Un peu sur les collisions La situation dans laquelle différentes clés se retrouvent dans le même compartiment (même avec des hachages différents) est appelée collision ou collision. Même si la table de hachage est plus grande que l'ensemble de données et qu'une bonne fonction de hachage a été choisie, cela ne garantit pas qu'il n'y aura pas de collisions. Et la valeur de hachage est limitée à la plage de valeurs int (environ 4 milliards). La nouvelle valeur résultante doit également être écrite quelque part, et pour cela, vous devez déterminer où exactement elle sera écrite. C’est ce qu’on appelle la résolution des conflits. Il existe deux approches :

• chaînage externe ou méthode de chaînage (implémentée dans HashMap) - c'est-à-dire la cellule contient en fait une liste (chaîne). Et la liste peut déjà contenir plusieurs valeurs (pas forcément avec le même hash code).
• méthode de sondage linéaire ou d'adressage ouvert (implémentée dans IdentityHashMap) - consiste à rechercher la première cellule vide après celle pointée par la fonction de hachage ;

Vous pouvez en savoir plus sur les collisions ici : cliquez sur

1. En utilisant la méthode, put()nous ajouterons une autre paire clé-valeur au mappage de hachage :

   map.put("BLAKE", 10);

2. Nous calculons le « hachage préliminaire » – 63281361. Nous le modifions et nous obtenons ainsi le code de hachage final – 63281940.

3. Puisque la première vérification du « vide » retournera désormais false (il n'est pas nécessaire de créer une table), nous calculons immédiatement l'index du bucket où sera placé notre objet :

   
   i = (n - 1) & hash
   i = (16 - 1) & 63281940
   i = 4

4. Le bucket à l'index spécifié est vérifié pour la présence d'éléments, et comme la condition if ((p = tab[i = (n - 1) & hash]) == null)n'est pas remplie dans ce cas (il y a déjà un élément dans le bucket), alors nous passons au bloc else.

5. Tout d'abord, nous comparons l'élément ajouté avec le premier élément de la liste chaînée à l'intérieur du bucket :

   (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

   Lors de la vérification, les hachages de clés sont d'abord comparés. Si cette "partie" (p.hash == hash)renvoie false, alors le reste de la condition est ignoré ( &&) puisque les objets sont garantis différents. Sinon, les clés sont ensuite comparées par référence (==) et en cas d'inégalité, les clés sont comparées selon la méthode equals(). Les comparaisons sont faites dans cet ordre dans un souci de performance. Si les trois expressions renvoient vrai, cela signifie que les clés sont égales et que le nouvel élément sera écrit dans une variable supplémentaire afin d'écraser ultérieurement la valeur de la clé :

   if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
         e.value = value;
         afterNodeAccess(e);
          return oldValue;
    }

   En comparant les clés, nous obtenons déjà faux dès la première étape (hachages différents).

6. Nous ignorons la condition ( p instanceof TreeNode) puisque la structure dans le bucket n'est pas arborescente à ce stade.

7. Ensuite, nous entrons dans une boucle for, où dans un compartiment nous vérifions les éléments pour un pointeur vers l'élément suivant next, et s'il est nul (ce qui signifie que l'élément de la liste est le dernier et le seul), nous ajoutons un nouveau Node élément à la fin de la liste :

   if ((e = p.next) == null){
   	p.next = newNode(hash, key, value, null)
   ... };

   Vous vous demandez peut-être où se trouve le contrôle clé de l’égalité ? Nous ne pouvons pas simplement ajouter un nouvel élément. Cela a donc déjà été mis en œuvre au préalable au paragraphe (5). Grâce à cela, on peut désormais simplement vérifier le pointeur de cet élément, et comme il est désormais nul, on peut conclure qu'il n'y a qu'un seul élément dans la liste. Et comme nous avons déjà vérifié leurs clés, nous pouvons ajouter un nouvel élément en toute sécurité.

   Si lors de la première itération le pointeur n'est pas nul, cela indique qu'il y a au moins deux éléments dans la liste, donc dans ce cas on passe à la condition suivante et on compare la clé de l'élément en cours d'ajout avec toutes les clés de la éléments de la liste (de la manière décrite au cinquième paragraphe).

   if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))

   Si une correspondance est trouvée lors de la comparaison des clés, le nouvel élément sera écrit dans une variable supplémentaire afin d'écraser ultérieurement la valeur de la clé.

   Après avoir ajouté le deuxième élément, notre objet HashMap ressemble graphiquement à ceci :

   En conséquence, l'ajout d'éléments lors d'une collision (au sein d'un même bucket) ressemble à ceci :

   • Nous vérifions à l'aide des méthodes hashCode()et equals()que les deux clés sont identiques.
   • si les clés sont les mêmes, remplacez la valeur actuelle par la nouvelle.
   • sinon, connectez les nouveaux et les anciens objets à l'aide d'une structure de données « liste chaînée », indiquant un lien vers l'objet suivant dans l'objet actuel et stockez les deux sous l'index souhaité ; ou passer à une arborescence

8. Après chaque itération (ajout d'un nouvel élément), la boucle for augmente le compteur, qui est responsable du nombre d'éléments dans le bucket :

   for (int binCount = 0; ; ++binCount)

   Jusqu'à ce que leur nombre devienne égal ou supérieur à 7 :

   binCount >= TREEIFY_THRESHOLD – 1

   Dans ce cas, une méthode sera appelée treeifyBin()treeify()pour construire directement l’arborescence. Cependant, si le nombre de buckets dans la table de hachage actuelle est inférieur à 64 :

   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

   Au lieu d'aller dans l'arborescence, une méthode sera appelée resize()pour augmenter la taille de la table de hachage, redistribuant ainsi les éléments. treeify()à son tour, la liste chaînée des TreeNodeconvertis en un arbre rouge-noir. La méthode resize()parcourt tous les éléments du stockage actuel, recalcule leurs indices (en tenant compte de la nouvelle taille) et redistribue les éléments dans un nouveau tableau.

   En bref, sans entrer dans les détails de la structure de l'arbre rouge-noir, il se passe ce qui suit :

   1. Le premier élément de la liste est écrit comme la racine de l'arbre entier (en noir) :

      if (root == null) {
          x.parent = null;
          x.red = false;
          root = x;
      }

   2. Pour les autres éléments :

      répartissez-les vers la gauche ou la droite en fonction de la valeur de hachage :

      if ((ph = p.hash) > h)
          dir = -1;
      else if (ph < h)
          dir = 1;

      Tous les enfants de gauche doivent être inférieurs (ou égaux) à leur nœud racine, tandis que tous les enfants de droite doivent être supérieurs.

   3. Si deux éléments ont les mêmes hachages et ne peuvent être comparés d'aucune autre manière (ils n'implémentent pas l'interface Comparable), nous interrompons la construction de l'arbre et appelons la méthode tieBreakOrder(), qui à son tour utilise la méthode native System.identityHashCode()pour calculer un code de hachage globalement unique. .

      Plus de détails ici : lien vers l'article

   4. Nous vérifions les éléments de l'arborescence (objets TreeNode) jusqu'à ce qu'un élément zéro enfant (gauche ou droit) soit trouvé.

      if ((p = (dir <= 0) ? p.left : p.right) == null)

   5. Ajoutez un nœud enfant (gauche ou droite selon le répertoire) :

      x.parent = xp;
      if (dir <= 0)
          xp.left = x;
      else
          xp.right = x;

   6. Puisque l’ajout d’un nouvel élément peut perturber l’équilibre de l’arbre, nous appelons la méthode de rééquilibrage :

      root = balanceInsertion(root, x);

      Vous pouvez en savoir plus sur l'équilibrage du CCH ici : habr

   7. Après équilibrage, l'élément racine peut changer. Nous résolvons ce problème en appelant une méthode qui garantit que la racine qui lui est transmise sera le premier nœud :

      moveRootToFront(tab, root)

      Vous pouvez clairement voir comment un arbre rouge-noir est construit et s'auto-équilibre ici : visualisation

C'est tout, en principe, et à l'aide d'un exemple, supposons que nous souhaitions ajouter les noms suivants comme clés : KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Et disons que nous avons au moins 64 buckets dans la table de hachage et que tous ces éléments se sont accumulés dans un seul bucket. Structurellement, ce compartiment ressemblera à ceci (les éléments sont triés par code de hachage) : Type de CCHD : Vue à l'intérieur du seau : Récupération d'éléments (récupération d'une valeur par clé) Concernant l'opération d'ajout, c'est assez simple. L'algorithme (lorsqu'il y a une liste chaînée dans le bucket) peut s'écrire comme ceci :

1. Calculez le code de hachage de la clé.
2. Calculez l’indice du bucket.
3. Parcourez l'index et comparez la clé du premier élément avec la valeur existante. S'ils sont égaux, renvoyez la valeur, sinon recherchez l'élément suivant, s'il existe.
4. Si le prochain objet Node est nul, renvoie null.
5. Si l'objet Node 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 Node suivant soit nul.

En utilisant la méthode, get()nous obtenons la valeur de la clé « KING » :

map.get("KING");

À l'intérieur, la méthode est appelée getNode(int hash, Object key), à laquelle sont transmises la clé elle-même (« KING ») et son hachage (2306996), qui est pré-calculé de la même manière que lors de l'opération put().

1. Nous vérifions:

   1. une table de hachage existe-t-elle :(tab = table) != null

      Je vous rappelle que lors de la création d'un HashMap, un tableau pour la table n'est pas créé dans le constructeur ; cela se produit plus tard dans la méthode resize(), qui est toujours appelée lors de l'ajout du premier élément à la table de hachage. Par conséquent, si aucun élément n’a été ajouté au HashMap, il n’y a tout simplement pas de tableau interne pour stocker les éléments.

   2. si l'expression précédente renvoie vrai, vous devez vous assurer que la longueur du tableau interne est supérieure à 0 :(n = tab.length) > 0;

   3. si l'expression précédente renvoie également vrai, accédez au bucket à l'index (dans notre cas 4), qui a été précédemment calculé, et vérifiez la présence d'éléments :

      (first = tab[(n - 1) & hash]) != null)

   4. Nous comparons la clé que nous recherchons avec la clé du premier élément de la liste à l'intérieur du bucket, car dans la plupart des buckets, il n'y aura (pas partout où nous avons des collisions) un seul élément (notre cas). Comme dans le cas de la méthode put(), les hachages sont comparés, et s'ils correspondent, les clés sont comparées par référence, et ensuite seulement par equals().

      if (first.hash == hash && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))

      Puisque dans notre cas, la clé « KING » précédera la clé « BLAKE » (dans une liste chaînée, de nouveaux éléments sont ajoutés à la fin, et KING a été ajouté en premier), nous nous arrêterons à ce stade et renverrons le premier objet de tapez Node à la méthode get(), qui lui « arrache » un champ de valeur (100) :

      return (e = getNode(hash(key), key)) == null ? null : e.value;

2. S'il y a plus d'un élément à l'intérieur du bucket, alors :

   1. si le bucket est une liste chaînée, nous parcourons la liste en passant par chacun des éléments dans une boucle do – whilejusqu'à ce qu'une correspondance soit trouvée :

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

   2. si le compartiment est une structure arborescente, la méthode est également appelée getTreeNode(), qui à son tour utilise la méthode pour trouver la clé requise find(). Nous effectuons une recherche arborescente - les hachages sont comparés et le nœud racine gauche ou droit à rechercher est déterminé. Si les clés sont égales (par référence ou par equals), renvoyez ce nœud. Si les nœuds enfants gauche ou droit sont nuls, nous comparons en outre les clés à l'aide de compareTo (si les clés implémentent l'interface Comparable), sinon nous effectuons une recherche récursive dans l'arborescence (sous-arbre droit ou gauche) jusqu'à ce qu'une correspondance soit trouvée.

Supprimer des objets d'un HashMap Puisque l'espace dans l'article vient à manquer, je vais décrire brièvement comment la suppression se produit par clé. L'algorithme est très similaire :

• aller dans le bucket souhaité (encore une fois, il est pré-calculé) ;

• s'il n'y a qu'un seul objet dans le bucket (on vérifie son pointeur nul) on compare les hachages, les liens et equals(si du coup les hachages ne sont pas égaux). Vous avez trouvé une correspondance ? Super, c'est notre clé - supprimez-la (=null) et renvoyez la valeur de cette clé.

• s'il y a plus d'un élément dans le bucket, nous vérifions chaque élément dans une boucle jusqu'à ce que nous trouvions l'élément ou atteignions la fin de la liste.

• si l'élément n'a pas été trouvé, nous renvoyons null.

Dans le cas d'un arbre, il existe une implémentation assez délicate, qu'il vaut mieux ne pas connaître et dormir sur ses deux oreilles (la description de la méthode dit même que l'implémentation est plus compliquée que dans une opération de suppression ordinaire dans un rouge-noir arbre). De plus, une fois supprimé, le nombre de nœuds dans un compartiment peut revenir à 6, puis l'arborescence sera reconstruite en une liste chaînée. Si vous n'êtes pas un développeur avec de nombreuses années d'expérience, il n'est pas du tout nécessaire de le savoir et de le comprendre (et tout simplement pas nécessaire).