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<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
🔹 Load factor и resize:
По умолчанию capacity = 16, loadFactor = 0.75. Порог = capacity * loadFactor = 12.
Как только элементов стало больше 12 — начинается resize(): таблица удваивается до 32, все элементы перераспределяются по новым бакетам. Это O(n) операция.
Поэтому если заранее знаете размер — задавайте начальную ёмкость:
// Хотим 1000 элементов без resize:
// 1000 / 0.75 ≈ 1334, берём следующую степень двойки
Map<String, Integer> map = new HashMap<>(2048);
🐸 Библиотека собеса по Java
#core