Detaillierte Analyse der HashMap-Klasse

Bevor wir zu einer ausführlichen Diskussion der Klasse übergehen, konzentrieren wir uns auf die grundlegenden Konzepte im Zusammenhang mit Hash-Tabellen. In diesem Artikel werden keine Methoden zum Arbeiten mit Hash-Mapping erläutert. Nur die Vorgänge Einfügen, Suchen und Löschen werden klar und ausführlich besprochen. Ich denke, es wird nicht schwer sein , die Beschreibung der für HashMap verfügbaren Methoden von demselben Schildt zu lesen. Vielleicht werde ich in Zukunft einen weiteren Artikel über solche Methoden schreiben, aber das ist vorerst fraglich. Im Vergleich zu Java 7 hat die HashMap-Klasse in Java 8 erhebliche Änderungen erfahren (+1000 Codezeilen). Über die Implementierung in Java 7 können Sie hier lesen (aber nicht mehr relevant): habr Eine Hash-Tabelle ist eine Datenstruktur, die die assoziative Array- Schnittstelle (abstraktes Schlüssel-Wert-Modell oder Eintrag) implementiert, die eine sehr schnelle Einfügung und Suche ermöglicht: unabhängig davon Das Einfügen und Suchen (und manchmal Löschen) der Zahlenelemente erfolgt in einer Zeit, die nahe an einer Konstante liegt – O(1). Im Wesentlichen handelt es sich hierbei um ein reguläres Array, bei dem die Position des Elements vom Wert des Elements selbst abhängt. Die Beziehung zwischen dem Wert eines Elements und seiner Position in der Hash-Tabelle wird durch eine Hash-Funktion angegeben. Eine Hash-Funktion nimmt ein Eingabedatenelement, das wir Schlüssel nennen , und erzeugt als Ausgabe eine ganze Zahl, die als Hash-Wert (oder Hash-Code) bekannt ist . Der Hash-Wert bindet dann unseren Schlüssel an einen bestimmten Hash-Tabellenindex. Für die Grundoperationen Einfügen, Suchen und Löschen verwenden wir dieselbe Hash-Funktion, sodass diese Operationen recht schnell ausgeführt werden. Aus diesem Grund ist es wichtig, dass sich die Hash-Funktion konsistent verhält und für dieselben Eingabedaten denselben Index ausgibt. Es ist erwähnenswert, dass der resultierende Hash-Code ein großer numerischer Wert sein kann und das ursprüngliche Array bedingt für nur 16 Elemente ausgelegt ist. Warum nicht ein Array mit einer Milliarde Elementen erstellen, um nur zehn hinzuzufügen? Daher müssen wir diesen Hash-Code irgendwie in Werte von 0 bis 15 umwandeln (wenn die Array-Größe 16 beträgt). Und dafür werden zusätzliche Transformationen verwendet. Deshalb generieren wir einen Index, um die Größe des Arrays zu minimieren. Beispielsweise wurde in HashMap vor Java 8 diese zusätzliche Methode verwendet, um die gewünschte Zelle zu finden:

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

