Определяется ли hashCode значения при добавлении элемента в HashMap

hashCode и HashMap

Коротко: Да, hashCode ВСЕГДА вычисляется при добавлении элемента в HashMap

Это основной механизм HashMap для определения bucketa, в который попадёт элемент.

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

Шаг 1: Вычисление hash-кода

Когда ты добавляешь элемент в HashMap:

Map<String, Integer> map = new HashMap<>();
map.put("hello", 1);

Сразу вычисляется hash-код ключа:

int hash = key.hashCode(); // вызов метода hashCode() на ключе

Шаг 2: Определение bucket index

int bucketIndex = hash & (table.length - 1);
// или: hash % table.length

HashMap использует bitwise операцию для определения индекса bucket-а в массиве.

Шаг 3: Обработка коллизий

Если hash-коды совпадают (collision), то используется equals() для проверки:

if (hash == existingHash && key.equals(existingKey)) {
    // Ключ уже существует, обновляем value
    existingValue = newValue;
} else {
    // Коллизия: добавляем в LinkedList или Red-Black дерево
    node.next = newNode;
}

Полный пример с объяснением

class Person {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int hashCode() {
        System.out.println("hashCode() вызван для " + name);
        return Objects.hash(name, age);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person other = (Person) obj;
        return age == other.age && Objects.equals(name, other.name);
    }
}

public class HashMapExample {
    public static void main(String[] args) {
        Map<Person, String> map = new HashMap<>();
        
        Person p1 = new Person("Alice", 25);
        Person p2 = new Person("Bob", 30);
        
        // hashCode() будет вызван для p1
        map.put(p1, "Developer");
        // Output: hashCode() вызван для Alice
        
        // hashCode() будет вызван для p2
        map.put(p2, "Manager");
        // Output: hashCode() вызван для Bob
        
        // hashCode() будет вызван для проверки, есть ли такой ключ
        map.put(new Person("Alice", 25), "Senior Developer");
        // Output: hashCode() вызван для Alice
        // Потом equals() проверит, что это тот же объект
    }
}

Когда ещё вычисляется hashCode

1. При get()

String value = map.get("hello");
// hashCode() вычисляется для определения bucket-а

2. При remove()

map.remove("hello");
// hashCode() вычисляется для поиска элемента

3. При containsKey()

if (map.containsKey("hello")) {
    // hashCode() вычисляется
}

Важные правила для hashCode/equals

Правило 1: Если equals() возвращает true, то hashCode должен быть одинаковый

// ✅ Правильно
class Student {
    private String id;
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Student)) return false;
        return id.equals(((Student) obj).id);
    }
    
    @Override
    public int hashCode() {
        return id.hashCode(); // используем то же поле
    }
}

// ❌ Неправильно (нарушает контракт)
class BadStudent {
    private String id;
    private String name;
    
    @Override
    public boolean equals(Object obj) {
        return id.equals(((Student) obj).id); // сравниваем только id
    }
    
    @Override
    public int hashCode() {
        return name.hashCode(); // но используем name!
    }
}

Правило 2: Неизменяемость ключей

// ✅ Правильно - используем String (immutable)
map.put("immutable", value);

// ❌ Опасно - изменяемый ключ
class MutableKey {
    private List<String> items = new ArrayList<>();
    
    @Override
    public int hashCode() {
        return items.hashCode(); // зависит от содержимого
    }
}

MutableKey key = new MutableKey();
map.put(key, "value");
key.items.add("new"); // OMG! hash изменился, потеряется элемент!

Performance: Почему это важно

// Хороший hashCode распределяет элементы равномерно
class GoodHash {
    private int value;
    
    @Override
    public int hashCode() {
        return value; // простой, быстрый
    }
}

// Плохой hashCode все элементы в один bucket
class BadHash {
    private String name;
    
    @Override
    public int hashCode() {
        return 1; // ВСЕ элементы в одном bucket! O(n) поиск
    }
}

HashMap внутри (упрощённо)

public V put(K key, V value) {
    // Шаг 1: вычисляем hash
    int hash = key.hashCode(); // ← ВСЕГДА вычисляется
    
    // Шаг 2: определяем bucket index
    int bucketIndex = hash & (table.length - 1);
    
    // Шаг 3: проверяем существующие элементы в bucket
    Entry entry = table[bucketIndex];
    while (entry != null) {
        if (entry.hash == hash && entry.key.equals(key)) {
            // Нашли существующий ключ, обновляем value
            V oldValue = entry.value;
            entry.value = value;
            return oldValue;
        }
        entry = entry.next;
    }
    
    // Шаг 4: добавляем новый элемент
    addEntry(hash, key, value, bucketIndex);
    return null;
}

Вывод

• hashCode() ВСЕГДА вычисляется при операциях с HashMap (put, get, remove)
• Это основной механизм для определения места хранения элемента
• Должен быть быстрым и обеспечивать равномерное распределение
• Контракт: если equals() true, то hashCode должен быть одинаковым
• Никогда не меняй hashCode объекта, пока он ключ в HashMap