Szczegółowa analiza klasy HashMap

Zanim przejdziemy do szczegółowego omówienia zajęć, skupmy się na podstawowych pojęciach związanych z tablicami skrótów. W tym artykule nie zostaną omówione metody pracy z mapowaniem skrótów. Jasno i szczegółowo zostaną omówione jedynie operacje wstawiania, wyszukiwania i usuwania. Myślę, że nie będzie trudno przeczytać opis metod dostępnych dla HashMap od tego samego Schildta. Być może w przyszłości napiszę kolejny artykuł poświęcony takim metodom, ale na razie jest to kwestią sporną. W porównaniu z Javą 7, klasa HashMap w Javie 8 uległa znaczącym zmianom (+1000 linii kodu). O implementacji w Javie 7 możesz przeczytać tutaj (ale to już nieaktualne): habr Tablica skrótów to struktura danych, która implementuje interfejs tablicy asocjacyjnej (abstrakcyjny model klucz-wartość lub wpis), który zapewnia bardzo szybkie wstawianie i wyszukiwanie: niezależnie wstawiania i wyszukiwania (a czasami usuwania) elementów liczbowych dokonuje się w czasie zbliżonym do stałego - O(1). Zasadniczo jest to zwykła tablica, w której położenie elementu zależy od wartości samego elementu. Zależność pomiędzy wartością elementu a jego pozycją w tablicy mieszającej jest określana za pomocą funkcji mieszającej. Funkcja skrótu pobiera część danych wejściowych, którą nazywamy kluczem , a na wyjściu generuje liczbę całkowitą znaną jako wartość skrótu (lub kod skrótu) . Wartość skrótu wiąże następnie nasz klucz z określonym indeksem tablicy skrótów. Do podstawowych operacji: wstawiania, wyszukiwania i usuwania używamy tej samej funkcji skrótu, więc operacje te wykonujemy dość szybko. Z tego powodu ważne jest, aby funkcja mieszająca zachowywała się spójnie i wyświetlała ten sam indeks dla tych samych danych wejściowych. Warto zauważyć, że powstały kod skrótu może mieć ogromną wartość liczbową, a oryginalna tablica jest warunkowo zaprojektowana tylko na 16 elementów. Dlaczego nie utworzyć tablicy składającej się z miliarda elementów, aby dodać tylko dziesięć? Dlatego musimy jakoś przekształcić ten kod skrótu na wartości od 0 do 15 (jeśli rozmiar tablicy wynosi 16). W tym celu stosuje się dodatkowe przekształcenia. Generujemy więc indeks, aby zminimalizować rozmiar tablicy. Na przykład w HashMap przed wersją Java 8 do znalezienia żądanej komórki zastosowano tę dodatkową metodę:

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

Jako dane wejściowe przyjmował uzyskany w wyniku pracy kod skrótu hashCode()oraz długość tablicy wewnętrznej (liczba komórek). I zwrócił wynik „kod skrótu” -> bitowo „AND” -> (długość tablicy – ​​1). Klasa HashMapdziedziczy po klasie AbstractMapi implementuje następujące interfejsy: Map, Cloneable, Serializable. Metoda .method jest odpowiedzialna za funkcję skrótu w Javie hashCode(). Domyślna implementacja hashCode()zwraca wartość zwaną kodem skrótu tożsamości . Nawet jeśli klasa zastąpi hashCode(), zawsze możesz uzyskać skrót identyfikatora obiektu, wywołując System.identityHashCode(Object o). Domyślna implementacja hashCode()w OpenJDK nie ma nic wspólnego z adresem pamięci, jak się czasem uważa. Więcej szczegółów tutaj: habr W HashMap tablica mieszająca jest zaimplementowana w oparciu o tablicę (a dokładniej dynamiczną, ponieważ tabela może się rozszerzać) pojedynczo połączonych list. Zasadniczo kod skrótu klucza uzyskujemy w wyniku metody hashCode(), który jest następnie modyfikowany (o czym rozważymy później), a wewnętrznie, za pomocą dodatkowej metody, powstałe wartości są dystrybuowane do wymaganych komórek. Elementy tablicy (komórki) nazywane są także zasobnikami , które służą do przechowywania poszczególnych węzłów. Każdy segment jest kolekcją (listą lub drzewem). Węzeł jest obiektem klasy zagnieżdżonej Node(lub TreeNodestruktury drzewa). W rzeczywistości wewnątrz komórki tablicy znajduje się LinkedListtylko pojedynczo połączona lista, czyli czerwono-czarne drzewo, które leży u podstaw implementacji innej klasy - TreeMap. Opcja z czerwono-czarnym drzewem nie pojawia się tak często (jak, co i gdzie - poniżej), a ta struktura jest dość trudna do zrozumienia, dlatego nacisk zostanie położony na węzeł typu Node. Node to zagnieżdżona klasa HashMap, w której znajdują się następujące pola:

