Что случится, если изменить ключ после добавления в HashMap

Если изменить поле объекта-ключа после того, как он был добавлен в HashMap через put():

🟢 Junior Level

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

Если изменить поле объекта-ключа после того, как он был добавлен в HashMap через put():

Элемент станет недоступен по ключу: метод map.get(key) вернет null, а map.containsKey(key) вернет false. Причина в том, что get() вычисляет хеш от текущего состояния объекта и ищет его в новом бакете, тогда как запись физически осталась лежать в старом бакете.
Парадокс итератора: при этом метод map.size() не изменится, а при обходе через for (var e : map.entrySet()) элемент будет виден, так как итератор обходит все корзины массива подряд.
Удалить через 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"); // Хеш-код объекта изменился прямо в куче!

        // ❌ ПАРАДОКС 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)

Удивительное свойство хеш-таблиц: если поля ключа вернуть в точности в исходное состояние, элемент снова начнет находиться!

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 сочтет узел несовпадающим и продолжит поиск, вернув 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")

Что происходит в куче:

В мапе теперь существуют две разные ноды 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(), возвращая null, так как поиск пойдет в корзину по новому хешу. При этом 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, проверка проваливается за 1 такт процессора, и метод equals() даже не вызывается.

Вопрос 3: Что произойдет с мутированным ключом во время ресайза таблицы `resize()`?

Ответ: Никакого пересчета key.hashCode() не произойдет. При ресайзе HashMap использует сохраненное поле e.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 не слушает события изменения объектов и не отслеживает мутации ключей. Узел остается в старой корзине.

❌ “Элемент уничтожается сборщиком мусора, так как ключ сломан.”
Правильно: Массив table[] удерживает сильную ссылку на Node, а узел удерживает ключ и значение. Возникает классическая утечка памяти.

❌ “Итератор тоже не сможет найти мутированный элемент.”
Правильно: Итератор обходит все корзины последовательно (table[0]...table[n-1]), поэтому он видит все узлы независимо от их хешей.