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

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

🟢 Junior Level

Короткий опис для співбесіди (30 секунд)

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

Елемент стане недоступним за ключем: виклик map.get(key) поверне null, а map.containsKey(key) поверне false. Причина в тому, що get() обчислює геш від поточного стану об’єкта і шукає його в новому бакеті, тоді як сам запис фізично залишився лежати в старому бакеті.
Парадокс ітератора: розмір колекції map.size() не зміниться, а при прямому обході через цикл for (var e : map.entrySet()) елемент буде видно, оскільки ітератор просто послідовно обходить усі бакети масиву table[] один за одним.
Неможливість видалення через map.remove(key): метод remove() так само розрахує новий бакет і поверне null. У пам’яті виникає «вузол-привид» (Ghost Entry), що породжує прогресуючий витік пам’яті.

Демонстрація на Java 21

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class MutatedKeyDemo {

    public static class UserKey {
        private String login; // Змінюване поле

        public UserKey(String login) { this.login = login; }
        public void setLogin(String login) { this.login = login; }

        @Override
        public boolean equals(Object o) {
            return o instanceof UserKey k && Objects.equals(login, k.login);
        }

        @Override
        public int hashCode() {
            return Objects.hash(login);
        }
    }

    public static void main(String[] args) {
        Map<UserKey, String> sessions = new HashMap<>();

        UserKey key = new UserKey("alice");
        sessions.put(key, "ActiveSession_Alice"); // Збережено в бакет за гешем "alice"

        // До мутації:
        System.out.println("Пошук до мутації: " + sessions.get(key)); // ActiveSession_Alice

        // Мутуємо ключ:
        key.setLogin("bob"); // Геш-код об'єкта змінився прямо в купі (heap)!

        // ❌ ПАРАДОКС 1: Прямий пошук повертає null
        System.out.println("Пошук після мутації: " + sessions.get(key)); // null!

        // ❌ ПАРАДОКС 2: Ітератор успішно знаходить "втрачений" елемент
        for (Map.Entry<UserKey, String> entry : sessions.entrySet()) {
            System.out.println("Знайдено ітератором: " + entry.getKey().login + " => " + entry.getValue());
            // Надрукує: "Знайдено ітератором: bob => ActiveSession_Alice"
        }
    }
}

🟡 Middle Level

Ефект «Відновлення ключа» (Key Restoration)

Цікава властивість архітектури геш-таблиць: якщо значення полів ключа повернути в початковий первинний стан, елемент знову почне успішно знаходитися через get():

key.setLogin("bob");
System.out.println(sessions.get(key)); // null (новий геш вказує в інший бакет)

// Повертаємо вихідний стан поля:
key.setLogin("alice");
System.out.println(sessions.get(key)); // Знову повертає "ActiveSession_Alice"!

Оскільки сам вузол фізично ніколи не залишав первинний бакет, щойно виклик key.hashCode() повертається до початкового значення, мапа знову звертається до правильного кошика і знаходить запис.

Поведінка під час ресайзу (`resize()`)

Що відбувається з мутованим ключем, коли HashMap подвоює місткість таблиці?

У кожному вузлі Node<K,V> зберігається незмінне кешоване поле final int hash, записане в момент виклику put():

Під час ресайзу HashMap не викликає метод key.hashCode() заново!

Вона використовує збережене значення e.hash і розраховує нову позицію бітовою перевіркою:

if ((e.hash & oldCap) == 0) // Залишається на oldIndex
else                        // Переходить на oldIndex + oldCap

Це означає, що навіть після ресайзу вузол залишиться прив’язаним до свого первинного гешу, тоді як виклик get(key) продовжить використовувати новий мутований геш. Розсинхронізація стає постійною.

🔴 Senior Level

Розсинхронізація `Node.hash` та випадковий збіг індексу бакета

Що станеться, якщо внаслідок мутації новий hashCode() випадково вкаже на той самий індекс бакета? Чи знайдеться елемент?

Відповідь: НІ, елемент все одно НЕ знайдеться!

Поглянемо на умову валідації вузла в HotSpot HashMap.getNode():

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

