Докладний розбір класу HashMap

Перш ніж переходити до докладного розгляду класу, зупинимося на базових поняттях, пов'язаних із хеш-таблицями. У цій статті не розглядатимуться методи для роботи з хеш-відображенням. Наочно і детально будуть розглянуті тільки операції вставляння, пошуку і видалення. Прочитати опис наявних у HashMap методів у того ж Шилдта, я гадаю, не становитиме труднощів. Можливо, у майбутньому я напишу ще одну статтю, присвячену таким методам, але поки що це під питанням. Порівняно з Java 7 клас HashMap у Java 8 зазнав значних змін (+1000 рядків коду). Хеш-таблицею називається структура даних, яка реалізує інтерфейс асоціативного масиву (абстрактна модель «ключ - значення» або entry), що забезпечує дуже швидке вставляння та пошук: незалежно від кількості елементів вставляння та пошук (а іноді й видалення) виконуються за час, близький до константи – O(1). По суті, це звичайний масив, де місце розташування елемента залежить від значення самого елемента. Зв'язок між значенням елемента і його позицією в хеш-таблиці задає хеш-функція. Хеш-функція отримує вхідну частину даних, яку ми називаємо ключем, а на виході вона видає ціле число, відоме як хеш-значення (або хеш-код). Потім хеш-значення прив'язує наш ключ до певного індексу хеш-таблиці. Для основних операцій: вставляння, пошуку та видалення ми використовуємо одну й ту саму хеш-функцію, тому ці операції здійснюються досить швидко. Через це важливо, щоб хеш-функція поводилася послідовно і виводила один і той самий індекс для однакових вхідних даних. Варто зазначити, що отриманий хеш-код може бути величезним числовим значенням, а вихідний масив умовно розрахований тільки на 16 елементів. Не створювати ж масив на мільярд елементів, щоб додати туди лише десять? Тому ми цей хеш-код маємо якось трансформувати у значення від 0 до 15 (якщо розмір масиву 16). І ось для цього використовують додаткові перетворення. Таким чином, ми генеруємо індекс для мінімізації розміру масиву. Наприклад, у HashMap до Java 8 використовувався ось такий додатковий метод для пошуку необхідної комірки:

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

На вхід він приймав хеш-код, отриманий внаслідок роботи hashCode(), і довжину внутрішнього масиву (кількість комірок). А повертав результат «"хеш-код» -> побітове «І» -> (довжина масиву – 1). Клас HashMap успадковується від класу AbstractMap і реалізує такі інтерфейси: Map, Cloneable, Serializable. За хеш-функцію в Java відповідає метод hashCode(). Реалізація за замовчуванням hashCode() повертає значення, яке називається ідентифікаційний хеш (identity hash code). Навіть якщо клас перевизначає hashCode(), ви завжди можете отримати ідентифікаційний хеш об'єкта за допомогою виклику System.identityHashCode(Object o). Реалізація за замовчуванням hashCode() в OpenJDK не має нічого спільного з адресою пам'яті, як це іноді прийнято вважати. У HashMap хеш-таблиця реалізована на основі масиву (а якщо точніше – динамічного, оскільки таблиця може розширюватися) однозв'язаних списків. По суті, ми отримуємо хеш-код ключа внаслідок роботи методу hashCode(), який потім модифікують (як розглянемо далі), а всередині за допомогою додаткового методу отримані значення розподіляють за потрібними комірками. Елементи масиву (комірки) ще називаються кошиками "buckets", які використовуються для зберігання окремо взятих вузлів. Кожен з бакетів являє собою колекцію (список або дерево). Вузол являє собою об'єкт вкладеного класу Node (або TreeNode у разі деревоподібної структури). По суті, всередині комірки масиву лежить LinkedList, тільки список однозв'язаний, або червоне-чорне дерево, яке лежить в основі реалізації іншого класу – TreeMap. Варіант із червоно-чорним деревом виникає не настільки часто (як, що і куди – далі), та й структура ця досить непроста для розуміння, тому акцент буде зроблено на вузлі типу Node. Node – це вкладений клас усередині HashMap, який має такі поля:

• final int hash – хеш поточного елемента, який ми отримуємо внаслідок хешування ключа;
• final K key – ключ поточного елемента. Саме сюди записується те, що ви вказуєте першим об'єктом у методі put();
• V value – значення поточного елемента. А сюди записується те, що ви вказуєте другим об'єктом у методі put();
• Node < K, V> next – посилання на наступний вузол у межах одного кошика. Список же зв'язаний, тому йому потрібне посилання не наступний вузол, якщо такий є.

