Что такое коллизия HashCode с точки зрения HashMap?

# Коллизии HashCode в HashMap

Коллизия (hash collision) — это ситуация, когда два разных объекта производят одинаковый хеш-код. Это нормальное явление в любой хеш-таблице и HashMap имеет механизмы для их разрешения.

Основы работы HashMap

HashMap использует массив "корзин" (buckets) фиксированного размера:

public class HashMap<K, V> {
    // Массив корзин (обычно 16 по умолчанию)
    private Node<K,V>[] table;
    private int capacity; // размер массива
    
    public V put(K key, V value) {
        // 1. Вычисляем индекс: hashCode % capacity
        int hash = hash(key.hashCode());
        int index = hash & (capacity - 1); // эквивалент % capacity
        
        // 2. Помещаем в корзину по индексу
        table[index] = new Node(key, value);
    }
    
    public V get(Object key) {
        int hash = hash(key.hashCode());
        int index = hash & (capacity - 1);
        
        // 3. Ищем в корзине
        Node<K,V> node = table[index];
        while(node != null) {
            if(node.key.equals(key)) {
                return node.value;
            }
            node = node.next;  // проверяем следующие элементы
        }
        return null;
    }
}

Что происходит при коллизии

Пример коллизии

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

// Примеры двух объектов с одинаковым hashCode
// (гипотетически, в реальности маловероятно)
public class Custom {
    int value;
    
    @Override
    public int hashCode() {
        return 42; // всегда одинаковый хеш
    }
    
    @Override
    public boolean equals(Object o) {
        return this == o;
    }
}

Map<Custom, String> map = new HashMap<>();
Custom key1 = new Custom(1);
Custom key2 = new Custom(2);

map.put(key1, "first");  // hashCode = 42, index = 0
map.put(key2, "second"); // hashCode = 42, index = 0 — КОЛЛИЗИЯ!

Разрешение коллизии: Chaining (до Java 8)

В каждой корзине хранится цепочка элементов (linked list):

// Узел в HashMap
private static class Node<K,V> {
    int hash;
    K key;
    V value;
    Node<K,V> next;  // указатель на следующий элемент
}

// При коллизии:
// table[0] -> Node(key1, "first") -> Node(key2, "second") -> null

// При поиске проходим по цепочке:
public V get(Object key) {
    int index = hash(key) & (capacity - 1);
    Node<K,V> node = table[index];
    
    while(node != null) {
        if(node.hash == hash && (key == node.key || key.equals(node.key))) {
            return node.value;
        }
        node = node.next;  // ← идём по цепочке при коллизии
    }
    return null;
}

Оптимизация: Tree-based buckets (Java 8+)

Если в корзине много элементов (обычно > 8), HashMap конвертирует цепочку в красно-чёрное дерево:

// Java 8+ оптимизация
private static final int TREEIFY_THRESHOLD = 8;
private static final int UNTREEIFY_THRESHOLD = 6;

// При добавлении 9-го элемента в корзину:
if(binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash); // преобразуем цепочку в дерево
}

// Это улучшает производительность при поиске:
// Цепочка: O(n) — нужно пройти все элементы
// Дерево: O(log n) — бинарный поиск

Визуализация

Без коллизии

index  bucket
  0    [key1 → value1]
  1    [key2 → value2]
  2    [null]
  3    [key3 → value3]

Коллизия (цепочка)

index  bucket
  0    [key1 → value1] → [key4 → value4] → [key7 → value7] → null
  1    [key2 → value2]
  2    [null]
  3    [key3 → value3]

Коллизия (дерево, Java 8+)

index  bucket (8 элементов)
  0         [root]
           /    \
        key1   key4
       /   \   / \
    key7 key2 key5 ...

Влияние на производительность

// Идеальный случай (без коллизий)
// Каждая корзина содержит ≤ 1 элемент
// get/put: O(1) в среднем
Map<Integer, String> map = new HashMap<>();
for(int i = 0; i < 1000; i++) {
    map.put(i, "value" + i);
}
String value = map.get(500); // быстро

// Плохой случай (много коллизий)
public class BadHash {
    @Override
    public int hashCode() {
        return 0; // все элементы в одной корзине!
    }
}

Map<BadHash, String> map = new HashMap<>();
for(int i = 0; i < 1000; i++) {
    map.put(new BadHash(), "value" + i);
}
// Все 1000 элементов в одной корзине
// get/put: O(n) — почти как LinkedList

Load Factor и rehashing

HashMap автоматически расширяется при заполнении:

private static final float DEFAULT_LOAD_FACTOR = 0.75f;

public V put(K key, V value) {
    // ... добавляем элемент
    
    if(++size > capacity * loadFactor) {
        resize(); // увеличиваем capacity в 2 раза
    }
}

// При resize() все элементы перехешируются в новый массив
// Это уменьшает коллизии, но требует O(n) времени

Почему 0.75?

size / capacity = 0.75

// С вероятностной точки зрения это оптимум:
// - При меньшем коэффициенте: мало коллизий, но много памяти
// - При большем коэффициенте: экономия памяти, но много коллизий и rehashing

Правильная реализация hashCode/equals

public class Person {
    private String name;
    private int age;
    
    // ❌ Плохо
    @Override
    public int hashCode() {
        return 0; // все объекты имеют одинаковый хеш — много коллизий!
    }
    
    // ✅ Хорошо
    @Override
    public int hashCode() {
        return Objects.hash(name, age); // использует поля
    }
    
    @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);
    }
}

// ПРАВИЛО: если equals() говорит два объекта равны,
// то hashCode() должен вернуть одинаковый хеш!
// Но обратное не обязательно — hashCode может совпадать для разных объектов

Контракт hashCode/equals

// ✅ Правильно
Person p1 = new Person("John", 30);
Person p2 = new Person("John", 30);

if(p1.equals(p2)) {  // true
    assert p1.hashCode() == p2.hashCode(); // тоже true
}

Map<Person, String> map = new HashMap<>();
map.put(p1, "value1");
String found = map.get(p2); // найдёт, потому что equals() и hashCode() согласованы
assert found.equals("value1");

// ❌ Неправильно
public class BadPerson {
    public boolean equals(Object o) {
        return name.equals(((BadPerson)o).name);
    }
    public int hashCode() {
        return age; // не основано на name!
    }
}
// Два объекта с одинаковым name могут быть найдены неправильно

Заключение

1. Коллизия — нормальное явление в хеш-таблицах
2. Разрешение — цепочка элементов (до Java 8) или дерево (Java 8+)
3. Производительность — O(1) в среднем, O(n) в худшем (плохой hashCode())
4. Оптимизация — rehashing при load factor > 0.75
5. Контракт — hashCode() и equals() должны быть согласованы
6. Практика — используй Objects.hash() и Objects.equals()