Как устроен HashMap внутри

HashMap в Java основан на массиве Node<K,V>[], где каждый элемент (бакет) может содержать связанный список или дерево (в Java 8+) для разрешения коллизий.

Основные моменты:

• При добавлении элемента вычисляется хеш-ключа (hashCode()), затем индекс бакета: index = (n - 1) & hash, где n — размер массива.
• Если бакет пуст — элемент сохраняется. Если нет — добавляется в конец списка или дерева (если размер списка > TREEIFY_THRESHOLD (8)).
• При достижении loadFactor (по умолчанию 0.75) массив увеличивается вдвое и элементы перераспределяются.

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("key", 1); // hash("key") -> индекс, сохранение в бакет
map.get("key");    // аналогичный расчёт индекса и поиск

Нюансы:

• hashCode() должен быть консистентным и равномерным.
• В Java 8 при коллизиях используется красно-чёрное дерево для улучшения производительности с O(n) до O(log n).