Используешь ли equals при помещении элемента в бакет

equals и hashCode при вставке в HashMap

Ответ: Да, equals() используется, но не при вставке в bucket, а после поиска bucket'а по hashCode(), для проверки совпадения ключей в цепочке.

Как работает вставка в HashMap

Шаг 1: Вычисляем хеш (используется hashCode)

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);

// Внутри HashMap.put():
int hash = hash("apple".hashCode());  // hashCode() вызывается
int index = hash & (table.length - 1);  // индекс в массиве

Шаг 2: Смотрим в bucket по индексу

Массив buckets:
┌─────────┐
│ [0]     │ -> null (пусто)
├─────────┤
│ [1]     │ -> Node("apple", 5) -> null  <-- Здесь хранится
├─────────┤
│ [2]     │ -> null
└─────────┘

Шаг 3: Проверяем наличие ключа в цепочке (используется equals)

// Проходим по цепочке узлов в bucket'е
Node<K,V> node = table[index];
while (node != null) {
    // ЗДЕСЬ используется equals()!
    if (node.hash == hash && node.key.equals(key)) {
        // Ключ уже есть, обновляем значение
        node.value = value;
        return;
    }
    node = node.next;
}

// Ключа нет, добавляем новый узел
Node<K,V> newNode = new Node<>(hash, key, value);
newNode.next = table[index];
table[index] = newNode;

Граф работы HashMap.put()

put(key, value)
    |
    v
hashCode() вычисляется
    |
    v
находим index в массиве
    |
    v
доступ к bucket'у за O(1)
    |
    v
проходим по цепочке:
    |
    v
  equals() проверка для каждого узла в цепочке
    |
    v
если найден -> обновляем значение
если не найден -> добавляем новый узел

Полный пример

HashMap<String, Integer> map = new HashMap<>();

// Вставка 1
map.put("apple", 1);
// hashCode("apple") % 4 = 1
// bucket[1] -> ("apple", 1) -> null

// Вставка 2: ТОТ ЖЕ КЛЮЧ
map.put("apple", 2);
// hashCode("apple") % 4 = 1
// bucket[1] уже содержит ("apple", 1)
// equals("apple", "apple") = true  <- ИСПОЛЬЗУЕТСЯ equals
// Обновляем: bucket[1] -> ("apple", 2) -> null

// Вставка 3: КОЛЛИЗИЯ (другой ключ, одинаковый хеш)
map.put("apricot", 3);  // Предположим, hashCode = 1 тоже
// hashCode("apricot") % 4 = 1
// bucket[1] уже содержит узлы
// Проверяем: equals("apricot", "apple") = false
// Продолжаем цепочку, если есть
// Добавляем новый: bucket[1] -> ("apricot", 3) -> ("apple", 2) -> null

Почему hashCode() используется ДО equals()

Эффективность:

// hashCode() быстрая (O(1))
// equals() может быть медленная (O(n) для строк)

if (node.hash == hash && node.key.equals(key)) {
    //                ^^^^^^^^^^^^^^^^^^^^^
    // Сначала быстрая проверка хеша (обычно 32-битное число)
    // Потом медленная проверка equals (посимвольно для строк)
}

Оптимизация: если хеши разные, equals не вызывается вообще!

Контракт hashCode() и equals()

Очень важно соблюдать контракт при переопределении:

public class User {
    private int id;
    private String email;
    
    @Override
    public int hashCode() {
        return Objects.hash(id, email);
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        
        User user = (User) o;
        
        // ВАЖНО: use ВСЕ поля, которые используются в hashCode()
        return id == user.id && Objects.equals(email, user.email);
    }
}

Правило: Если equals() возвращает true для двух объектов, то hashCode() ДОЛЖЕН вернуть одинаковый хеш:

Если a.equals(b) == true
    ТО a.hashCode() == b.hashCode()  <- ГАРАНТИРОВАНО

Если a.hashCode() == b.hashCode()
    ТО a.equals(b) может быть true или false (коллизии!)

Плохой пример: нарушение контракта

public class BadUser {
    private String name;
    
    @Override
    public int hashCode() {
        return 1;  // ПЛОХО: всегда одинаковый хеш!
    }
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof BadUser)) return false;
        BadUser other = (BadUser) o;
        return name.equals(other.name);
    }
}

// Использование:
HashMap<BadUser, String> map = new HashMap<>();
BadUser user1 = new BadUser("Alice");
BadUser user2 = new BadUser("Bob");
BadUser user3 = new BadUser("Alice");

map.put(user1, "value1");
map.put(user2, "value2");
map.put(user3, "value3");  // user1.equals(user3) = true, обновит value1

// Все три попадут в один bucket (хеш = 1)
// Поиск будет O(n) вместо O(1)!

Хороший пример: правильная реализация

public class GoodUser {
    private int id;
    private String email;
    
    @Override
    public int hashCode() {
        return Objects.hash(id, email);
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        GoodUser goodUser = (GoodUser) o;
        return id == goodUser.id && 
               Objects.equals(email, goodUser.email);
    }
}

// Использование:
HashMap<GoodUser, String> map = new HashMap<>();
GoodUser user1 = new GoodUser(1, "alice@example.com");
GoodUser user2 = new GoodUser(2, "bob@example.com");
GoodUser user3 = new GoodUser(1, "alice@example.com");

map.put(user1, "value1");
map.put(user2, "value2");
map.put(user3, "value3");  // user1.equals(user3) = true, обновит value1

// Объекты распределяются по разным bucket'ам (разные хеши)
// Поиск O(1)
// HashSet содержит только 2 элемента

HashSet и исключение ConcurrentModificationException

Особенно важно при работе с HashSet:

HashSet<User> users = new HashSet<>();
User user = new User(1, "alice@example.com");
users.add(user);

// ПЛОХО: изменяем объект в сете!
user.setEmail("newemail@example.com");  // hashCode() теперь другой!

// Поиск сломан, контракт нарушен
boolean contains = users.contains(user);  // false (правильно, но неожиданно!)

Решение: используй immutable объекты в HashMap/HashSet или будь осторожен при изменениях.

Итог

1. hashCode() используется для нахождения bucket'а (индекс в массиве)
2. equals() используется для проверки совпадения ключа внутри цепочки
3. Оба нужны для корректной работы HashMap
4. Контракт: если equals = true, то hashCode должен быть одинаковым
5. Коллизии неизбежны, но редкие при хорошем hashCode()
6. Никогда не изменяй объекты, которые используются как ключи в HashMap/HashSet