Когда теряется объект в HashMap?

HashMap: когда теряются объекты

Проблема с изменяемыми ключами

Объект теряется в HashMap когда изменяется значение hashCode() после добавления ключа. HashMap использует hashCode() для расчёта позиции в таблице, поэтому изменение хэша превращает объект в "невидимку".

Механизм работы HashMap

public class HashMap<K, V> {
    Node<K, V>[] table;  // Массив бакетов
    
    public V put(K key, V value) {
        // 1. Вычисляем хэш ключа
        int hash = hash(key.hashCode());
        
        // 2. Вычисляем индекс в массиве
        int index = hash & (table.length - 1);
        
        // 3. Добавляем в таблицу
        table[index].put(key, value);
    }
    
    public V get(Object key) {
        // 1. Вычисляем хэш ключа
        int hash = hash(key.hashCode());
        
        // 2. Вычисляем индекс в массиве
        int index = hash & (table.length - 1);
        
        // 3. Ищем в таблице
        return table[index].get(key);
    }
}

Классический пример проблемы

public class Person {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    // ❌ ОШИБКА: hashCode зависит от изменяемого поля
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Person)) return false;
        Person other = (Person) obj;
        return Objects.equals(this.name, other.name) && this.age == other.age;
    }
    
    // Setter нарушает контракт HashMap
    public void setAge(int age) {
        this.age = age;
    }
}

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

map.put(person, "Engineer");  // hashCode = hash(Alice, 30)
system.out.println(map.get(person));  // ✓ "Engineer"

person.setAge(31);  // hashCode изменился!
system.out.println(map.get(person));  // ❌ null — объект "потерялся"!

Почему объект потерялся

Шаг 1: Добавляем (Alice, 30)
    hash(Alice, 30) = 1234
    index = 1234 & (capacity - 1) = 5
    table[5] = (Alice, 30, Engineer)

Шаг 2: Изменяем возраст на 31
    person.age = 31
    person.hashCode() = hash(Alice, 31) = 5678
    index = 5678 & (capacity - 1) = 12

Шаг 3: Ищем get(person)
    hash(Alice, 31) = 5678
    index = 5678 & (capacity - 1) = 12
    table[12] = пусто
    Возвращаем null
    
Объект остался в table[5], но мы ищем в table[12]!

Правильное решение: immutable ключи

// ✓ Правильный подход: неизменяемый Person
public class Person {
    private final String name;  // final
    private final int age;      // final
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Person)) return false;
        Person other = (Person) obj;
        return Objects.equals(this.name, other.name) && this.age == other.age;
    }
    
    // Нет setters!
}

// Использование
Map<Person, String> map = new HashMap<>();
Person person1 = new Person("Alice", 30);
map.put(person1, "Engineer");
system.out.println(map.get(person1));  // ✓ "Engineer"

// Если нужно изменить — создаём новый объект
Person person2 = new Person("Alice", 31);
system.out.println(map.get(person2));  // null (это другой человек)
map.put(person2, "Senior Engineer");

Использование String в качестве ключа

String безопасен как ключ HashMap, потому что он immutable:

Map<String, Integer> frequencies = new HashMap<>();

String word = "Java";
frequencies.put(word, 1);  // hashCode вычислен один раз
system.out.println(frequencies.get(word));  // ✓ 1

// String нельзя изменить
word = word.toLowerCase();  // Создаётся новый объект
system.out.println(frequencies.get(word));  // null

Опасные примеры

Mutable ключи: массив

// ❌ ОПАСНО: массив как ключ
Map<int[], String> map = new HashMap<>();
int[] array = {1, 2, 3};

map.put(array, "data");
system.out.println(map.get(array));  // ✓ "data"

array[0] = 999;  // Изменили массив!
system.out.println(map.get(array));  // Может быть null!

Mutable ключи: коллекции

// ❌ ОПАСНО: List как ключ
Map<List<Integer>, String> map = new HashMap<>();
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));

map.put(list, "data");
system.out.println(map.get(list));  // ✓ "data"

list.add(4);  // Изменили список!
system.out.println(map.get(list));  // ❌ null

Эффект каскадного теряния

public class Container {
    private Map<MutableKey, String> data = new HashMap<>();
    
    public void storeData(MutableKey key, String value) {
        data.put(key, value);  // Ключ добавлен
    }
    
    public String retrieve(MutableKey key) {
        return data.get(key);  // Может вернуть null после изменения ключа
    }
    
    public int countValues() {
        return data.values().stream()
            .distinct()  // Потеряли доступ к значениям!
            .collect(Collectors.toList())
            .size();
    }
}

Контракт для ключей HashMap

Основной контракт: если equals вернул true для двух объектов, их hashCode должны быть одинаковыми.

// Правило для equals и hashCode
if (a.equals(b)) {
    assert a.hashCode() == b.hashCode();
}

Если ключ изменяется, этот контракт нарушается.

Практические рекомендации

✓ Используй неизменяемые объекты (String, Integer, другие immutable классы)
✓ Создавай свои immutable ключи с final полями
✓ Если hashCode зависит от полей — сделай эти поля final
✓ Избегай mutable объектов как ключей (массивы, списки)
✓ Для изменяющихся данных используй WeakHashMap или другие структуры

Вывод

Объект теряется в HashMap при изменении hashCode() после добавления. Решение: использовать immutable ключи с final полями и делать hashCode() и equals() зависимыми только от неизменяемых полей.