Als Eingabe wurden der als Ergebnis der Arbeit erhaltene Hash-Code hashCode()und die Länge des internen Arrays (Anzahl der Zellen) verwendet. Und es gab das Ergebnis „Hash-Code“ -> bitweises „AND“ -> (Array-Länge – 1) zurück. Die Klasse HashMaperbt von der Klasse AbstractMapund implementiert die folgenden Schnittstellen: Map, Cloneable, Serializable. Die .method ist für die Hash-Funktion in Java verantwortlich hashCode(). Die Standardimplementierung hashCode()gibt einen Wert zurück, der als Identitäts-Hash-Code bezeichnet wird . Selbst wenn eine Klasse überschreibt hashCode(), können Sie immer den ID-Hash des Objekts abrufen, indem Sie aufrufen System.identityHashCode(Object o). Die Standardimplementierung hashCode()in OpenJDK hat nichts mit der Speicheradresse zu tun, wie manchmal angenommen wird. Weitere Details hier: habr In HashMap wird die Hash-Tabelle basierend auf einem Array (oder genauer gesagt dynamisch, da die Tabelle erweitert werden kann) einfach verknüpfter Listen implementiert. Im Wesentlichen erhalten wir als Ergebnis der Methode den Hash-Code des Schlüssels hashCode(), der dann geändert wird (wie wir später betrachten werden), und intern werden die resultierenden Werte mithilfe einer zusätzlichen Methode auf die erforderlichen Zellen verteilt. Array-Elemente (Zellen) werden auch Buckets genannt , die der Speicherung einzelner Knoten dienen. Jeder der Buckets ist eine Sammlung (Liste oder Baum). Ein Knoten ist ein Objekt einer verschachtelten Klasse Node(oder TreeNodein einer Baumstruktur). Tatsächlich befindet sich innerhalb der Array-Zelle LinkedListnur eine einfach verknüpfte Liste oder ein rot-schwarzer Baum, der der Implementierung einer anderen Klasse zugrunde liegt – TreeMap. Die Option mit einem rot-schwarzen Baum kommt nicht so oft vor (wie, was und wo – weiter unten), und diese Struktur ist ziemlich schwer zu verstehen, daher wird der Schwerpunkt auf einem Knoten vom Typ „Knoten“ liegen. Node ist eine verschachtelte Klasse HashMapmit den folgenden Feldern:

• final int hash— der Hash des aktuellen Elements, den wir als Ergebnis des Hashings des Schlüssels erhalten;
• final K key— der Schlüssel des aktuellen Elements. Hier wird das geschrieben, was Sie als erstes Objekt in der Methode angeben put().
• V value— der Wert des aktuellen Elements. Und was Sie als zweites Objekt in der Methode angeben, wird hier geschrieben put();
• Node < K, V> next– Link zum nächsten Knoten innerhalb desselben Warenkorbs. Die Liste ist verbunden, daher benötigt sie einen Link, nicht zum nächsten Knoten, falls vorhanden.

Schauen wir uns nun die Felder der HashMap-Klasse selbst an:

• transient Node < K, V> [] table– die Hash-Tabelle selbst, implementiert auf Basis eines Arrays, zur Speicherung von Schlüssel-Wert-Paaren in Form von Knoten. Hier werden unsere Nodes gespeichert;
• transient int size— Anzahl der Schlüssel-Wert-Paare;
• int threshold— die maximale Anzahl von Elementen, bei deren Erreichen sich die Größe der Hash-Tabelle verdoppelt. Berechnet nach der Formel (Kapazität * Lastfaktor);
• final float loadFactor— Dieser Parameter bestimmt, welchen Auslastungsgrad die aktuelle Hash-Tabelle benötigt, um eine neue Hash-Tabelle zu erstellen, d. h. Sobald die Hash-Tabelle zu 75 % gefüllt ist, wird eine neue Hash-Tabelle erstellt und die aktuellen Elemente werden in diese verschoben (ein kostspieliger Vorgang, da alle Elemente erneut aufbereitet werden müssen);
• transient Set< Map.Entry< K,V>> entrySet- enthält einen Cache entrySet(), mit dem wir iterieren können HashMap.