• final int hash— hash bieżącego elementu, który otrzymamy w wyniku mieszania klucza;
• final K key— klucz bieżącego elementu. W tym miejscu zapisywane jest to, co określisz jako pierwszy obiekt metody put();
• V value— wartość bieżącego elementu. Tutaj zostanie zapisane to, co określisz jako drugi obiekt w metodzie put();
• Node < K, V> next— link do następnego węzła w tym samym koszyku. Lista jest połączona, więc potrzebuje linku, a nie do następnego węzła, jeśli taki istnieje.

Przyjrzyjmy się teraz polom samej klasy HashMap:

• transient Node < K, V> [] table– sama tablica mieszająca, zaimplementowana w oparciu o tablicę, służąca do przechowywania par klucz-wartość w postaci węzłów. Tutaj przechowywane są nasze węzły;
• transient int size— liczba par klucz-wartość;
• int threshold— maksymalna liczba elementów, po osiągnięciu której rozmiar tablicy skrótów ulega podwojeniu. Obliczane przy użyciu wzoru (pojemność * współczynnik obciążenia);
• final float loadFactor— parametr ten określa, jakiego stopnia obciążenia potrzebuje bieżąca tablica mieszająca, aby utworzyć nową tablicę mieszającą, tj. gdy tylko tabela mieszająca zostanie zapełniona w 75%, zostanie utworzona nowa tablica mieszająca i przeniesione do niej obecne elementy (operacja kosztowna, ponieważ wszystkie elementy muszą zostać ponownie przemieszane);
• transient Set< Map.Entry< K,V>> entrySet- zawiera pamięć podręczną entrySet(), za pomocą której możemy iterować HashMap.

I stałe:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— domyślna pojemność tablicy mieszającej (16);
• static final int MAXIMUM_CAPACITY = 1 << 30— maksymalna możliwa pojemność tablicy skrótów (około 1 miliarda);
• static final float DEFAULT_LOAD_FACTOR = 0.75f— domyślny współczynnik obciążenia;
• static final int TREEIFY_THRESHOLD = 8to „próg” liczby elementów w jednym zasobniku, po osiągnięciu którego wewnętrzna lista linkowana zostanie przekształcona w strukturę drzewiastą (drzewo czerwono-czarne).
• static final int UNTREEIFY_THRESHOLD = 6— jeżeli liczba elementów w jednym koszyku spadnie do 6, wówczas nastąpi odwrotne przejście z drzewa do listy połączonej;
• static final int MIN_TREEIFY_CAPACITY = 64— minimalna pojemność (liczba segmentów) tablicy mieszającej, przy której możliwe jest przejście do struktury drzewiastej. Te. Jeśli w tabeli mieszającej znajdują się co najmniej 64 zasobniki, a w jednym zasobniku znajduje się 8 lub więcej elementów, wówczas nastąpi przejście do struktury drzewiastej.

Konstruktorzy klas:

