Как работает HashMap? Какова временная сложность операций?

HashMap в Java

Структура:

HashMap — хеш-таблица с методом цепочек (chaining).

[0] → null
[1] → Node(key1, val1) → Node(key2, val2)
[2] → null
[3] → Node(key3, val3)
...

Основные параметры:

• Initial Capacity: 16 (по умолчанию)
• Load Factor: 0.75
• Threshold: capacity × loadFactor

Процесс добавления:

map.put("key", "value");

// 1. Вычисление хеша
int hash = key.hashCode() ^ (key.hashCode() >>> 16);

// 2. Определение бакета
int index = hash & (capacity - 1);

// 3. Добавление/обновление в бакете

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

*В Java 8+ при >8 элементах в бакете — красно-чёрное дерево

Коллизии:

// Все ключи с одинаковым hashCode
// попадают в один бакет

// Java 8+: бакет превращается в дерево
// при TREEIFY_THRESHOLD = 8

Resize (расширение):

// Когда size > threshold
// capacity удваивается
// Все элементы перехешируются

HashMap<String, Integer> map = new HashMap<>(100);
// Задать начальную ёмкость для оптимизации

Сравнение с другими: