Что произойдет если в бакете HashMap уже есть другие элементы?

Коллизии в HashMap: что происходит при добавлении элемента в уже заполненный bucket

Это фундаментальный вопрос о внутреннем устройстве HashMap. Давайте разберёмся, как HashMap обрабатывает ситуацию, когда несколько элементов хешируются в один и тот же бакет.

Структура HashMap

HashMap использует массив bucket'ов (корзин). Каждый bucket может содержать несколько элементов. Размер массива определяется capacity (изначально 16 по умолчанию).

// Примерная структура
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private Node<K,V>[] table;  // массив bucket'ов

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

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

Разрешение коллизий: Chaining (Цепочка)

Java HashMap с Java 8+ использует метод цепочек (chaining):

// Структура bucket'а
// До Java 8: LinkedList
// Java 8+: LinkedList или красно-чёрное дерево (TreeNode)

public class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // указатель на следующий элемент в цепи
    
    // ...
}

Процесс добавления элемента в заполненный bucket

Шаг 1: Вычисление хеша

int hash = hash(key);
int index = hash & (table.length - 1);  // получаем индекс bucket'а

Шаг 2: Проверка наличия элемента с тем же ключом

Если в bucket'е уже есть элементы, HashMap проходит по цепи и проверяет каждый элемент:

Node<K,V> e = table[index];  // первый элемент в цепи
while (e != null) {
    if (e.hash == hash && (key == e.key || key.equals(e.key))) {
        // Найден элемент с тем же ключом
        V oldValue = e.value;
        e.value = value;  // обновляем значение
        return oldValue;
    }
    e = e.next;  // переходим к следующему элементу
}

Шаг 3: Добавление нового элемента в начало цепи

Если элемента с таким ключом нет, новый элемент добавляется в начало цепи (это более эффективно, чем в конец):

Node<K,V> newNode = new Node<>(hash, key, value, table[index]);
table[index] = newNode;  // новый узел становится первым
size++;

Java 8+: Оптимизация с использованием Tree

С Java 8 HashMap имеет умное улучшение. Если цепь в bucket'е становится слишком длинной (по умолчанию > 8 элементов), она преобразуется в красно-чёрное дерево (TreeNode):

// Константы
private static final int TREEIFY_THRESHOLD = 8;   // порог для преобразования в дерево
private static final int UNTREEIFY_THRESHOLD = 6; // порог для преобразования обратно
private static final int MIN_TREEIFY_CAPACITY = 64; // минимальная capacity для treeify

// Процесс
if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(table, hash);  // преобразуем LinkedList в Tree
}

Почему это нужно?

• Поиск в LinkedList: O(n) в худшем случае
• Поиск в Tree: O(log n) даже в худшем случае

Визуализация процесса

До добавления:
table[i] → Node1(hash=5, key="a") → Node2(hash=5, key="b") → null

Добавляем новый элемент с hash=5, key="c":
table[i] → Node3(hash=5, key="c") → Node1(hash=5, key="a") → Node2(hash=5, key="b") → null

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

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

// Оба ключа имеют хеш-код 5 (гипотетически)
map.put("apple", "яблоко");   // добавляется в bucket[5]
map.put("apricot", "абрикос"); // коллизия! добавляется в ту же цепь bucket[5]
map.put("avocado", "авокадо"); // ещё одна коллизия

// Структура в памяти:
// bucket[5] → avocado → apricot → apple → null

// При поиске:
String value = map.get("apricot");
// 1. Вычисляем хеш: hash("apricot") = 5
// 2. Получаем bucket[5]
// 3. Проходим по цепи: avocado? нет, apricot? ДА! Возвращаем "абрикос"

Резюме

• Коллизия — неизбежная ситуация при использовании HashMap
• HashMap решает коллизии методом цепочек (chaining)
• Элементы в одном bucket'е связаны в LinkedList
• Java 8+ оптимизирует длинные цепи, преобразуя их в красно-чёрные деревья
• При добавлении проверяется наличие элемента с тем же ключом (затем обновление или добавление)
• Новый элемент добавляется в начало цепи
• В среднем операции get/put имеют сложность O(1)
• В худшем случае (при деградации) — O(log n) благодаря оптимизации с деревьями