1. public HashMap()— domyślnie tworzy wyświetlacz skrótu: według objętości (capacity) = 16i ze współczynnikiem obciążenia (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— tworzy mapowanie skrótu inicjowane przez elementy innego danego mapowania o początkowej pojemności wystarczającej do pomieszczenia elementów innego mapowania;
3. public HashMap(int initialCapacity)— tworzy mapę skrótów o zadanej pojemności początkowej. Aby HashMap działał poprawnie, rozmiar tablicy wewnętrznej musi być potęgą dwójki (tj. 16, 64, 128 itd.);
4. public HashMap(int initialCapacity, float loadFactor)— tworzy mapę skrótów z określonymi parametrami: początkową pojemnością i współczynnikiem obciążenia.

Klasa implementuje interfejs Mapi rozszerza klasę AbstractMapbez dodawania własnych metod. Mapa mieszająca nie gwarantuje kolejności jej elementów. Dlatego kolejność wprowadzania elementów do mapy skrótów niekoniecznie jest kolejnością, w jakiej są one pobierane przez iterator. Dodawanie obiektów Dodawanie pary klucz-wartość odbywa się za pomocą metody put(). Przyjrzyjmy się etapom dodawania obiektu:

1. Obliczana jest wartość skrótu klucza wprowadzonego obiektu. Skrót klucza jest obliczany metodą static final int hash(Object key), która już uzyskuje dostęp do hashCode()znanej nam metody klucza. W tym celu używana jest metoda przesłonięta hashCode()lub jej domyślna implementacja. Dodatkowe przekształcenia w metodzie 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 кладем маленькие значения, то у них и биты хеш-kodов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Jakой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша obiektа начали вносить коррективы в то, в Jakой бакет попадёт obiekt) и, Jak следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

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

   
   i = (n - 1) & hash

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

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

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

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

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

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

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

      map.put("KING", 100);

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

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

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

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

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

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

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

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

   5. Jednocześnie obliczamy indeks kubełka, w którym będzie umieszczony nasz obiekt i sprawdzamy, czy znajdują się już w nim elementy. Obliczamy:

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

      sprawdzać:

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

   6. Ponieważ w wyniku sprawdzenia otrzymamy true (w zasobniku nie ma żadnych elementów), zostanie wygenerowany obiekt Node z następującymi polami:

      
      {
      int hash = 2306996 — сгенерированный хеш-kod
      String key = {"KING"} — ключ
      Integer value = 100 — oznaczający
      Node next = null — połączyć на следующий узел
      }

      Wygenerowany przez nas obiekt Node zostanie dodany do zasobnika pod indeksem [4]:

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

      newNode()to metoda, która po prostu zwraca obiekt klasy Node.

   7. Po dodaniu zostanie sprawdzone, czy aktualna liczba elementów nie przekracza parametru threshold:

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

      Jeśli przekroczy, zostanie wywołana metoda resize()zwiększająca rozmiar tablicy mieszającej.

      W tym momencie metoda putVal()(i odpowiednio put()) zakończy swoją pracę.

      Wynik można przedstawić graficznie w następujący sposób:

      Ogólnie tak wygląda dodanie węzła (pary klucz-wartość) do tabeli mieszającej, jeśli żądany segment jest pusty . Spróbujmy teraz dodać element, który doprowadzi do kolizji (gdy w jednym wiadrze znajduje się więcej niż jeden element).

Trochę o kolizjach Sytuację, w której różne klucze trafiają do tego samego segmentu (nawet z różnymi skrótami) nazywa się kolizją lub kolizją. Nawet jeśli tablica mieszająca jest większa niż zbiór danych i została wybrana dobra funkcja mieszająca, nie gwarantuje to, że nie wystąpią kolizje. A wartość skrótu jest ograniczona do zakresu wartości int (około 4 miliardów). Powstałą nową wartość również należy gdzieś zapisać i w tym celu należy określić, gdzie dokładnie zostanie zapisana. Nazywa się to rozwiązywaniem konfliktów. Istnieją dwa podejścia:

• łańcuchowanie zewnętrzne lub metoda łańcuchowania (zaimplementowana w HashMap) - tj. komórka faktycznie zawiera listę (łańcuch). A lista może już zawierać kilka wartości (niekoniecznie z tym samym kodem skrótu).
• metoda sondowania liniowego lub adresowania otwartego (zaimplementowana w IdentityHashMap) - polega na wyszukaniu pierwszej pustej komórki po tej, na którą wskazuje funkcja haszująca;

O kolizjach przeczytasz tutaj: kliknij

1. Korzystając z tej metody, put()do mapowania skrótu dodamy kolejną parę klucz-wartość:

   map.put("BLAKE", 10);

2. Obliczamy „wstępny skrót” – 63281361. Modyfikujemy go i w rezultacie otrzymujemy ostateczny kod skrótu – 63281940.

3. Ponieważ pierwsze sprawdzenie „pustości” zwróci teraz wartość false (nie ma potrzeby tworzenia tabeli), od razu obliczamy indeks wiadra, w którym zostanie umieszczony nasz obiekt:

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