Тепер розглянемо поля самого класу HashMap:

• transient Node < K, V> [] table – сама хеш-таблиця, реалізована на основі масиву, для зберігання пар «ключ-значення» у формі вузлів. Тут зберігаються наші Node;
• transient int size – кількість пар «ключ-значення»;
• int threshold – гранична кількість елементів, після досягнення якої розмір хеш-таблиці збільшується вдвічі. Обчислюється за формулою (capacity * loadFactor);
• final float loadFactor – цей параметр відповідає за те, за якого ступеня завантаженості поточної хеш-таблиці необхідно створювати нову хеш-таблицю, тобто щойно хеш-таблиця заповниться на 75%, буде створено нову хеш-таблицю з переміщенням в неї поточних елементів (витратна операція, адже потребується перехешування всіх елементів);
• transient Set< Map.Entry< K,V>> entrySet – містить кешований entrySet(), за допомогою якого ми можемо перебирати HashMap.

І константи:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4 – ємність хеш-таблиці за замовчуванням (16);
• static final int MAXIMUM_CAPACITY = 1 << 30 – максимально можлива ємність хеш-таблиці (приблизно 1 млрд.);
• static final float DEFAULT_LOAD_FACTOR = 0.75f – коефіцієнт завантаження, який використовується за замовчуванням;
• static final int TREEIFY_THRESHOLD = 8 – це «поріг» кількості елементів в одному кошику, після досягнення якого внутрішній зв'язаний список буде перетворено на деревоподібну структуру (червоно-чорне дерево).
• static final int UNTREEIFY_THRESHOLD = 6 – якщо кількість елементів в одному кошику зменшиться до 6, то станеться зворотний перехід від дерева до зв'язаного списку;
• static final int MIN_TREEIFY_CAPACITY = 64 – мінімальна ємність (кількість кошиків) хеш-таблиці, за якої можливий перехід до деревоподібної структури. Тобто якщо в хеш-таблиці принаймні 64 бакети і в одному бакеті 8 або більше елементів, то відбудеться перехід до деревоподібної структури.

Конструктори класу:

1. public HashMap() – створює хеш-відображення за замовчуванням: обсягом (capacity) = 16 і з коефіцієнтом завантаженості (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m) – створює хеш-відображення, ініціалізоване елементами іншого заданого відображення з тією початковою ємністю, якої вистачить, щоб вмістити в себе елементи іншого відображення;
3. public HashMap(int initialCapacity) – створює хеш-відображення із заданою початковою ємністю. Для коректної і правильної роботи HashMap розмір внутрішнього масиву обов'язково має бути ступенем двійки (тобто 16, 64, 128 тощо);
4. public HashMap(int initialCapacity, float loadFactor) – створює хеш-відображення із заданими параметрами: початковою ємністю і коефіцієнтом завантаженості.

Клас реалізує інтерфейс Map і розширює клас AbstractMap, не доповнюючи їх своїми методами. Хеш-відображення не гарантує порядок розташування своїх елементів. Отже, порядок, у якому елементи вводять у хеш-відображення, не обов'язково відповідає тому порядку, у якому їх витягує ітератор.

Додавання об'єктів

Додавання пари "ключ-значення" здійснюється за допомогою методу put(). Розглянемо кроки, що виконуються під час додавання об'єкта:

1. Обчислюється хеш-значення ключа введеного об'єкта. Хеш ключа обчислює метод static final int hash(Object key), який уже звертається до відомого нам методу hashCode() ключа. Для цього використовується або перевизначений метод hashCode(), або його реалізація за замовчуванням. Додаткові перетворення в методі 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 кладемо маленькі значення, то у них і біти хеш-кодів будуть заповнені тільки нижні. У такому разі ключі в HashMap матимуть тенденцію накопичуватися в нижніх комірках, а верхні залишатимуться порожніми, що не дуже ефективно. На те, в який бакет потрапить новий запис, впливають тільки молодші біти хеша. Тому й придумали різними маніпуляціями підмішувати старші біти хеша в молодші, щоб поліпшити розподіл за бакетами (щоб старші біти рідного хеша об'єкта почали вносити корективи в те, в який бакет потрапить об'єкт) і, як наслідок, продуктивність. Тому і придумана додаткова функція hash всередині HashMap.

2. Обчислюємо індекс бакета (комірки масиву), в який буде додано наш елемент:

   i = (n - 1) & hash

   де n – довжина масиву.

3. Створюється об'єкт Node.

