Какой принцип работы HаshMap при добавлении элемента?

Принцип работы HashMap при добавлении элемента

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

Базовая структура HashMap

HashMap основан на массиве (bucket array) и использует механизм хеширования для разрешения коллизий:

// Внутренняя структура HashMap (упрощенно)
private 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;
    }
}

private Node<K,V>[] table;   // Массив buckets
private int size;             // Количество элементов
private int capacity;         // Текущая емкость
private float loadFactor;     // Коэффициент загрузки (по умолчанию 0.75)

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

Шаг 1: Вычисление хеш-кода

public V put(K key, V value) {
    // 1. Вычисляем хеш-код ключа
    int hash = hash(key);  // Вызов Object.hashCode()
    
    // Реальный процесс в HashMap:
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    // XOR с правым сдвигом уменьшает коллизии
    
    // 2. Вычисляем индекс в массиве
    int index = (capacity - 1) & hash;  // Эквивалентно hash % capacity
    // Это работает, потому что capacity всегда степень 2
    
    // 3. Поиск bucket и вставка
    // ...
}

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

// HashMap требует, чтобы capacity была степенью 2
// Это позволяет использовать битовую операцию & вместо модуля %
private static final int DEFAULT_CAPACITY = 16;  // 2^4

int bucketIndex = hash & (capacity - 1);
// Например: hash=42, capacity=16
// bucketIndex = 42 & 15 = 42 & 0b1111 = 0b101010 & 0b001111 = 0b001010 = 10

Шаг 3: Разрешение коллизий (связные списки или Red-Black деревья)

public V put(K key, V value) {
    int hash = hash(key);
    int index = hash & (capacity - 1);
    
    // Если bucket пуст
    if (table[index] == null) {
        table[index] = new Node<>(hash, key, value, null);
        size++;
        return null;
    }
    
    // Если в bucket уже есть элементы (коллизия)
    Node<K,V> current = table[index];
    
    // Java 8+: если связный список становится слишком длинным,
    // он преобразуется в Red-Black дерево (TREEIFY_THRESHOLD = 8)
    while (current != null) {
        // Проверяем, что это именно нужный элемент
        if ((current.hash == hash) && 
            (current.key == key || key.equals(current.key))) {
            // Ключ уже существует — обновляем значение
            V oldValue = current.value;
            current.value = value;
            return oldValue;  // Возвращаем старое значение
        }
        
        // Если это последний элемент в цепи
        if (current.next == null) {
            // Добавляем новый узел
            current.next = new Node<>(hash, key, value, null);
            size++;
            
            // Проверяем нужна ли пересорти при достижении TREEIFY_THRESHOLD
            if (shouldTreeify()) {
                treeify(index);
            }
            return null;
        }
        
        current = current.next;
    }
    
    return null;
}

Шаг 4: Проверка на необходимость расширения (Rehashing)

private void putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ... (добавление элемента как выше)
    
    // После добавления элемента
    ++size;
    
    // Проверяем, нужно ли увеличить capacity
    if (size >= capacity * loadFactor) {
        // loadFactor по умолчанию 0.75
        // При capacity=16 это означает: size > 12 => rehash
        resize();
    }
}

private void resize() {
    // Увеличиваем capacity в 2 раза
    int newCapacity = capacity << 1;  // Умножаем на 2
    
    // Создаем новый массив
    Node<K,V>[] newTable = new Node[newCapacity];
    
    // Перехешируем все существующие элементы в новый массив
    for (int i = 0; i < capacity; i++) {
        Node<K,V> node = table[i];
        while (node != null) {
            int newIndex = node.hash & (newCapacity - 1);
            Node<K,V> next = node.next;  // Сохраняем следующий узел
            node.next = newTable[newIndex];  // Вставляем в начало нового bucket
            newTable[newIndex] = node;
            node = next;
        }
    }
    
    table = newTable;
    capacity = newCapacity;
}

Пример пошагово

HashMap<String, Integer> map = new HashMap<>();
// capacity = 16, loadFactor = 0.75, size = 0

map.put("Apple", 1);
// 1. hash("Apple") = 2051939260
// 2. index = 2051939260 & 15 = 12
// 3. table[12] пуст, добавляем новый Node
// 4. size = 1

map.put("Banana", 2);
// 1. hash("Banana") = 1859860886
// 2. index = 1859860886 & 15 = 6
// 3. table[6] пуст, добавляем новый Node
// 4. size = 2

map.put("Apple", 10);  // Обновление
// 1. hash("Apple") = 2051939260
// 2. index = 12
// 3. table[12] не пуст, ищем Node с key="Apple"
// 4. Находим, обновляем value с 1 на 10
// 5. size остается 2, возвращаем старое значение 1

// После добавления 13-го элемента (size=13 > 12=capacity*loadFactor)
// Происходит resize(): capacity = 32, все элементы перехешируются

Важные моменты

1. Hash collision handling (Java 8+)

// При небольших коллизиях используется связный список O(n)
static final int TREEIFY_THRESHOLD = 8;
// Когда в одном bucket 8+ элементов, он становится Red-Black деревом O(log n)

static final int UNTREEIFY_THRESHOLD = 6;
// При resize() если в дереве 6 и менее элементов, переходим на список

2. equals() и hashCode() контракт

public class Person {
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // ДОЛЖЕН быть консистентным
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Person)) return false;
        Person other = (Person) obj;
        return Objects.equals(name, other.name) && age == other.age;
    }
    // ВАЖНО: если a.equals(b) == true, то a.hashCode() == b.hashCode()
}

HashMap<Person, String> map = new HashMap<>();
Person p1 = new Person("John", 30);
Person p2 = new Person("John", 30);

map.put(p1, "Developer");
map.get(p2);  // Вернет "Developer" благодаря правильным equals() и hashCode()

3. Потокобезопасность

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

// Это может привести к бесконечному циклу при одновременном resize()
// Решение: использовать Collections.synchronizedMap() или ConcurrentHashMap

Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// Лучше: ConcurrentHashMap (отдельные locks для bucket)
ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();

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

• put(): O(1) в среднем, O(n) в худшем (все элементы в одном bucket)
• get(): O(1) в среднем, O(n) в худшем
• remove(): O(1) в среднем, O(n) в худшем
• resize(): O(n) — переход всех элементов

Итоговый чеклист

✓ HashMap использует хеширование с разрешением коллизий через связные списки/деревья ✓ При добавлении: вычисляется хеш, определяется индекс, разрешаются коллизии ✓ Capacity всегда степень 2 для оптимизации через битовые операции ✓ При size > capacity × loadFactor происходит rehashing ✓ Реализуй equals() и hashCode() правильно для кастомных объектов ✓ HashMap не потокобезопасен — используй ConcurrentHashMap если надо