Und Konstanten:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— Standard-Hash-Tabellenkapazität (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— die maximal mögliche Kapazität der Hash-Tabelle (ungefähr 1 Milliarde);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— Standardlastfaktor;
• static final int TREEIFY_THRESHOLD = 8ist der „Schwellenwert“ der Anzahl der Elemente in einem Bucket, bei dessen Erreichen die interne verknüpfte Liste in eine Baumstruktur (rot-schwarzer Baum) umgewandelt wird.
• static final int UNTREEIFY_THRESHOLD = 6— Wenn die Anzahl der Elemente in einem Korb auf 6 sinkt, erfolgt ein umgekehrter Übergang von einem Baum zu einer verknüpften Liste.
• static final int MIN_TREEIFY_CAPACITY = 64— die Mindestkapazität (Anzahl der Buckets) einer Hash-Tabelle, bei der ein Übergang zu einer Baumstruktur möglich ist. Diese. Wenn die Hash-Tabelle mindestens 64 Buckets enthält und ein Bucket 8 oder mehr Elemente enthält, erfolgt ein Übergang zu einer Baumstruktur.

Klassenkonstruktoren:

1. public HashMap()– erstellt standardmäßig eine Hash-Anzeige: nach Volumen (capacity) = 16und mit Auslastungsfaktor (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)– erstellt eine Hash-Zuordnung, die durch die Elemente einer anderen gegebenen Zuordnung initialisiert wird, mit der anfänglichen Kapazität, die ausreicht, um die Elemente einer anderen Zuordnung aufzunehmen;
3. public HashMap(int initialCapacity)– Erstellt eine Hash-Map mit einer bestimmten Anfangskapazität. Damit HashMap richtig und korrekt funktioniert, muss die Größe des internen Arrays eine Zweierpotenz sein (d. h. 16, 64, 128 usw.);
4. public HashMap(int initialCapacity, float loadFactor)– erstellt eine Hash-Map mit den angegebenen Parametern: Anfangskapazität und Auslastungsfaktor.

Eine Klasse implementiert eine Schnittstelle Mapund erweitert eine Klasse, AbstractMapohne eigene Methoden hinzuzufügen. Eine Hash-Map garantiert nicht die Reihenfolge ihrer Elemente. Daher ist die Reihenfolge, in der Elemente in die Hash-Map eingegeben werden, nicht unbedingt die Reihenfolge, in der sie vom Iterator abgerufen werden. Hinzufügen von Objekten Das Hinzufügen eines Schlüssel-Wert-Paares erfolgt über die put(). Schauen wir uns die Schritte an, die beim Hinzufügen eines Objekts erforderlich sind:

1. Der Hashwert des Schlüssels des eingegebenen Objekts wird berechnet. Der Schlüssel-Hash wird durch eine Methode berechnet static final int hash(Object key), die bereits auf die hashCode()uns bekannte Schlüsselmethode zugreift. Hierzu hashCode()wird entweder eine überschriebene Methode oder deren Standardimplementierung verwendet. Zusätzliche Transformationen in der Methode 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 будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Wieой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша ein Objektа начали вносить коррективы в то, в Wieой бакет попадёт ein Objekt) и, Wie следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

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

   
   i = (n - 1) & hash

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

3. Создается ein Objekt Node.

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

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

   1. Создадим ein Objekt класса HashMap:

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

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

      map.put("KING", 100);

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

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

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

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

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

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

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

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

   5. Gleichzeitig berechnen wir den Index des Buckets, in dem unser Objekt platziert wird, und prüfen, ob darin bereits Elemente vorhanden sind. Wir berechnen:

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

      überprüfen:

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

   6. Da wir als Ergebnis der Prüfung „true“ erhalten (es sind keine Elemente im Bucket vorhanden), wird ein Node-Objekt mit den folgenden Feldern generiert:

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

      Unser generiertes Node-Objekt wird dem Bucket unter Index [4] hinzugefügt:

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

      newNode()ist eine Methode, die einfach ein Objekt der Node-Klasse zurückgibt.

   7. Nach dem Hinzufügen wird geprüft, ob die aktuelle Anzahl der Elemente den Parameter überschreitet threshold:

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

      Bei Überschreitung wird eine Methode aufgerufen, resize()um die Größe der Hash-Tabelle zu erhöhen.

      An diesem Punkt wird die Methode putVal()(bzw. put()) ihre Arbeit abschließen.

      Das Ergebnis lässt sich grafisch wie folgt darstellen:

      Im Allgemeinen sieht das Hinzufügen eines Knotens (Schlüssel-Wert-Paar) zu einer Hash-Tabelle so aus, wenn der gewünschte Bucket leer ist . Versuchen wir nun, ein Element hinzuzufügen, das zu einer Kollision führt (wenn sich mehr als ein Element in einem Bucket befindet).

