Почему тип данных, используемый в качестве ключа в Hash Table, должен быть неизменяемым?

Почему тип данных, используемый в качестве ключа в Hash Table, должен быть неизменяемым?

Это один из критических требований при работе с хеш-таблицами (HashMap, Hashtable, ConcurrentHashMap). Использование mutable объектов в качестве ключей приводит к нарушению целостности структуры данных и потере данных.

Основная проблема: Изменение hashCode()

Вся архитектура хеш-таблицы строится на предположении, что hashCode() ключа никогда не меняется:

// Контракт HashMap требует:
// Если объект используется как ключ, его hashCode() НИКОГДА не должен меняться

public class MutableKey {
    private String value;  // mutable!
    
    public MutableKey(String value) {
        this.value = value;
    }
    
    @Override
    public int hashCode() {
        return value.hashCode();  // hashCode зависит от mutable содержимого
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof MutableKey)) return false;
        return value.equals(((MutableKey) o).value);
    }
    
    // Проблема: этот setter меняет hashCode()!
    public void setValue(String newValue) {
        this.value = newValue;
    }
}

Демонстрация проблемы

public class MutableKeyProblem {
    public static void main(String[] args) {
        HashMap<MutableKey, String> map = new HashMap<>();
        
        MutableKey key1 = new MutableKey("alice");
        map.put(key1, "Alice data");
        System.out.println("После put: " + map.get(key1));  // "Alice data"
        
        // Проблема: Меняем содержимое ключа
        key1.setValue("bob");
        
        // Теперь hashCode() вернет другое значение!
        System.out.println("После изменения: " + map.get(key1));  // null!
        
        // Почему null?
        // 1. Первоначально key1 с value="alice" хранился в bucket[hash("alice")]
        // 2. Когда мы изменили value на "bob", hashCode() изменился
        // 3. HashMap ищет ключ в bucket[hash("bob")]
        // 4. Там его нет! Он всё ещё в bucket[hash("alice")]
    }
}

Как работает HashMap внутри

Шаг 1: Добавление (put)

key = "alice", hashCode = 100

1. Вычисляем bucket index: 100 % capacity = 5
2. Размещаем в bucket[5]: (key="alice", value="Alice data")

Шаг 2: Поиск (get) - ВСЁ ОК

key = "alice", hashCode = 100

1. Вычисляем bucket index: 100 % capacity = 5
2. Ищем в bucket[5] - Находим!

Шаг 3: Изменение ключа

key.setValue("bob")
Теперь hashCode(key) = 200 (ДРУГОЙ!)

Шаг 4: Поиск (get) - ВСЁ ЛОМАЕТСЯ

key = "bob", hashCode = 200

1. Вычисляем bucket index: 200 % capacity = 7
2. Ищем в bucket[7] - Ничего там нет!
3. Возвращаем null

Но данные остались в bucket[5]! ПОТЕРЯ ДАННЫХ!

Почему String/Integer/Long работают?

Они неизменяемы (immutable):

public final class String implements Comparable<String>, CharSequence {
    private final char[] value;  // final - не может быть изменено
    private final int hash;      // кешированный hashCode
    
    public int hashCode() {
        if (hash == 0) {
            // Вычисляем один раз и кешируем
            int h = 0;
            for (char c : value) {
                h = 31 * h + c;
            }
            hash = h;
        }
        return hash;  // Всегда одно и то же значение
    }
}

// Безопасное использование:
HashMap<String, String> map = new HashMap<>();
String key = new String("alice");
map.put(key, "Alice data");

// Даже если заново создать String с тем же содержимым
String key2 = new String("alice");
map.get(key2);  // "Alice data" - работает корректно

Практический пример: Правильно vs Неправильно

НЕПРАВИЛЬНО: Mutable ключ

public class Person {  // mutable class
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // hashCode от mutable полей!
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    public void setName(String name) {  // ОПАСНО как ключ!
        this.name = name;
    }
}

// Использование:
HashMap<Person, String> map = new HashMap<>();
Person key = new Person("Alice", 30);
map.put(key, "Alice data");

// Проблема:
key.setName("Bob");  // hashCode изменился!
map.get(key);  // null - данные потеряны!

ПРАВИЛЬНО: Immutable ключ

public final class ImmutablePerson {  // final класс
    private final String name;  // final поля
    private final int age;      // final поля
    
    public ImmutablePerson(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof ImmutablePerson)) return false;
        ImmutablePerson person = (ImmutablePerson) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    // НЕТ setters - объект неизменяем!
}

// Безопасное использование:
HashMap<ImmutablePerson, String> map = new HashMap<>();
ImmutablePerson key = new ImmutablePerson("Alice", 30);
map.put(key, "Alice data");
map.get(key);  // "Alice data" - всегда работает

Контракт HashMap

Документация Java явно требует:

Note that the use of mutable objects as key values is not recommended:
if the value of an object is changed and the object is used as a key
then the behavior of the hash table is undefined.

Техническая причина: Оптимизация

HashMap может кешировать hashCode():

public final class String {
    private final char[] value;
    private int hash;  // Кеширует hashCode
    
    public int hashCode() {
        int h = hash;
        if (h == 0) {
            // Вычисляем один раз
            h = computeHash();
            hash = h;
        }
        return h;  // Последующие вызовы вернут кешированное значение
    }
}

Благодаря immutable гарантии:

• Первый вызов hashCode() вычисляет значение
• Последующие вызовы вернут то же значение
• Производительность улучшается

Лучшие практики

// ДА: Использовать immutable типы как ключи
HashMap<String, String> map1 = new HashMap<>();
HashMap<Integer, String> map2 = new HashMap<>();
HashMap<LocalDate, String> map3 = new HashMap<>();

// ДА: Если нужен custom класс - сделай его final и immutable
public final class CustomKey {
    private final String id;      // final
    private final int version;    // final
    
    public String getId() { return id; }
    public int getVersion() { return version; }
}

// НЕТ: Не используй mutable объекты
public class BadKey {  // не final
    public String id;    // не final
    public int version;  // не final
    
    public void setId(String id) { this.id = id; }
}

Итоговое резюме

Ключи в HashMap ДОЛЖНЫ быть неизменяемы (immutable) потому что:

1. hashCode() не должен меняться - это основной контракт HashMap
2. Коррупция данных - если hashCode изменится, HashMap не найдёт ключ
3. Потеря данных - значения остаются в памяти, но недоступны
4. Race conditions - в многопоточной среде это приводит к нарушениям целостности
5. Производительность - immutable объекты позволяют кешировать hashCode
6. Предсказуемость - код с immutable ключами ведёт себя ожидаемо

Используй String, Integer, Long, UUID, LocalDate как ключи. Если нужен custom класс - сделай его final с final полями.