Почему ключ в хэш-таблице должен быть неизменяемым?

Ключ должен быть неизменяемым (immutable), чтобы гарантировать корректную работу хэш-таблицы. Механизм поиска в таблице (например, HashMap в Java) основан на первоначальном значении хэш-кода ключа.

Проблема при изменении ключа:

1. Объект-ключ помещается в корзину (bucket), вычисленную на основе его hashCode().
2. Если после этого изменить состояние ключа, его hashCode() может стать другим.
3. При последующем поиске по этому (уже изменённому) ключу будет вычислена другая корзина, и запись не будет найдена, хотя она физически присутствует в таблице.

Пример с проблемой (Java):

import java.util.*;

public class HashMapMutableKeyDemo {
    public static void main(String[] args) {
        Map<List<String>, String> map = new HashMap<>();
        List<String> mutableKey = new ArrayList<>(Arrays.asList("A", "B"));

        map.put(mutableKey, "Data"); // Хэш вычислен для [A, B]
        System.out.println("До изменения: " + map.get(mutableKey)); // Вывод: Data

        mutableKey.add("C"); // Ключ изменён! Теперь это [A, B, C]
        // Хэш-код для [A, B, C] отличается от хэш-кода для [A, B]
        System.out.println("После изменения: " + map.get(mutableKey)); // Вывод: null
    }
}

Решение: Используйте в качестве ключей неизменяемые типы (String, Integer, собственные record-классы с final полями) или строго гарантируйте, что состояние ключевого объекта не будет меняться после добавления в таблицу.