Ein wenig über Kollisionen Die Situation, in der verschiedene Schlüssel im selben Bucket landen (auch mit unterschiedlichen Hashes), wird als Kollision oder Kollision bezeichnet. Selbst wenn die Hash-Tabelle größer als der Datensatz ist und eine gute Hash-Funktion gewählt wurde, ist dies keine Garantie dafür, dass es nicht zu Kollisionen kommt. Und der Hash-Wert ist auf den Bereich der Int-Werte (ca. 4 Milliarden) beschränkt. Der resultierende neue Wert muss ebenfalls irgendwo geschrieben werden, und dazu müssen Sie bestimmen, wo genau er geschrieben wird. Dies nennt man Konfliktlösung. Es gibt zwei Ansätze:

• externe Verkettung oder Verkettungsmethode (implementiert in HashMap) – d.h. Die Zelle enthält tatsächlich eine Liste (Kette). Und die Liste kann bereits mehrere Werte enthalten (nicht unbedingt mit demselben Hashcode).
• lineare Sondierung oder offene Adressierungsmethode (implementiert in IdentityHashMap) – besteht darin, nach der ersten leeren Zelle nach der Zelle zu suchen, auf die die Hash-Funktion zeigt;

Über Kollisionen können Sie hier lesen: klick

1. Mit dieser Methode put()fügen wir der Hash-Zuordnung ein weiteres Schlüssel-Wert-Paar hinzu:

   map.put("BLAKE", 10);

2. Wir berechnen den „vorläufigen Hash“ – 63281361. Wir modifizieren ihn und als Ergebnis erhalten wir den endgültigen Hash-Code – 63281940.

3. Da die erste Prüfung auf „Leerheit“ nun „false“ zurückgibt (es ist nicht erforderlich, eine Tabelle zu erstellen), berechnen wir sofort den Index des Buckets, in dem unser Objekt platziert wird:

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

4. Der Bucket am angegebenen Index wird auf das Vorhandensein von Elementen überprüft. Da die Bedingung in if ((p = tab[i = (n - 1) & hash]) == null)diesem Fall nicht erfüllt ist (im Bucket befindet sich bereits ein Element), gehen wir zum Block else.

5. Zunächst vergleichen wir das hinzuzufügende Element mit dem ersten Element der verknüpften Liste im Bucket:

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

   При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так Wie ein Objektы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неgleichtства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать Bedeutung у ключа:

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

   В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

6. Игнорируем Zustand (p instanceof TreeNode), так Wie структура в бакете не является древовидной на данном этапе.

7. Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он gleicht null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

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

   Вы можете спросить, а где же проверка на gleichtство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого Element, и так Wie он сейчас gleicht null, можно сделать вывод о том, что в списке только один элемент. И так Wie мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

   Если же при первой итерации указатель не gleicht null, это говорит о том, что в списке Wie минимум два Element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого Element со всеми ключами элементов в списке (способом, описанным в пятом пункте).

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

   Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать Bedeutung у ключа.

   После добавления второго Element наш ein Objekt HashMap графически выглядит так:

   В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

   • проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
   • если ключи одинаковы, заменить текущее Bedeutung новым.
   • иначе связать новый и старый ein Objektы с помощью структуры данных "связный список", указав ссылку на следующий ein Objekt в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

