Как устроена HashMap внутри? Что происходит при коллизии?

Как устроена HashMap внутри? Что происходит при коллизии?

HashMap — это одна из самых часто используемых структур данных в Java. Её эффективность зависит от сложного механизма хэширования и разрешения коллизий. Понимание внутреннего устройства HashMap критически важно для написания эффективного кода.

Базовая архитектура HashMap

HashMap использует массив (bucket array) связанных списков для хранения пар ключ-значение. Основной компонент — это массив buckets, где каждый bucket может содержать один или несколько элементов.

public class HashMap<K, V> {
    // Массив buckets
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    Node<K, V>[] table;
    
    // Параметр нагрузки
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // Количество элементов
    int size;
}

Процесс добавления элемента (put)

Когда вы добавляете элемент в HashMap, происходят следующие шаги:

1. Вычисление хэша: hash(key) вычисляет хэш-код ключа
2. Определение индекса: index = hash(key) % table.length
3. Помещение в bucket: Элемент добавляется в соответствующий bucket

public V put(K key, V value) {
    // Вычисляем хэш ключа
    int hash = hash(key);
    
    // Определяем индекс в массиве
    int index = hash & (table.length - 1); // Эквивалентно hash % table.length
    
    // Получаем bucket по индексу
    Node<K, V> node = table[index];
    
    // Проходим по цепочке (в случае коллизии)
    while (node != null) {
        if (node.hash == hash && (key == node.key || key.equals(node.key))) {
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        node = node.next;
    }
    
    // Добавляем новый узел
    addToHead(index, key, value, hash);
    size++;
    
    // Проверяем необходимость расширения
    if (size > table.length * loadFactor) {
        resize();
    }
    
    return null;
}

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

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

public class HashMap<K, V> {
    // Узел цепочки (связный список)
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
        
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
}

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

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

// Предположим, что "John" и "Jane" имеют одинаковый хэш
map.put("John", 30);  // bucket[5] -> Node("John", 30)
map.put("Jane", 25);  // bucket[5] -> Node("Jane", 25) -> Node("John", 30)
map.put("Bob", 35);   // bucket[7] -> Node("Bob", 35)

System.out.println(map.get("Jane")); // 25 - находится в цепочке
System.out.println(map.get("John")); // 30 - находится в цепочке

Преобразование в красно-чёрное дерево (TreeNode)

Начиная с Java 8, HashMap оптимизирован для больших цепочек коллизий. Когда цепочка в одном bucket становится слишком длинной (8 элементов), она преобразуется в сбалансированное красно-чёрное дерево.

public class HashMap<K, V> {
    static final int TREEIFY_THRESHOLD = 8;  // Преобразование в дерево
    static final int UNTREEIFY_THRESHOLD = 6; // Преобразование обратно в список
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // Процесс treeification
    private void treeifyBin(Node<K, V>[] tab, int hash) {
        int n, index;
        Node<K, V> e;
        
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
            resize(); // Расширяем массив вместо treeification
        } else if ((e = tab[index = (n - 1) & hash]) != null) {
            // Преобразуем цепочку в дерево
            TreeNode<K, V> hd = null, tl = null;
            do {
                TreeNode<K, V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
}

Преимущества дерева над списком:

• Поиск в дереве: O(log n) вместо O(n) в списке
• Более эффективно при большом количестве коллизий

Расширение (Resize) HashMap

Когда количество элементов превышает capacity * loadFactor, HashMap расширяется (по умолчанию в 2 раза).

final Node<K, V>[] resize() {
    Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // Новая ёмкость = старая * 2
        newCap = oldCap << 1; // oldCap * 2
    } else {
        newCap = DEFAULT_INITIAL_CAPACITY;
    }
    
    // Пересчитываем пороги
    newThr = (int)(newCap * loadFactor);
    
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    table = newTab;
    threshold = newThr;
    
    // Переразмещаем все элементы из старого массива
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                do {
                    Node<K, V> next = e.next;
                    int newIndex = e.hash & (newCap - 1);
                    e.next = newTab[newIndex];
                    newTab[newIndex] = e;
                    e = next;
                } while (e != null);
            }
        }
    }
    
    return newTab;
}

Факторы, влияющие на производительность

1. Коэффициент нагрузки (Load Factor)

• По умолчанию 0.75
• Баланс между использованием памяти и частотой коллизий
• Меньший коэффициент = меньше коллизий, но больше памяти

2. Качество хэш-функции

• Равномерное распределение значений по buckets
• Минимизация коллизий

public class Example {
    public static void main(String[] args) {
        // Создание HashMap с заранее известной ёмкостью
        // Уменьшает количество resizes
        HashMap<String, Integer> map = new HashMap<>(100);
        
        for (int i = 0; i < 1000; i++) {
            map.put("key" + i, i);
        }
    }
}

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

Основной вывод: HashMap крайне эффективна благодаря сочетанию хэширования, разрешения коллизий через цепочки/деревья и расширения при необходимости.