4. Тепер, знаючи індекс у масиві, ми отримуємо список (ланцюжок) елементів, прив'язаних до цієї комірки. Якщо в бакеті порожньо, тоді просто розміщуємо в ньому елемент. Інакше хеш і ключ нового елемента почергово порівнюються з хешами і ключами елементів зі списку і, у разі збігу цих параметрів, значення елемента перезаписується. Якщо збігів не виявлено, елемент додається в кінець списку.

Тепер до дуже докладного прикладу.

1. Створимо об'єкт класу HashMap:

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

2. За допомогою методу put() додамо в хеш-відображення першу пару «ключ-значення»:

   
   map.put("KING", 100);
   

   У цей момент всередині викликається метод putVal().

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

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

   Отриманий хеш-код модифікується за формулою: (хеш-код) ^ (хеш-код>>> 16), і внаслідок отримуємо остаточний хеш-код - 2306996.

4. Перевіряємо таблицю на "порожнечу":

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

   де [] tab – сама хеш-таблиця: посилаємо tab і table (нагадаю, що це поле класу HashMap, яке зберігає масив для наших елементів) на один і той самий масив, а int n – додаткова змінна-лічильник.

   Оскільки перевірка поверне true (бо масив для таблиці не було створено за допомогою оператора new у конструкторі), буде викликано метод resize(), який власне і створить таблицю розміром у 16 елементів. Так-так, конструктори класу ніякої таблиці не створюють. Замість цього завжди відбувається виклик методу resize() під час першого додавання елемента. Довжина створеної таблиці (вважай довжина масиву) буде записана у змінну n - n = (tab = resize()).length, яка надалі використовується для обчислення бакета.

5. Одночасно обчислюємо індекс бакета, куди буде поміщений наш об'єкт, і перевіряємо, а чи є вже в ньому елементи. Обчислюємо:

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

   перевіряємо:

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

6. Оскільки внаслідок перевірки ми отримаємо true (у пакеті елементів немає), буде згенеровано об'єкт Node з такими полями:

   { int hash = 2306996 – згенерований хеш-код String key = {"KING"} - ключ Integer value = 100 – значення Node next = null – посилання на наступний вузол }

   Наш сформований об'єкт Node буде додано в бакет під індексом [4]:

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

   newNode() – це метод, який просто повертає об'єкт класу Node.

7. Після додавання буде здійснена перевірка, чи не перевищує поточна кількість елементів параметр threshold:

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

   Якщо перевищує, тоді буде викликано метод resize() для збільшення розміру хеш-таблиці.

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

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

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

Трохи про колізії

Ситуація, коли різні ключі потрапляють в один і той самий бакет (навіть із різними хешами), називається колізією або зіткненням. Навіть якщо хеш-таблиця більша за набір даних, і було обрано хорошу хеш-функцію, це не гарантує того, що колізії не виникнуть. Та й значення хеша обмежене діапазоном значень типу int (приблизно 4 млрд.). Отримане нове значення також потрібно кудись записати, і для цього потрібно визначити, куди саме воно буде записано. Це називається вирішенням колізії. Існує два підходи:

• external chaining або метод ланцюжків (реалізований у HashMap) – тобто в комірці насправді міститься список (chain). А вже у списку може міститися кілька значень (не обов'язково з однаковим хеш-кодом).
• linear probing або метод відкритої адресації (реалізований в IdentityHashMap) – полягає в пошуку першої порожньої комірки після тієї, на яку вказала хеш-функція;

1. За допомогою методу put() додамо в хеш-відображення ще одну пару «ключ-значення»:

   
   map.put("BLAKE", 10);
   

2. Обчислюємо "попередній хеш" – 63281361. Модифікуємо його і внаслідок отримуємо остаточний хеш-код – 63281940.

3. Оскільки перша перевірка на «порожнечу» тепер поверне false (створювати таблицю не треба), одразу обчислюємо індекс бакета, куди буде поміщений наш об'єкт:

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

4. Бакет під зазначеним індексом перевіряється на наявність у ньому елементів, і оскільки умова if ((p = tab[i = (n - 1) & hash]) == null) у цьому разі не виконується (у бакеті вже є елемент), тоді переходимо до блоку else.

5. Насамперед ми порівнюємо елемент, що додається, з першим елементом зв'язаного списку всередині бакета:

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

   Під час перевірки спочатку порівнюються хеші ключів. Якщо ця «ділянка» (p.hash == hash) повертає false, тоді інша частина умови ігнорується(&&), оскільки об'єкти гарантовано різні. Інакше потім порівнюються ключі за посиланням (==) і в разі нерівності, ключі порівнюються вже за допомогою методу equals(). Порівняння здійснюється в такому порядку на благо продуктивності. Якщо всі три вирази повертають true, це означає, що ключі рівні і новий елемент буде записано в додаткову змінну, щоб надалі за її допомогою перезаписати значення в ключа:

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

   У результаті порівняння ключів ми отримуємо false вже на першому етапі (різні хеші).

6. Ігноруємо умову(p instanceof TreeNode), оскільки структура в пакеті не є деревоподібною на цьому етапі.

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

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

   Ви можете запитати, а де ж перевірка на рівність ключів? Ми ж не можемо просто взяти і додати новий елемент. Так ось вона вже була заздалегідь здійснена в пункті (5). Завдяки цьому тепер ми можемо просто перевірити покажчик цього елемента, і оскільки він зараз дорівнює null, можна дійти висновку, що в списку тільки один елемент. І оскільки ми вже перевіряли їхні ключі, ми можемо безболісно додавати новий елемент.

   Якщо ж під час першої ітерації покажчик не дорівнює null, це свідчить про те, що в списку щонайменше два елементи, тож у такому разі ми переходимо до наступної умови та порівнюємо ключ елемента, що додається, з усіма ключами елементів у списку (способом, описаним у п'ятому пункті).

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

   Якщо під час порівняння ключів буде виявлено збіг, новий елемент буде записано в додаткову змінну, щоб надалі з її допомогою перезаписати значення в ключа.

   Після додавання другого елемента наш об'єкт HashMap графічно має такий вигляд:

   Зрештою додавання елементів під час колізії (у межах одного бакета) має такий вигляд:

   • перевіряємо за допомогою методів hashCode() і equals(), що обидва ключі однакові.
   • якщо ключі однакові, замінити поточне значення новим.
   • інакше зв'язати новий і старий об'єкти за допомогою структури даних "зв'язаний список", вказавши посилання на наступний об'єкт у поточному і зберегти обидва під потрібним індексом; або здійснити перехід до деревоподібної структури

8. Після кожної ітерації (додавання нового елемента) у циклі for збільшується лічильник, який відповідає за кількість елементів у пакеті:

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

   Допоки їхня кількість не стане рівною або більшою за 7:

   
   binCount >= TREEIFY_THRESHOLD – 1
   

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

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

   Замість переходу до деревоподібної структури буде викликано метод resize() для збільшення розміру хеш-таблиці з перерозподілом елементів. treeify() зі свого боку зв'язаний список із TreeNode конвертує в червоно-чорне дерево. Метод resize() перебирає всі елементи поточного сховища, перераховує їхні індекси (з урахуванням нового розміру) і перерозподіляє елементи в усьому масиві.

   Якщо коротко, не вдаючись у подробиці структури червоно-чорного дерева, то відбувається таке:

   1. Перший елемент списку записується як корінь усього дерева (чорний колір):

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

   2. Для інших елементів:

      розподіляємо їх наліво або направо залежно від значення хешів:

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

      Усі ліві нащадки мають бути меншими за свій кореневий вузол (або дорівнювати йому), тоді як усі праві нащадки мають бути більшими.

   3. Якщо у двох елементів збіглися хеші та їх не можна порівняти в інший спосіб (не реалізують інтерфейс Comparable), перериваємо побудову дерева і викликаємо метод tieBreakOrder(), який зі свого боку використовує нативний метод System.identityHashCode() для обчислення глобального унікального хеш-коду.

   4. Перевіряємо елементи дерева (об'єкти TreeNode), допоки не вдасться відшукати дочірній (лівий або правий) нульовий елемент.

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

   5. Додаємо дочірній вузол (лівий або правий, залежно від dir):

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

   6. Оскільки під час додавання нового елемента може порушитися баланс дерева, викликаємо метод для перебалансування:

      
      root = balanceInsertion(root, x);
      

   7. Після балансування кореневий елемент може змінитися. Виправляємо це викликом методу, який гарантує, що переданий йому корінь буде першим вузлом:

      
      moveRootToFront(tab, root)
      

      Як будується і самобалансується червоно-чорне дерево можна наочно подивитися тут: візуалізація

На цьому в принципі все і на прикладі припустимо, що ми хочемо додати як ключі такі імена: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. І припустимо, що в хеш-таблиці у нас мінімум 64 бакети, і всі ці елементи скупчилися в одному бакеті. Структурно цей бакет матиме такий вигляд (елементи сортуються за хеш-кодом): Вид КЧД: Вид всередині бакета:

Отримання елементів (витяг значення за ключем)

Щодо операції додавання здійснюється досить просто. Алгоритм (коли в пакеті зв'язаний список) можна записати так:

1. Обчислити хеш-код ключа.
2. Обчислити індекс бакета.
3. Перейти за індексом і порівняти ключ першого елемента з наявним значенням. Якщо вони рівні – повернути значення, інакше виконати перевірку для наступного елемента, якщо він існує.
4. Якщо наступний об'єкт Node дорівнює null, повертаємо null.
5. Якщо наступний об'єкт Node не дорівнює null, переходимо до нього і повторюємо перші три кроки, допоки елемент не буде знайдений або наступний об'єкт Node не дорівнюватиме null.

За допомогою методу get() отримаємо значення для ключа "KING":

map.get("KING");

Усередині викликається метод getNode(int hash, Object key), якому передають сам ключ ("KING") і його хеш (2306996), який попередньо обчислюють у такий самий спосіб, як і під час операції put().

1. Перевіряємо:

   1. чи існує взагалі хеш-таблиця: (tab = table) != null

      Нагадаю, що під час створення HashMap масив для таблиці в конструкторі не створюють, це відбувається надалі в методі resize(), який викликається завжди під час додавання першого елемента в хеш-таблицю. Тому, якщо в HashMap не було додано жодних елементів, внутрішнього масиву для зберігання елементів просто не існує.

   2. якщо попередній вираз повертає true, необхідно переконатися в тому, що довжина внутрішнього масиву більша за 0: (n = tab.length) > 0;

   3. якщо попередній вираз також повертає true, переходимо в бакет під індексом (у нашому випадку 4), який був попередньо обчислений, і перевіряємо його на наявність у ньому елементів:

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

   4. Порівнюємо ключ, який ми шукаємо, з ключем першого елемента в списку всередині бакета, оскільки в більшості бакетів буде знаходитися (не скрізь же у нас колізії) тільки один елемент (наш випадок). Як і у випадку з методом put(), порівнюються хеші, і якщо вони збігаються, ключі порівнюються за посиланням, і тільки потім за equals().

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

      Оскільки в нашому випадку ключ "KING" передуватиме ключу "BLAKE" (усередині зв'язаного списку нові елементи додаються в кінець, а KING було додано першим), ми зупинимося на цьому етапі та повернемо об'єкт first типу Node методу get(), який "витягне" у нього поле зі значенням (100):

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

2. Якщо всередині бакета знаходиться понад один елемент, тоді:

   1. якщо бакет являє собою зв'язаний список – проходимося в списку по кожному з елементів у циклі do-while, допоки не буде знайдено збіг:

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

   2. якщо бакет являє собою деревоподібну структуру, тоді додатково викликається метод getTreeNode(), який зі свого боку для пошуку потрібного ключа використовує метод find(). Здійснюємо пошук у дереві – порівнюємо хеші та визначаємо лівий або правий вузол кореня для пошуку. Якщо ключі рівні (за посиланням або за equals), повертаємо цей вузол. Якщо лівий або правий дочірній вузли дорівнюють null, додатково порівнюємо ключі через compareTo (якщо ключі реалізують інтерфейс Comparable), інакше здійснюємо рекурсивний пошук у дереві (правому або лівому піддереві), допоки не буде знайдено збіг.

Видалення об'єктів з HashMap

Оскільки місце в статті закінчується, коротко опишу як відбувається видалення за ключем. Алгоритм дуже схожий:

• заходимо в потрібний бакет (знову ж таки він попередньо обчислюється);

• якщо в пакеті тільки один об'єкт (перевіряємо у нього покажчик null) порівнюємо хеші, посилання і equals (якщо раптом хеші не рівні). Знайшовся збіг? Чудово, це наш ключ – видаляємо його (=null) і повертаємо значення цього ключа.

• якщо в пакеті понад один елемент, перевіряємо кожен елемент у циклі, допоки не знайдемо елемент або досягнемо кінця списку.

• якщо елемент не було знайдено – повертаємо null.

У ситуації з деревом досить мудрована реалізація, про яку краще не знати і спати спокійно (в описі до методу навіть написано, що реалізація складніша за звичайну операцію видалення в червоно-чорному дереві). Тим паче, під час видалення кількість вузлів в одному пакеті може повернутися до значення 6, і тоді дерево назад перебудується у зв'язаний список. Якщо ви не розробник з багаторічним стажем, знати про це і розуміти це зовсім не обов'язково (та й просто не потрібно).