8. После каждой итерации (добавления нового Element) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

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

   До тех пор, пока их количество не станет равно oder больше 7:

   binCount >= TREEIFY_THRESHOLD – 1

   В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

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

   Anstatt zur Baumstruktur zu wechseln, wird eine Methode aufgerufen resize(), um die Hash-Tabelle zu vergrößern und die Elemente neu zu verteilen. treeify()Die verknüpfte Liste wird wiederum TreeNodein einen rot-schwarzen Baum umgewandelt. Die Methode resize()durchläuft alle Elemente des aktuellen Speichers, berechnet deren Indizes neu (unter Berücksichtigung der neuen Größe) und verteilt die Elemente neu in ein neues Array.

   Ohne näher auf die Struktur des Rot-Schwarz-Baums einzugehen, passiert kurz gesagt Folgendes:

   1. Das erste Element der Liste wird als Wurzel des gesamten Baums geschrieben (schwarz):

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

   2. Für andere Elemente:

      Verteile sie je nach Hashwert nach links oder rechts:

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

      Alle linken Kinder müssen kleiner (oder gleich) ihrem Wurzelknoten sein, während alle rechten Kinder größer sein müssen.

   3. Wenn zwei Elemente die gleichen Hashes haben und nicht auf andere Weise verglichen werden können (sie implementieren die Schnittstelle nicht Comparable), unterbrechen wir den Aufbau des Baums und rufen die Methode auf tieBreakOrder(), die wiederum die native Methode verwendet, System.identityHashCode()um einen weltweit eindeutigen Hash-Code zu berechnen .

      Weitere Details hier: Link zum Artikel

   4. Wir überprüfen die Baumelemente (Objekte TreeNode), bis ein untergeordnetes (linkes oder rechtes) Nullelement gefunden wird.

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

   5. Fügen Sie einen untergeordneten Knoten hinzu (links oder rechts, je nach Verzeichnis):

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

   6. Da das Hinzufügen eines neuen Elements das Gleichgewicht des Baums stören kann, rufen wir die Methode zum Neuausgleich auf:

      root = balanceInsertion(root, x);

      Informationen zum Ausgleich des CCH finden Sie hier: habr

   7. Nach dem Ausgleich kann sich das Wurzelelement ändern. Wir beheben dieses Problem, indem wir eine Methode aufrufen, die garantiert, dass der an sie übergebene Root der erste Knoten ist:

      moveRootToFront(tab, root)

      Wie ein rot-schwarzer Baum aufgebaut ist und sich selbst balanciert, können Sie hier deutlich erkennen: Visualisierung

Das ist im Prinzip alles, und nehmen wir anhand eines Beispiels an, dass wir die folgenden Namen als Schlüssel hinzufügen möchten: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. Nehmen wir an, wir haben mindestens 64 Buckets in der Hash-Tabelle und alle diese Elemente haben sich in einem Bucket angesammelt. Strukturell sieht dieser Bucket so aus (Elemente sind nach Hash-Code sortiert): Typ des CCHD: Blick in den Eimer: Elemente abrufen (Wert per Schlüssel abrufen) Der Additionsvorgang ist recht einfach. Der Algorithmus (wenn sich eine verknüpfte Liste im Bucket befindet) kann wie folgt geschrieben werden:

1. Berechnen Sie den Hash-Code des Schlüssels.
2. Berechnen Sie den Bucket-Index.
3. Gehen Sie den Index durch und vergleichen Sie den Schlüssel des ersten Elements mit dem vorhandenen Wert. Wenn sie gleich sind, geben Sie den Wert zurück, andernfalls prüfen Sie, ob das nächste Element vorhanden ist.
4. Wenn das nächste Node-Objekt null ist, wird null zurückgegeben.
5. Wenn das nächste Node-Objekt nicht null ist, gehen Sie zu ihm und wiederholen Sie die ersten drei Schritte, bis das Element gefunden wird oder das nächste Node-Objekt null ist.

Mit der Methode get()erhalten wir den Wert für den Schlüssel „KING“:

map.get("KING");

Im Inneren wird die Methode aufgerufen getNode(int hash, Object key), an die der Schlüssel selbst („KING“) und sein Hash (2306996) übergeben werden, der auf die gleiche Weise wie bei der Operation vorberechnet wird put().

