Какие методы ключа вызываются при вставке в HashMap?

Методы ключа, вызываемые при вставке в HashMap

Это один из самых важных вопросов для понимания HashMap. При вставке элемента в HashMap вызываются критические методы ключа, от которых зависит корректная работа.

Методы, вызываемые при вставке

1. hashCode()

hashCode() — это первый и самый важный метод. HashMap использует его для определения индекса bucket'а, где будет храниться элемент.

public class CustomKey {
    private String id;
    
    @Override
    public int hashCode() {
        // Вызывается при каждой вставке/получении из HashMap
        System.out.println("hashCode() вызван");
        return id.hashCode();
    }
}

public class Main {
    public static void main(String[] args) {
        Map<CustomKey, String> map = new HashMap<>();
        CustomKey key = new CustomKey("key1");
        
        map.put(key, "value1");
        // Вывод: hashCode() вызван
        
        map.put(key, "value2");
        // Вывод: hashCode() вызван (ещё раз)
    }
}

Процесс:

1. HashMap вычисляет индекс: index = hash(key.hashCode()) & (capacity - 1)
2. Переходит к bucket'у с этим индексом
3. Если bucket пуст — вставляет элемент
4. Если bucket не пуст — проверяет существующие ключи (вызывает equals())

2. equals()

equals() — вызывается только если hashCode() вернул тот же значение, что и существующий ключ. Это проверка на точное совпадение.

public class CustomKey {
    private String id;
    
    @Override
    public int hashCode() {
        return id.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        // Вызывается только если hashCode совпадает
        System.out.println("equals() вызван");
        if (this == obj) return true;
        if (!(obj instanceof CustomKey)) return false;
        
        CustomKey other = (CustomKey) obj;
        return this.id.equals(other.id);
    }
}

public class Main {
    public static void main(String[] args) {
        Map<CustomKey, String> map = new HashMap<>();
        CustomKey key1 = new CustomKey("key1");
        CustomKey key2 = new CustomKey("key1");  // Другой объект, но equals = true
        
        map.put(key1, "value1");
        System.out.println("--- Вставляем ещё раз ---");
        map.put(key2, "value2");  // Перезапишет значение
        
        // Вывод:
        // hashCode() вызван
        // --- Вставляем ещё раз ---
        // hashCode() вызван
        // equals() вызван
        
        System.out.println(map.size());  // 1 (не 2!)
    }
}

Сценарии вызова методов

Сценарий 1: Новый ключ (разный hashCode)

Map<CustomKey, String> map = new HashMap<>();
CustomKey key1 = new CustomKey("key1");
CustomKey key2 = new CustomKey("key2");  // Другой hashCode

map.put(key1, "value1");
map.put(key2, "value2");

// Вывод (в порядке):
// hashCode() -> key1.hashCode() вычислен
// hashCode() -> key2.hashCode() вычислен
// equals() НЕ вызывается! (разные bucket'ы)

System.out.println(map.size());  // 2

Сценарий 2: Коллизия hashCode (одинаковый hashCode, разные объекты)

class BadKey {
    private String value;
    
    @Override
    public int hashCode() {
        return 42;  // Плохая реализация: всегда возвращает одно значение
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof BadKey)) return false;
        return this.value.equals(((BadKey) obj).value);
    }
}

Map<BadKey, String> map = new HashMap<>();
BadKey key1 = new BadKey("a");
BadKey key2 = new BadKey("b");

map.put(key1, "value1");
map.put(key2, "value2");

// Вывод:
// hashCode() -> 42
// hashCode() -> 42 (одинаковые!)
// equals() -> false (разные значения)
// Оба элемента добавлены в одном bucket'е

System.out.println(map.size());  // 2 (но они в одном bucket'е)

Сценарий 3: Перезапись (одинаковый hashCode и equals)

Map<CustomKey, String> map = new HashMap<>();
CustomKey key1 = new CustomKey("key1");
CustomKey key2 = new CustomKey("key1");  // equals() == true

map.put(key1, "value1");
map.put(key2, "value2");

// Вывод:
// hashCode() -> вычислен для key1
// hashCode() -> вычислен для key2 (одинаковые!)
// equals() -> true (это один и тот же ключ)
// Значение перезаписано!

System.out.println(map.size());  // 1
System.out.println(map.get(key1));  // "value2"

Правила реализации hashCode() и equals()

public class ProperKey {
    private String id;
    private int priority;
    
    @Override
    public boolean equals(Object obj) {
        // 1. Проверка идентичности
        if (this == obj) return true;
        
        // 2. Проверка null
        if (obj == null) return false;
        
        // 3. Проверка типа
        if (getClass() != obj.getClass()) return false;
        
        // 4. Сравнение всех полей, используемых в hashCode()
        ProperKey other = (ProperKey) obj;
        return Objects.equals(this.id, other.id) &&
               this.priority == other.priority;
    }
    
    @Override
    public int hashCode() {
        // Используй Objects.hash() для правильного хеширования
        // Включай ВСЕ поля, которые используются в equals()
        return Objects.hash(id, priority);
    }
}

Последствия неправильной реализации

Проблема 1: Изменение ключа после вставки

public class MutableKey {
    private String value;
    
    public void setValue(String value) {
        this.value = value;
    }
    
    @Override
    public int hashCode() {
        return value.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof MutableKey)) return false;
        return this.value.equals(((MutableKey) obj).value);
    }
}

Map<MutableKey, String> map = new HashMap<>();
MutableKey key = new MutableKey("key1");

map.put(key, "value1");
key.setValue("key2");  // ОШИБКА: изменили ключ!

// Теперь ключ находится в неправильном bucket'е
System.out.println(map.get(key));  // null (не найдёт!)
System.out.println(map.containsKey(key));  // false

Проблема 2: Несоответствие между hashCode() и equals()

public class BadImplementation {
    private String id;
    
    @Override
    public int hashCode() {
        return id.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        // ОШИБКА: equals() проверяет больше, чем hashCode()
        return this == obj;  // Только идентичность
    }
}

// Такой код нарушает contract HashMap
// Если hashCode() равны, но equals() false — проблемы!

Практический пример с отладкой

public class DebugExample {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        
        String key1 = new String("test");
        String key2 = new String("test");
        
        map.put(key1, "value1");
        System.out.println("key1.hashCode() = " + key1.hashCode());
        System.out.println("key2.hashCode() = " + key2.hashCode());
        System.out.println("key1.equals(key2) = " + key1.equals(key2));
        
        map.put(key2, "value2");
        
        System.out.println("map.size() = " + map.size());  // 1
        System.out.println("map.get(key1) = " + map.get(key1));  // value2
        
        // Вывод:
        // key1.hashCode() = 3556498
        // key2.hashCode() = 3556498
        // key1.equals(key2) = true
        // map.size() = 1
        // map.get(key1) = value2
    }
}

Выводы

При вставке в HashMap вызываются:

1. hashCode() — ВСЕГДА (для определения bucket'а)
2. equals() — ТОЛЬКО если существует ключ с одинаковым hashCode

Правила:

• Если equals() возвращает true, то hashCode() должен быть одинаковый
• Если hashCode() одинаковый, equals() может быть true или false
• Никогда не изменяй ключ после вставки в HashMap
• Используй immutable объекты как ключи
• Правильно реализуй оба метода вместе