Что произойдёт, если изменить мутабельный ключ в 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 и отменит поиск.