1. Wir überprüfen:

   1. Gibt es überhaupt eine Hash-Tabelle:(tab = table) != null

      Ich möchte Sie daran erinnern, dass beim Erstellen einer HashMap kein Array für die Tabelle im Konstruktor erstellt wird; dies geschieht später in der Methode resize(), die immer aufgerufen wird, wenn das erste Element zur Hash-Tabelle hinzugefügt wird. Wenn der HashMap keine Elemente hinzugefügt wurden, gibt es daher einfach kein internes Array zum Speichern der Elemente.

   2. Wenn der vorherige Ausdruck „true“ zurückgibt, müssen Sie sicherstellen, dass die Länge des internen Arrays größer als 0 ist:(n = tab.length) > 0;

   3. Wenn der vorherige Ausdruck ebenfalls „true“ zurückgibt, gehen Sie zum Bucket am Index (in unserem Fall 4), der zuvor berechnet wurde, und überprüfen Sie ihn auf das Vorhandensein von Elementen:

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

   4. Wir vergleichen den gesuchten Schlüssel mit dem Schlüssel des ersten Elements in der Liste innerhalb des Buckets, da es in den meisten Buckets (nicht überall, wo es Kollisionen gibt) nur ein Element gibt (in unserem Fall). Wie bei der Methode put()werden die Hashes verglichen, und wenn sie übereinstimmen, werden die Schlüssel anhand der Referenz und dann erst anhand verglichen equals().

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

      Da in unserem Fall der Schlüssel „KING“ vor dem Schlüssel „BLAKE“ steht (innerhalb einer verknüpften Liste werden neue Elemente am Ende hinzugefügt, und KING wurde zuerst hinzugefügt), stoppen wir an dieser Stelle und geben das erste Objekt von zurück Geben Sie Node zur get()-Methode ein, die ihm ein Feld mit dem Wert (100) „schnappt“:

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

2. Wenn sich mehr als ein Element im Bucket befindet, gilt Folgendes:

   1. Wenn es sich bei dem Bucket um eine verknüpfte Liste handelt, gehen wir die Liste durch jedes der Elemente in einer Schleife durch, do – whilebis eine Übereinstimmung gefunden wird:

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

   2. Wenn es sich bei dem Bucket um eine Baumstruktur handelt, wird zusätzlich die Methode aufgerufen getTreeNode(), die wiederum die Methode verwendet, um den erforderlichen Schlüssel zu finden find(). Wir führen eine Baumsuche durch – die Hashes werden verglichen und der zu durchsuchende linke oder rechte Wurzelknoten wird bestimmt. Wenn die Schlüssel gleich sind (durch Referenz oder durch equals), wird dieser Knoten zurückgegeben. Wenn der linke oder rechte untergeordnete Knoten null ist, vergleichen wir zusätzlich die Schlüssel mit „compareTo“ (sofern die Schlüssel die Schnittstelle implementieren Comparable), andernfalls führen wir eine rekursive Suche durch den Baum (rechter oder linker Teilbaum) durch, bis eine Übereinstimmung gefunden wird.

Entfernen von Objekten aus einer HashMap Da der Platz im Artikel knapp wird, werde ich kurz beschreiben, wie das Löschen per Schlüssel erfolgt. Der Algorithmus ist sehr ähnlich:

• Gehen Sie zum gewünschten Bucket (er ist wiederum vorberechnet);

• Wenn sich nur ein Objekt im Bucket befindet (wir überprüfen seinen Nullzeiger), vergleichen wir Hashes, Links und equals(wenn die Hashes plötzlich nicht gleich sind). Eine Übereinstimmung gefunden? Großartig, das ist unser Schlüssel – löschen Sie ihn (=null) und geben Sie den Wert dieses Schlüssels zurück.

• Wenn sich mehr als ein Element im Bucket befindet, überprüfen wir jedes Element in einer Schleife, bis wir das Element finden oder das Ende der Liste erreichen.

• Wenn das Element nicht gefunden wurde, geben wir null zurück.

In der Situation mit einem Baum gibt es eine ziemlich knifflige Implementierung, von der man besser nichts wissen und ruhig schlafen sollte (in der Beschreibung der Methode heißt es sogar, dass die Implementierung komplizierter ist als bei einem regulären Löschvorgang in einem Rot-Schwarz). Baum). Darüber hinaus kann die Anzahl der Knoten in einem Bucket beim Löschen auf 6 zurückgesetzt werden, und der Baum wird dann wieder in eine verknüpfte Liste umgewandelt. Wenn Sie kein Entwickler mit langjähriger Erfahrung sind, ist es überhaupt nicht notwendig, dies zu wissen und zu verstehen (und einfach nicht notwendig).