Для чего используют массив связанных списков в HashMap?

# Массив связанных списков в HashMap

Это фундаментальный вопрос о внутреннем устройстве HashMap. Давайте разберемся, почему именно эта структура используется.

Основная идея

HashMap использует массив bucket-ов (корзин), где каждый bucket — это связанный список. Это гибридная структура.

Почему нужна связанная структура

Hashing не гарантирует, что разные объекты получат разные хеши. Это называется hash collision (коллизия).

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

String key1 = "Aa";   // hashCode = 2080
String key2 = "BB";   // hashCode = 2080 тоже!

Если бы HashMap использовала просто массив без списков, второе значение перезапишет первое. Нам нужна структура, которая может хранить несколько значений в одной ячейке.

Решение: Связанный список в bucket-е

HashMap хранит в каждом bucket-е не одно значение, а связанный список:

class Entry {
    int hash;
    Object key;
    Object value;
    Entry next;  // Ссылка на следующий элемент
}

Если два ключа имеют одинаковый hash, они попадают в один bucket и образуют цепь: Entry1 -> Entry2 -> Entry3.

Процесс получения значения

V get(Object key) {
    int hash = hash(key.hashCode());
    int index = hash % table.length;
    
    // Идем по связанному списку в bucket-е
    Entry entry = table[index];
    while (entry != null) {
        if (entry.hash == hash && entry.key.equals(key)) {
            return entry.value;
        }
        entry = entry.next;
    }
    
    return null;
}

Сложность операций

Best case (нет коллизий): O(1) — прямой доступ к bucket-у Worst case (все в одном bucket-е): O(n) — нужно пройти весь список

Java 8+ улучшение: Red-Black Tree

Если в одном bucket-е больше 8 элементов, HashMap преобразует список в красно-черное дерево. Это дает O(log n) вместо O(n) в worst case.

Почему именно связанный список

Плюсы:

• Простая структура для коллизий
• Динамический размер (не фиксированный)
• Легко добавлять/удалять элементы

Минусы:

• Cache miss (плохая локальность памяти)
• Дополнительная память на ссылку

Load Factor и Resize

Чтобы минимизировать коллизии, HashMap увеличивает размер массива, когда заполненность (load factor) превышает 0.75:

if (size / capacity > 0.75) {
    // Resize: новый массив в 2 раза больше
    // Все Entry переходят в новые bucket-ы
}

Выводы

1. Связанный список решает проблему hash collisions
2. Массив обеспечивает быстрый доступ O(1) к bucket-у
3. Комбинация дает O(1) average и O(log n) worst case
4. Load factor контролирует баланс между памятью и коллизиями

Эта архитектура — один из самых элегантных решений в программировании.