Что происходит при добавлении элемента в HashMap

# Что происходит при добавлении элемента в HashMap

Общий процесс

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

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5); // Что происходит здесь?

Шаг 1: Вычисление Hash Code

// Сначала вычисляется hashCode ключа
int hashCode = "apple".hashCode();
// hashCode = 92599507

Но это слишком большое число, нужно привести к размеру массива.

Шаг 2: Вычисление Index (индекса в массиве)

// HashMap внутренне содержит массив (bucket array)
Node[] table = new Node[16]; // Начальный размер 16

// Вычисляется index с помощью таблицы хеша
int index = hashCode & (table.length - 1);
// Битовая операция &(table.length - 1) эквивалентна %
// Это быстрее чем modulo

// Например: 92599507 & 15 = 3
// Значит элемент должен идти в bucket с индексом 3

Почему & (table.length - 1)?

• Размер таблицы всегда степень 2 (16, 32, 64...)
• table.length - 1 дает маску всех бит (15 = 1111 в двоичном)
• Битовая операция & намного быстрее чем modulo %

Шаг 3: Проверка коллизии (Collision)

// HashMap использует метод цепочек (chaining) для коллизий
// Каждый bucket может содержать несколько элементов в виде связного списка

class Node<K, V> {
    K key;
    V value;
    Node<K, V> next; // Указатель на следующий узел в цепочке
}

// Если bucket пуст — добавляем элемент
if (table[3] == null) {
    table[3] = new Node("apple", 5);
}

// Если в bucket уже что-то есть — проверяем ключи
if (table[3] != null) {
    // Ищем узел с таким же ключом
    Node current = table[3];
    while (current != null) {
        if (current.key.equals("apple")) {
            // Ключ найден — обновляем значение
            current.value = 5;
            return;
        }
        current = current.next;
    }
    // Ключ не найден — добавляем в начало цепочки
    Node newNode = new Node("apple", 5);
    newNode.next = table[3];
    table[3] = newNode;
}

Шаг 4: Проверка Load Factor и Resizing

// После добавления элемента проверяется load factor
size++; // Увеличиваем размер

float loadFactor = (float) size / table.length;
// По умолчанию максимум = 0.75

if (loadFactor > 0.75) {
    resize();
}

Что такое load factor?

• Это отношение количества элементов к размеру массива
• Показывает насколько "заполнена" таблица
• Если > 0.75, то вероятно много коллизий

Процесс resize

private void resize() {
    // Увеличиваем размер в 2 раза
    int newCapacity = table.length * 2; // 16 -> 32 -> 64...
    Node[] newTable = new Node[newCapacity];
    
    // Rehashing: переносим все элементы в новую таблицу
    for (Node node : table) {
        while (node != null) {
            // Вычисляем новый index для каждого элемента
            int newIndex = node.hashCode & (newCapacity - 1);
            // Добавляем в новую таблицу
            Node next = node.next;
            node.next = newTable[newIndex];
            newTable[newIndex] = node;
            node = next;
        }
    }
    
    this.table = newTable;
}

Это дорогостоящая операция! Все элементы пересчитываются и перемещаются.

Полный пример с кодом

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // Добавим несколько элементов
        map.put("apple", 5);   // Index 3
        map.put("banana", 3);  // Index 7
        map.put("cherry", 8);  // Index 3 (коллизия с apple!)
        
        System.out.println(map);
        // {apple=5, cherry=8, banana=3}
        
        // Обновление существующего ключа
        map.put("apple", 10);
        System.out.println(map.get("apple")); // 10
    }
}

Коллизии (Collisions)

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

// Два разных ключа могут иметь одинаковый hash
String key1 = "Aa";
String key2 = "BB";

System.out.println(key1.hashCode()); // 2080
System.out.println(key2.hashCode()); // 2080 (коллизия!)

// HashMap справляется с этим через цепочку
HashMap<String, String> map = new HashMap<>();
map.put("Aa", "value1");
map.put("BB", "value2");

// Оба значения хранятся в одном bucket, но в разных узлах
// table[index] -> Node("Aa") -> Node("BB") -> null

Java 8+: Оптимизация с помощью деревьев

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

// До Java 8: O(n) для поиска в случае коллизий
// Java 8+: O(log n) если много коллизий (используется дерево вместо списка)

private static final int TREEIFY_THRESHOLD = 8; // Порог для дерева

if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(table, hash); // Преобразовать список в дерево
}

Это избегает деградации производительности при плохом hashCode().

Полная диаграмма процесса

map.put("apple", 5)
    ↓
1. Вычислить hashCode("apple") = 92599507
    ↓
2. Вычислить index = hashCode & (table.length - 1) = 3
    ↓
3. Проверить table[3]
    ├─ Если NULL → создать новый Node
    ├─ Если узел существует → проверить equals(key)
    │   ├─ Если совпадает → обновить value
    │   └─ Если не совпадает → добавить в цепочку
    └─ Если цепочка > 8 → преобразовать в дерево
    ↓
4. Увеличить size
    ↓
5. Если size > capacity * loadFactor → resize()
    ├─ Создать новый массив (в 2 раза больше)
    └─ Перехешировать все элементы

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

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

// Best case: O(1)
map.put("key1", 1);
int value = map.get("key1");

// Average case: O(1)
// Разреженная таблица, нет коллизий

// Worst case: O(n)
// Если много коллизий и все элементы в одном bucket
// Но с Java 8 (дерево): O(log n)

// Resize: O(n)
// Когда load factor превышен, нужно перестроить таблицу

Практические примеры

Кастомный класс как ключ

public class User {
    String id;
    String name;
    
    @Override
    public int hashCode() {
        return id.hashCode(); // Один из полей
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof User)) return false;
        User other = (User) obj;
        return this.id.equals(other.id);
    }
}

HashMap<User, String> userMap = new HashMap<>();
User user1 = new User();
user1.id = "123";
userMap.put(user1, "John");

// ВАЖНО: если id изменится, найти элемент будет сложно!
user1.id = "456;
// userMap.get(user1) вернёт null (неправильный hash)

Оптимальные размеры

// Если знаешь, сколько элементов будет
HashMap<String, Integer> map = new HashMap<>(100);
// Укажи начальный capacity, чтобы избежать resize

// Если не знаешь, используй LinkedHashMap для insertion order
LinkedHashMap<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("first", 1);
linkedMap.put("second", 2);
// Итерация в порядке добавления

Что НЕ нужно делать

// ПЛОХО: изменяемый объект как ключ
StringBuilder key = new StringBuilder("key");
map.put(key, "value");
key.append("2"); // Изменили hashCode!
map.get(key); // Может не найти!

// ХОРОШО: immutable объекты как ключи
String key = "key"; // immutable
map.put(key, "value");
// hashCode никогда не изменится

Заключение

Процесс put() в HashMap:

1. Hash — вычислить hashCode() ключа
2. Index — преобразовать в индекс массива
3. Collision resolution — обработать коллизии через цепочки/деревья
4. Update or Insert — обновить или добавить
5. Resize — если нужно, увеличить таблицу

Средняя сложность O(1), но может деградировать до O(n) при плохом hashCode().