4. Wiadro o podanym indeksie jest sprawdzane pod kątem obecności w nim elementów, a ponieważ if ((p = tab[i = (n - 1) & hash]) == null)w tym przypadku warunek nie jest spełniony (w wiadrze jest już element), to przechodzimy do bloku else.

5. Przede wszystkim porównujemy dodawany element z pierwszym elementem połączonej listy wewnątrz segmentu:

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

   При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так Jak obiektы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неrówna sięства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать oznaczający у ключа:

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

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

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

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

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

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

   Если же при первой итерации указатель не równa się null, это говорит о том, что в списке Jak минимум два element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого element со всеми ключами элементов в списке (способом, описанным в пятом пункте).

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

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

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

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

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

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

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

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

   binCount >= TREEIFY_THRESHOLD – 1

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

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

   Zamiast przechodzić do struktury drzewa, zostanie wywołana metoda resize()zwiększająca rozmiar tablicy mieszającej, redystrybuując elementy. treeify()z kolei połączona lista TreeNodekonwertuje się w czerwono-czarne drzewo. Metoda resize()iteruje po wszystkich elementach bieżącej pamięci, ponownie oblicza ich indeksy (biorąc pod uwagę nowy rozmiar) i redystrybuuje elementy do nowej tablicy.

   W skrócie, bez wchodzenia w szczegóły budowy czerwono-czarnego drzewa, dzieje się, co następuje:

   1. Pierwszy element listy zapisywany jest jako korzeń całego drzewa (czarny):

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

   2. Dla pozostałych elementów:

      rozłóż je w lewo lub w prawo w zależności od wartości skrótu:

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

      Wszystkie lewe dzieci muszą być mniejsze (lub równe) ich węzłowi głównemu, podczas gdy wszystkie prawe dzieci muszą być większe.

   3. Jeżeli dwa elementy mają takie same skróty i nie można ich w żaden inny sposób porównać (nie implementują interfejsu Comparable), przerywamy konstrukcję drzewa i wywołujemy metodę tieBreakOrder(), która z kolei wykorzystuje metodę natywną System.identityHashCode()do obliczenia unikalnego globalnie kodu skrótu .

      Więcej szczegółów tutaj: link do artykułu

   4. Sprawdzamy elementy drzewa (obiekty TreeNode) aż do znalezienia potomka (lewego lub prawego) elementu zerowego.

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

   5. Dodaj węzeł podrzędny (lewy lub prawy, w zależności od katalogu):

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

   6. Ponieważ dodanie nowego elementu może zaburzyć równowagę drzewa, metodę przywracania równowagi nazywamy:

      root = balanceInsertion(root, x);

      O równoważeniu CCH przeczytasz tutaj: habr

   7. Po zrównoważeniu element główny może ulec zmianie. Naprawiamy ten problem wywołując metodę, która gwarantuje, że przekazany do niej root będzie pierwszym węzłem:

      moveRootToFront(tab, root)

      Tutaj wyraźnie widać, jak zbudowane i samobalansujące jest czerwono-czarne drzewo: wizualizacja

To w zasadzie wszystko i na przykładzie załóżmy, że jako klucze chcemy dodać następujące imiona: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. I powiedzmy, że mamy w tabeli mieszającej co najmniej 64 segmenty i wszystkie te elementy zgromadziły się w jednym kubełku. Strukturalnie ten segment będzie wyglądał następująco (elementy są sortowane według kodu skrótu): Typ CCHD: Zobacz wnętrze wiadra: Odzyskiwanie elementów (pobieranie wartości według klucza) Jeśli chodzi o operację dodawania, jest ona dość prosta. Algorytm (jeśli w zasobniku znajduje się połączona lista) można zapisać w następujący sposób:

1. Oblicz kod skrótu klucza.
2. Oblicz indeks wiadra.
3. Przejdź przez indeks i porównaj klucz pierwszego elementu z istniejącą wartością. Jeśli są równe, zwróć wartość, w przeciwnym razie sprawdź następny element, jeśli istnieje.
4. Jeśli następny obiekt Node ma wartość null, zwróć wartość null.
5. Jeśli następny obiekt Node nie ma wartości null, przejdź do niego i powtarzaj pierwsze trzy kroki, aż element zostanie znaleziony lub następny obiekt Node będzie miał wartość null.

Metodą tą get()otrzymujemy wartość dla klucza „KRÓL”:

map.get("KING");

