Що станеться, якщо змінити змінний ключ в HashMap

Якщо змінити поля об'єкта, який вже використовується як ключ у HashMap, цей елемент стане недосяжним («загубиться»):

🟢 Junior Level

30-секундна відповідь

Якщо змінити поля об’єкта, який вже використовується як ключ у HashMap, цей елемент стане недосяжним («загубиться»):

Виклик map.get(key) поверне null.
Виклик map.containsKey(key) поверне false.
Виклик map.remove(key) не зможе видалити запис.

При цьому запис фізично залишиться в пам’яті купи всередині внутрішнього масиву HashMap. Розмір карти map.size() не зменшиться, збирач сміття не зможе видалити об’єкт, і в застосунку виникне тихий витік пам’яті (Logical Memory Leak).

Наочна аналогія з життя

Уявіть автоматичну камеру схову:

Ви здали валізу синього кольору. Автомат визначив номер комірки за кольором: «Синій $\to$ Комірка №5» і замкнув валізу там.
Вночі валізу перефарбували в червоний колір.
Вранці ви підходите до термінала й кажете: «Знайди мою червону валізу». Автомат обчислює алгоритм: «Червоний $\to$ Комірка №12», відкриває комірку №12 — вона порожня, і видає повідомлення: «Валізу не знайдено». Валіза назавжди залишилася замкненою в комірці №5.

Наочний приклад у коді

// Мутабельний список як ключ
List<String> keyList = new ArrayList<>();
keyList.add("USER");

Map<List<String>, String> permissions = new HashMap<>();
permissions.put(keyList, "READ_ACCESS");

// До мутації: ключ знаходить значення
System.out.println(permissions.get(keyList)); // "READ_ACCESS"

// 💥 КАТАСТРОФА: Мутуємо ключ прямо в пам'яті!
keyList.add("ADMIN");

// Після мутації: ключ втрачено!
System.out.println(permissions.get(keyList));          // ❌ null!
System.out.println(permissions.containsKey(keyList));  // ❌ false!
System.out.println(permissions.size());                // 1 (об'єкт застряг у мапі!)

🟡 Middle Level

Внутрішня будова: Подвійна точка відмови в `getNode()`

Щоб зрозуміти, чому HashMap не може знайти об’єкт, розглянемо вихідний код методу HashMap.getNode() в OpenJDK:

final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) { // Точка 1: Індекс бакета
        
        // Точка 2: Порівняння хешу та ключа
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // Пошук за списком/деревом бакета...
    }
    return null;
}

Коли поля ключа змінюються, пошук зазнає краху на двох рівнях:

1. Збій першого рівня: Пошук не в тому бакеті (Bucket Mismatch)

При виклику put(key) було обчислено хеш $H_1$, і запис було розміщено в table[5].
При виклику get(key) обчислюється новий хеш $H_2$, і формула (n - 1) & hash вказує на зовсім іншу комірку table[12]. У комірці №12 лежить null — пошук завершується за $O(1)$ з негативним результатом.

2. Збій другого рівня: Невідповідність кешованого хешу вузла

Навіть якщо в результаті випадкової колізії новий хеш вкаже на ту саму комірку table[5], пошук все одно провалиться:

Всередині вузла Node<K, V> зберігається кешоване значення final int hash, обчислене в момент вставки ($H_1$).
Перевірка first.hash == hash порівнює старий кешований хеш вузла $H_1$ та новий хеш переданого ключа $H_2$.
Оскільки $H_1 \ne H_2$, умова first.hash == hash повертає false, і HashMap навіть не намагається викликати key.equals(first.key)!

Порушення інваріантів `HashSet` (Дублікати в сеті)

Оскільки HashSet усередині побудований на HashMap, мутація елементів ламає контракт унікальності:

Set<List<String>> set = new HashSet<>();
List<String> list = new ArrayList<>(List.of("A"));
set.add(list);

list.add("B"); // Мутували елемент
set.add(list); // УСПІШНО ДОДАСТЬСЯ ВДРУГЕ!

System.out.println(set.size()); // Виведе 2! У Set потрапили дублікати одного об'єкта!

🔴 Senior Level

Витік пам’яті (Zombie Entries) та поведінка при `resize()`

Зомбі-записи (Logical Memory Leak):
- Вузол таблиці Node<K, V> утримує сильні посилання (Strong References) на об’єкт ключа та об’єкт значення.
- Збирач сміття не може звільнити цю пам’ять, навіть якщо в усьому застосунку на них більше немає зовнішніх посилань.
Що відбувається при розширенні таблиці (resize()):
- Коли кількість записів перевищує threshold, HashMap подвоює місткість масиву table.
- Під час рехешування HashMap НЕ перераховує key.hashCode() заново! Вона використовує старий кешований node.hash:
```
if ((e.hash & oldCap) == 0) // Використовується старий hash!
```
- Запис переміщується в новий бакет на основі свого старого початкового хешу.
- Таким чином, запис назавжди «консервується» в некоректному бакеті.

Єдиний спосіб вилучити втрачений елемент

Якщо ключ мутував, стандартний доступ за ключем неможливий. Єдиний спосіб прочитати або видалити зомбі-запис — повне лінійне сканування всіх корзин:

// Пошук за O(N) через ітератор entrySet:
for (Iterator<Map.Entry<List<String>, String>> it = map.entrySet().iterator(); it.hasNext(); ) {
    Map.Entry<List<String>, String> entry = it.next();
    if (entry.getKey() == keyList) { // Порівняння за посиланням!
        System.out.println("Знайдено значення: " + entry.getValue());
        it.remove(); // Єдиний спосіб видалити зомбі-вузол із пам'яті!
    }
}

3 архітектурні правила роботи з ключами

Незмінність як абсолютний закон: використовувати лише String, UUID, Long або record.
Ідіома Remove $\to$ Mutate $\to$ Put: якщо об’єкт зобов’язаний змінитися, його спочатку видаляють із карти за старим хешем, модифікують і вставляють назад із новим хешем:
```
String val = map.remove(key); // Видалення за старим хешем
key.mutate();
map.put(key, val);            // Вставка за новим хешем
```
IdentityHashMap: якщо бізнес-логіка вимагає порівняння об’єктів суворо за фізичною адресою в купі (k1 == k2), використовують IdentityHashMap. Її хеш обчислюється через System.identityHashCode() і ніколи не залежить від полів об’єкта.

4 Tricky Questions

1. Чи можна витягти значення з `HashMap`, якщо його ключ мутував, не очищаючи всю карту через `map.clear()`?

Відповідь: Так, але лише за час $O(N)$ через прямий обхід entrySet() або values(). Оскільки виклик map.get(key) розраховує індекс бакета за новим хешем і не знаходить вузол, залишається єдиний шлях — використати ітератор:

for (Map.Entry<K, V> entry : map.entrySet()) {
    if (entry.getKey() == mutatedKey) {
        return entry.getValue();
    }
}

Ітератор обходить усі корзини послідовно і знайде вузол незалежно від того, в якому бакеті він знаходиться. Через iterator.remove() цей запис можна безпечно видалити з купи.

2. Що відбувається з мутованим ключем під час операції `resize()` в `HashMap`? Чи перераховується його хеш-код заново?

Відповідь: Ні! Під час resize() метод HashMap ніколи не викликає key.hashCode() повторно. У вихідному коді resize() використовується значення e.hash, яке було обчислене та збережене в структурі Node в момент початкової вставки:

if ((e.hash & oldCap) == 0) { ... }

Вузол переміщується в нову таблицю в бакет зі старим індексом або зі зміщенням + oldCap, спираючись виключно на початковий старий хеш. Мутація ключа не виправляє його положення при ресайзі, а навпаки, назавжди закріплює його прив’язку до застарілого хешу.

3. Чому в методі `getNode()` перевірка `first.key == key` не спрацьовує, якщо новий хеш ключа за випадковим збігом вказав на ту саму корзину?

Відповідь: У методі getNode() умови перевірки в if з’єднані логічним оператором && та оптимізовані для раннього відсікання:

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

Першим виразом завжди йде перевірка цілочисельної рівності хешів: first.hash == hash. Оскільки first.hash зберігає старий хеш, а локальна змінна hash містить новий хеш мутованого ключа, умова first.hash == hash повертає false. Відповідно до логіки короткого замикання (Short-Circuit Evaluation) друга частина перевірки (first.key == key) навіть не обчислюється процесором, і вузол відкидається.

4. Що станеться, якщо мутувати елемент, що знаходиться всередині `HashSet`, а потім викликати `set.contains(element)`? А якщо викликати `set.add(element)`?

Відповідь:

set.contains(element) поверне false, оскільки пошук за новим хеш-кодом звернеться не в той бакет.
set.add(element) успішно додасть цей самий об’єкт у Set вдруге! Метод add() обчислить новий хеш-код, знайде порожню корзину (або корзину без дубліката) і створить новий запис. У результаті порушиться фундаментальний математичний контракт інтерфейсу Set: у колекції опиняться два однакові об’єкти з одним і тим самим посиланням у пам’яті, а розмір size() збільшиться на 1.

🎯 Шпаргалка для інтерв’ю

Що відбувається при зміні мутабельного ключа

get(key) / remove(key): повертають null / false (пошук в іншому бакеті).
Витік пам’яті: запис залишається в масиві table назавжди (Zombie Entry).
resize(): переміщує запис за старим кешованим хешем, не виправляючи помилку.
HashSet: порушується контракт унікальності, з’являються дублікати.
Як врятувати дані: лише повний обхід entrySet() за $O(N)$ із порівнянням посилань ==.

Як уникнути проблеми

Використовувати суворо незмінні ключі: String, UUID, Long, Record.
Якщо ключ зобов’язаний змінюватися: патерн Remove $\to$ Mutate $\to$ Put.
Для пошуку за посиланням використовувати IdentityHashMap.

Червоні прапорці на співбесіді (Чого говорити не можна)

❌ «HashMap автоматично перерахує хеш ключа при його зміні» — хеш-таблиця пасивна і не відстежує зміни полів об’єктів.
❌ «Втрачений об’єкт буде видалений Garbage Collector’ом» — масив table утримує сильне посилання, об’єкт не видалиться і спричинить Memory Leak.
❌ «Якщо бакет збігся, HashMap все одно знайде елемент за посиланням key == first.key» — перевірка first.hash == hash поверне false і скасує пошук.