Что будет в HashMap при коллизии?

Механизм обработки коллизий в HashMap

При возникновении коллизии в HashMap (когда два или более разных ключа имеют одинаковый хэш-код по модулю размера таблицы), Java реализует механизм разрешения коллизий через цепочки (chaining). Сейчас в основном используется подход с Node<K,V>, но в более старых версиях и в некоторых случаях может применяться переход к деревьям.

Основная структура: массив бакетов (buckets)

HashMap внутри представляет собой массив Node<K,V>[] table. Каждый элемент массива — это бакет, который может содержать:

• null — пустой бакет.
• Один Node — если нет коллизий.
• Цепочку Nodes или бинарное дерево — при коллизии.

// Внутренняя структура Node (до Java 8)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Ссылка на следующий Node в цепочке
}

Процесс при коллизии (chaining)

Когда два ключа попадают в один бакет (например, hash(key1) % capacity == hash(key2) % capacity), новый Node добавляется в существующую цепочку. Это классический односвязный список.

Пример коллизии и вставки:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1); // hash("key1") вычисляется, Node создается в бакете[index]
map.put("key2", 2); // hash("key2") совпадает по модулю с hash("key1") -> коллизия

Внутри бакета теперь будет цепочка:

Бакет[index] -> Node("key1", 1, next=Node("key2", 2, next=null))

При поиске (get(key)):

1. Вычисляется хэш и индекс бакета.
2. Если в бакете цепочка, происходит последовательный (O(n) для списка) поиск по ключу, используя сначала сравнение хэшей, затем equals() ключей.

Оптимизация в Java 8: переход от списка к дереву

Чтобы избежать деградации до O(n) при длинных цепочках (например, из-за плохого хэширования), в Java 8 добавлена оптимизация: при достижении определенного порога длины цепочки (параметр TREEIFY_THRESHOLD = 8) и при условии, что общее количество элементов в таблице превышает MIN_TREEIFY_CAPACITY = 64, цепочка преобразуется из односвязного списка в сбалансированное бинарное дерево (TreeNode).

// TreeNode для дерева (Java 8+)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

Преимущество дерева: поиск в длинной цепочке становится O(log n) вместо O(n). Условие: ключи должны быть Comparable (или будет использоваться специальный порядок), чтобы дерево могло быть построено.

Последовательность работы при коллизии

1. Вставка (put()):

    *   Вычисляется `hash(key)` и индекс бакета `i`.
    *   Если бакет `table[i]` пуст — создается новый `Node`.
    *   Если уже есть `Node` — проверяется коллизия: сравниваются хэши и ключи (через `equals()`).
        *   Если ключ совпадает — значение обновляется.
        *   Если ключ новый — добавляется новый `Node` в цепочку/дерево этого бакета.

1. Поиск (get()):

    *   Вычисляется индекс бакета.
    *   Если в бакете цепочка — линейный поиск по `equals()`.
    *   Если в бакете дерево — поиск через сравнение (`compareTo()` или системный порядок).

1. Удаление (remove()):

    *   Похоже на поиск: находится нужный `Node` в цепочке/дереве и удаляется с соответствующей реструктуризацией списка/дерева.

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

• Идеальный случай (без коллизий): операции O(1).
• Небольшие коллизии (короткие цепочки): практически O(1).
• Множественные коллизии без оптимизации: производительность падает до O(n).
• С оптимизацией дерева (Java 8+): падение до O(log n).

Ключевые параметры, влияющие на коллизии:

• initialCapacity и loadFactor — определяют размер таблицы и момент ресайза.
• Качество хэш-функции ключа — хорошая hashCode() минимизирует коллизии.

Таким образом, при коллизии в HashMap элементы организуются в цепочку (односвязный список) внутри одного бакета, а в современных версиях Java при определенных условиях цепочка может быть преобразована в бинарное дерево для сохранения производительности операций поиска, вставки и удаления.