Wewnątrz wywoływana jest metoda getNode(int hash, Object key), do której przekazywany jest sam klucz („KING”) i jego hash (2306996), który jest wstępnie obliczany w taki sam sposób, jak podczas operacji put().

1. Sprawdzamy:

   1. czy tablica mieszająca w ogóle istnieje:(tab = table) != null

      Przypomnę, że tworząc HashMap, w konstruktorze nie tworzy się tablicy dla tabeli, dzieje się to w dalszej części metody resize(), która jest zawsze wywoływana podczas dodawania pierwszego elementu do tablicy mieszającej. Dlatego też, jeśli do HashMap nie dodano żadnych elementów, po prostu nie ma wewnętrznej tablicy do przechowywania tych elementów.

   2. jeśli poprzednie wyrażenie zwróci wartość true, musisz upewnić się, że długość tablicy wewnętrznej jest większa niż 0:(n = tab.length) > 0;

   3. jeśli poprzednie wyrażenie również zwróci wartość true, przejdź do koszyka przy indeksie (w naszym przypadku 4), który został wcześniej obliczony i sprawdź w nim obecność elementów:

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

   4. Klucz, którego szukamy, porównujemy z kluczem pierwszego elementu listy wewnątrz segmentu, ponieważ w większości segmentów będzie (nie wszędzie mamy kolizje) tylko jeden element (w naszym przypadku). Podobnie jak w przypadku metody put(), skróty są porównywane, a jeśli pasują, klucze porównywane są przez referencję, a dopiero potem przez equals().

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

      Ponieważ w naszym przypadku klucz „KING” będzie poprzedzał klucz „BLAKE” (w ramach połączonej listy nowe elementy dodawane są na końcu, a KING był dodawany jako pierwszy), zatrzymamy się w tym miejscu i zwrócimy pierwszy obiekt wpisz Node do metody get(), która „wyrwie” mu pole o wartości (100):

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

2. Jeśli w wiadrze znajduje się więcej niż jeden element, to:

   1. jeśli segment jest listą połączoną, przeglądamy listę przez każdy element w pętli, do – whileaż znajdziemy dopasowanie:

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

   2. jeśli wiadro jest strukturą drzewiastą, to dodatkowo wywoływana jest metoda getTreeNode(), która z kolei wykorzystuje metodę do znalezienia wymaganego klucza find(). Przeprowadzamy przeszukiwanie drzewa – porównujemy skróty i określamy lewy lub prawy węzeł główny do przeszukania. Jeśli klucze są równe (przez odwołanie lub przez equals), zwróć ten węzeł. Jeśli lewy lub prawy węzeł potomny ma wartość null, dodatkowo porównujemy klucze za pomocą funkcji CompareTo (jeśli klucze implementują interfejs Comparable), w przeciwnym razie wykonujemy rekurencyjne przeszukiwanie drzewa (prawe lub lewe poddrzewo) aż do znalezienia dopasowania.

Usuwanie obiektów z HashMap Ponieważ w artykule kończy się miejsce, pokrótce opiszę, jak odbywa się usuwanie za pomocą klucza. Algorytm jest bardzo podobny:

• przejdź do żądanego wiadra (znowu jest to wstępnie obliczone);

• jeśli w wiadrze znajduje się tylko jeden obiekt (sprawdzamy jego wskaźnik zerowy) porównujemy skróty, łącza i equals(jeśli nagle skróty nie są równe). Znalazłeś dopasowanie? Świetnie, to jest nasz klucz - usuń go (=null) i zwróć wartość tego klucza.

• jeśli w wiadrze znajduje się więcej niż jeden element, sprawdzamy każdy element w pętli, aż znajdziemy element lub dotrzemy do końca listy.

• jeśli element nie został znaleziony, zwracamy wartość null.

W sytuacji z drzewem mamy do czynienia z dość trudną implementacją, o której lepiej nie wiedzieć i spać spokojnie (w opisie metody jest nawet napisane, że implementacja jest bardziej skomplikowana niż przy zwykłej operacji usuwania w czerwono-czarnym układzie) drzewo). Co więcej, po usunięciu liczba węzłów w jednym segmencie może powrócić do 6, a następnie drzewo zostanie ponownie przebudowane na listę połączoną. Jeśli nie jesteś programistą z wieloletnim doświadczeniem, to wcale nie jest konieczne, aby to wiedzieć i rozumieć (i po prostu nie jest to konieczne).