Что такое Коллизия?

Коллизия в структурах данных

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

Почему возникают коллизии?

Хеш-функция преобразует ключ в индекс массива конечного размера. Поскольку количество возможных ключей может быть намного больше, чем размер массива, неизбежно возникают ситуации, когда разные ключи генерируют одинаковый хеш.

// Пример коллизии
Map<String, Integer> map = new HashMap<>();
String key1 = "AB";
String key2 = "BA";

// В Java могут совпадать hashCode() для разных объектов
System.out.println(key1.hashCode()); // Может быть 2032
System.out.println(key2.hashCode()); // Может быть 2032

Методы разрешения коллизий

1. Chaining (Цепочки) — используется в HashMap

При коллизии элементы хранятся в связной цепочке. Java 8+ использует красно-чёрные деревья для больших цепочек.

Map<Integer, String> map = new HashMap<>();
map.put(1, "first");
map.put(1, "second"); // Перепишет значение

// Внутренне: массив Node<K,V>[]
// Каждая ячейка может содержать цепь элементов
// Node -> Node -> Node (если коллизии)

2. Open Addressing (Открытая адресация)

При коллизии ищется следующая свободная ячейку в массиве:

// Линейный поиск (linear probing)
int index = hash(key);
while (array[index] != null) {
    index = (index + 1) % arraySize;
}
array[index] = value;

3. Double Hashing (Двойное хеширование)

Используется вторая хеш-функция для перемещения по таблице.

Как Java обрабатывает коллизии в HashMap

HashMap использует метод chaining:

// Упрощённая структура HashMap
private static final int CAPACITY = 16;
private Node<K,V>[] table = new Node[CAPACITY];

private static class Node<K,V> {
    K key;
    V value;
    Node<K,V> next; // Ссылка на следующий элемент при коллизии
}

public V put(K key, V value) {
    int index = hash(key.hashCode()) % table.length;
    Node<K,V> node = table[index];
    
    while (node != null) {
        if (node.key.equals(key)) {
            V old = node.value;
            node.value = value;
            return old;
        }
        node = node.next; // Переходим к следующему элементу в цепи
    }
    
    // Добавляем новый узел в начало цепи
    Node<K,V> newNode = new Node<>(key, value, table[index]);
    table[index] = newNode;
    return null;
}

Оптимизация в Java 8+

При большом количестве коллизий (цепь > 8 элементов) HashMap преобразует цепочку в красно-чёрное дерево для лучшей производительности (O(log n) вместо O(n)):

private static final int TREEIFY_THRESHOLD = 8;

private void treeifyBin(Node<K,V>[] tab, int hash) {
    TreeNode<K,V> hd = null, tl = null;
    // Преобразование цепи в дерево
    for (Node<K,V> e = tab[index]; e != null; e = e.next) {
        TreeNode<K,V> p = new TreeNode<>(e.hash, e.key, e.value, null);
        if (tl == null) hd = p;
        else {
            p.prev = tl;
            tl.next = p;
        }
        tl = p;
    }
}

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

• Хорошее распределение (мало коллизий): O(1) для get/put
• Плохое распределение (много коллизий): O(n) в худшем случае
• Load Factor: отношение количества элементов к размеру таблицы (по умолчанию 0.75)
• При превышении load factor HashMap автоматически увеличивает размер в 2 раза (rehashing)

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

1. Переопределяй hashCode() корректно:

@Override
public int hashCode() {
    return Objects.hash(field1, field2); // Используй Objects.hash()
}

@Override
public boolean equals(Object o) {
    if (!(o instanceof MyClass)) return false;
    MyClass other = (MyClass) o;
    return Objects.equals(field1, other.field1) &&
           Objects.equals(field2, other.field2);
}

1. Не полагайся на порядок итерации при коллизиях
2. Выбирай правильную структуру: LinkedHashMap (сохраняет порядок), ConcurrentHashMap (потокобезопасная)

Коллизии — это естественная часть работы хеш-таблиц, и современные реализации в Java (особенно HashMap) хорошо их обрабатывают.