У вузлі збережено поле first.hash (геш до мутації, наприклад 100);
Поточний виклик get(key) розраховує новий геш: hash = key.hashCode() (наприклад, 116);
Навіть якщо за бітовою маскою & 15 обидва значення дають однаковий індекс бакета 4 (100 & 15 == 4 та 116 & 15 == 4), найперша перевірка цілих чисел: first.hash == hash $\implies$ 100 == 116 повертає false!
HashMap миттєво відкидає вузол за 1 такт CPU і продовжує обхід, у підсумку повертаючи null. Невідповідність кешованого гешу блокує доступ до елемента навіть у межах того самого бакета.

Аномалія дублювання посилань: Два записи на один об’єкт

Якщо після мутації ключа повторно викликати put() із тим самим екземпляром об’єкта:

UserKey key = new UserKey("alice");
map.put(key, "Version-1"); // table[3], Node.hash = hash("alice")

key.setLogin("bob");
map.put(key, "Version-2"); // table[11], Node.hash = hash("bob")

Що відбувається в пам’яті купи (JVM Heap):

Усередині мапи утворюються два різні вузли Node<K,V> у різних бакетах;
Обидва вузли в полі key посилаються на один і той самий екземпляр у купі;
Розмір мапи map.size() стає рівним 2;
Виклик map.get(key) повертає "Version-2";
Запис "Version-1" назавжди стає некерованим «сміттям» (Ghost Entry), яке неможливо отримати через get(), оскільки посилання key вже не генерує старий геш "alice".

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

1. 30-секундний есенс (Elevator Pitch)

Якщо змінити ключ після додавання в HashMap, елемент стане недоступним через get() і remove(), оскільки мапа піде шукати запис у кошику за новим гешем. При цьому size() не зміниться, а ітератор entrySet() побачить елемент під час повного перебору всіх бакетів. Навіть якщо новий геш випадково дасть той самий номер бакета, елемент не буде знайдено через невідповідність кешованого поля Node.hash. Якщо ж повернути поля ключа до початкового стану, доступ до елемента повністю відновиться.

2. 4 каверзні питання з глибокими відповідями

Питання 1: Що відбудеться, якщо після мутації ключа викликати `map.put(key, newValue)` з тим самим об’єктом?

Відповідь: Мапа розрахує новий геш і створить новий вузол в іншому бакеті. У результаті в таблиці з’являться два незалежні вузли Node, що посилаються на один і той самий екземпляр у пам’яті купи, а лічильник size() зросте на 1. Первинний запис перетвориться на «зомбі-вузол»: його неможливо оновити чи видалити стандартним викликом map.remove(key).

Питання 2: Чому метод `get()` не знайде мутований ключ, навіть якщо новий геш випадково вкаже на той самий бакет?

Відповідь: Тому що в HashMap під час перевірки вузла в бакеті спочатку порівнюються числові геші: if (first.hash == hash). У вузлі Node кешується первинний геш, обчислений у момент вставки (first.hash). Виклик get() передає новий мутований геш. Оскільки first.hash != hash, умова повертає false за 1 машинний такт, і метод equals() навіть не викликається.

Питання 3: Що станеться з мутованим ключем під час подвоєння місткості таблиці (`resize()`)?

Відповідь: Жодного перерахунку key.hashCode() не відбувається. Під час ресайзу HashMap зчитує збережене поле node.hash і розподіляє вузли за значенням біта (e.hash & oldCap) == 0. Вузол займе комірку відповідно до свого первинного гешу, назавжди закріпивши розсинхронізацію з мутованим ключем.

Питання 4: Як гарантовано видалити «втрачений» запис із мапи без виклику `map.clear()`?

Відповідь: Виключно за допомогою явного ітератора entrySet().iterator(), перевіряючи фізичну рівність посилань на об’єкти:

Iterator<Map.Entry<UserKey, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getKey() == mutatedKey) {
        it.remove(); // Безпечно видалить вузол безпосередньо з поточного бакета
    }
}

3. Типові помилки та Red Flags

❌ «При зміні ключа HashMap автоматично перенесе елемент у новий бакет.»
Правильно: HashMap не має механізмів спостереження (listeners) за мутацією ключів. Вузол залишається на старому місці.

❌ «Загублений елемент буде знищено збирачем сміття (GC).»
Правильно: Масив table[] утримує жорстке посилання на Node, а вузол посилається на ключ і значення. Це спричиняє класичний витік пам’яті.

❌ «Ітератор теж не зможе знайти мутований елемент.»
Правильно: Ітератор проходить фізично по всіх бакетах таблиці від table[0] до table[n-1], тому він бачить усі вузли незалежно від їхніх поточних геш-кодів.