Как работает вставка в Map?

Как работает вставка в HashMap: полный разбор

Понимание механизма вставки в HashMap критично для собеседования и оптимизации кода. Это основывается на концепции хеширования и решении коллизий.

Общий процесс вставки

Когда вы вызываете map.put(key, value), происходит следующее:

1. Вычисление хеша — вычисляется хеш-код ключа
2. Определение индекса — хеш маппируется на индекс в массиве
3. Поиск ячейки — проверяется содержимое этой ячейки
4. Разрешение коллизии — если там уже что-то есть, разрешается конфликт
5. Вставка или обновление — добавляется новая пара или обновляется существующая

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

// В классе HashMap происходит что-то вроде этого:
public V put(K key, V value) {
    if (key == null) {
        return putForNullKey(value);  // Null-ключи имеют специальную обработку
    }
    
    // Вычисляем хеш код ключа
    int hash = hash(key);
    
    // Дальше используем этот хеш...
}

// Метод hash() перемешивает биты для лучшего распределения
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Важно: хеш-код может быть любым числом (включая отрицательные). Он не напрямую используется как индекс.

Шаг 2: Определение индекса

// Индекс определяется как модуль от длины массива
int index = hash & (length - 1);  // Эквивалент hash % length, но быстрее

// Пример:
int hash = 15;
int length = 16;  // Длина всегда степень 2
int index = 15 & (16 - 1);  // 15 & 15 = 15

// Битовый AND работает быстрее чем модуль

Зачем длина степень 2? Потому что побитовое AND на степени 2 эквивалентно модулю и работает намного быстрее.

Шаг 3: Разрешение коллизий через цепочки (Separate Chaining)

Это основной механизм в Java 7 и ранее:

// Каждая ячейка содержит цепочку (список) пар ключ-значение
static class Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;  // Указатель на следующий элемент в цепочке
    int hash;
}

// При вставке:
// 1. Идём на позицию с индексом index
// 2. Проходим по цепочке, сравнивая ключи
// 3. Если нашли совпадение — обновляем значение
// 4. Если не нашли — добавляем в начало цепочки

Визуально:

indexArray:
[0] -> key1 -> key4 -> key7  // цепочка из 3 элементов
[1] -> key2 -> null
[2] -> null
[3] -> key3 -> key6 -> null
...

Шаг 4: Java 8+ Оптимизация - Red-Black Tree

В Java 8 добавлена оптимизация: если цепочка слишком длинная (> TREEIFY_THRESHOLD = 8), она преобразуется в красно-чёрное дерево:

static final int TREEIFY_THRESHOLD = 8;   // Превратить в дерево, если > 8
static final int UNTREEIFY_THRESHOLD = 6; // Вернуть цепочку, если < 6

// Это улучшает производительность при плохом распределении хешей
// Цепочка: O(n) поиск
// Дерево: O(log n) поиск

Полный пример вставки

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        // Вставка 1: "apple" -> 5
        map.put("apple", 5);
        // 1. hash("apple") = 95345062
        // 2. index = 95345062 & (capacity - 1) = 2 (если capacity = 16)
        // 3. map[2] пусто, вставляем
        
        // Вставка 2: "banana" -> 3 (коллизия)
        map.put("banana", 3);
        // 1. hash("banana") = -1234567 (гипотетически)
        // 2. index = -1234567 & 15 = 2 (КОЛЛИЗИЯ!)
        // 3. map[2] уже занято, добавляем в цепочку
        // map[2] -> banana -> apple -> null
        
        // Вставка 3: обновление
        map.put("apple", 10);
        // 1. hash("apple") = 95345062
        // 2. index = 2
        // 3. Проходим цепочку, находим "apple"
        // 4. Обновляем значение 5 -> 10
    }
}

Процесс Rehashing (увеличение размера)

Когда HashMap заполняется слишком сильно, она увеличивается в размере:

public HashMap(int initialCapacity, float loadFactor) {
    this.loadFactor = loadFactor;  // По умолчанию 0.75
    this.threshold = initialCapacity * loadFactor;
    // Если количество элементов превышает threshold, происходит resize
}

// При resize:
// 1. Создаётся новый массив большего размера (обычно в 2 раза)
// 2. Все элементы переуправляются (пересчитываются индексы)
// 3. Это дорогая операция O(n)

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) {
        newCap = oldCap << 1;  // Удваиваем размер (oldCap * 2)
    } else {
        newCap = DEFAULT_INITIAL_CAPACITY;  // 16
    }
    
    // Пересчитываем threshold для новой capacity
    newThr = (int)(newCap * loadFactor);
    threshold = newThr;
    
    // Создаём новый массив
    Node<K,V>[] newTab = new Node[newCap];
    table = newTab;
    
    // Перекопируем все элементы
    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;
}

Полный код put() в Java 16+

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // Инициализируем таблицу если нужно
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // Вычисляем индекс и проверяем ячейку
    if ((p = tab[i = (n - 1) & hash]) == null)
        // Пусто, создаём новый узел
        tab[i] = newNode(hash, key, value, null);
    else {
        // Ячейка занята, разрешаем коллизию
        Node<K,V> e; K k;
        
        // Проверяем первый узел
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;  // Найдено, обновим позже
        
        // Если это дерево, добавляем как в дерево
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // Иначе проходим по цепочке
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // Не найдено, добавляем в конец
                    p.next = newNode(hash, key, value, null);
                    
                    // Если цепочка слишком длинная, превращаем в дерево
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                
                // Проверяем этот узел
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;  // Найдено!
                
                p = e;
            }
        }
        
        // Обновляем значение если ключ уже был
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    ++modCount;  // Увеличиваем счётчик модификаций
    
    // Проверяем, нужен ли resize
    if (++size > threshold)
        resize();
    
    afterNodeInsertion(evict);
    return null;  // Новое значение
}

Временная сложность

Лучший случай: идеальное распределение хешей Средний: хороший хеш-код и разумный load factor Худший: все элементы хешируются в одну ячейку (до Java 8) или O(log n) с деревом (Java 8+)

Важные константы

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // 16
static final int MAXIMUM_CAPACITY = 1 << 30;        // 1 млрд
static final float DEFAULT_LOAD_FACTOR = 0.75f;     // 75%
static final int TREEIFY_THRESHOLD = 8;            // Превратить в дерево
static final int UNTREEIFY_THRESHOLD = 6;          // Вернуть цепочку
static final int MIN_TREEIFY_CAPACITY = 64;        // Минимальный размер для дерева

Практические советы

1. Указывайте нужную capacity при создании:

// ❌ Плохо — будет много resize операций
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    map.put("key" + i, i);
}

// ✅ Хорошо — одна операция resize
Map<String, Integer> map = new HashMap<>(15000);
for (int i = 0; i < 10000; i++) {
    map.put("key" + i, i);
}

2. Реализуйте качественный equals() и hashCode():

public class User {
    private String email;
    
    @Override
    public int hashCode() {
        return email.hashCode();  // Простая реализация
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return email.equals(user.email);  // Проверяем по email
    }
}

3. Используйте ConcurrentHashMap для многопоточности:

// ❌ Не потокобезопасно
Map<String, Integer> map = new HashMap<>();

// ✅ Потокобезопасно
Map<String, Integer> map = new ConcurrentHashMap<>();

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