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

HashMap — массив бакетов (Node[] table). Ключ хешируется, хеш определяет индекс бакета: index = hash & (capacity - 1

Что происходит при put(key, value):

Считается hash(key) — не просто hashCode(), а с дополнительным перемешиванием старших битов ((h = key.hashCode()) ^ (h >>> 16)). Это снижает коллизии при маленьком размере таблицы.

Находится бакет по индексу. Если пустой — кладём первым. Если нет — коллизия.

🔹 Коллизия:

До Java 8 → связный список в бакете. Поиск O(n) в худшем случае.

С Java 8 → когда в бакете больше 8 элементов и capacity >= 64, список превращается в красно-чёрное дерево. Поиск становится O(log n). Обратно в список — при сжатии ниже 6 элементов.

// Упрощённо: Node в списке или TreeNode в дереве
static class Node {
final int hash;
final K key;
V value;
Node next;
}

🔹 Load factor и resize:

По умолчанию capacity = 16, loadFactor = 0.75. Порог = capacity * loadFactor = 12.

Как только элементов стало больше 12 — начинается resize(): таблица удваивается до 32, все элементы перераспределяются по новым бакетам. Это O(n) операция.

Поэтому если заранее знаете размер — задавайте начальную ёмкость:

// Хотим 1000 элементов без resize:
// 1000 / 0.75 ≈ 1334, берём следующую степень двойки
Map map = new HashMap(2048);

🐸 Библиотека собеса по Java

#core