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

HashMap<K,V> в Java хранит свои данные (узлы Node) во внутреннем массиве Node<K,V>[] table. Это основа ее реализации.

Базовая структура:

// Внутренний массив «корзин» (buckets)
transient Node<K,V>[] table;

// Узел для хранения пары ключ-значение
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    // Хэш-код ключа
    final K key;       // Ключ
    V value;           // Значение
    Node<K,V> next;    // Ссылка на следующий узел в цепочке (при коллизии)
}

Алгоритм работы (упрощенно):

1. Вычисление индекса: При вставке или поиске по ключу вычисляется его хэш-код. На основе этого хэша определяется индекс корзины в массиве: index = (n - 1) & hash, где n — размер массива table.
2. Разрешение коллизий: Если в корзине по вычисленному индексу уже есть элемент(ы) — это коллизия. Новый узел добавляется в цепочку (связный список) или в дерево в этой корзине.
3. Преобразование в дерево: Для оптимизации производительности при большом количестве коллизий, когда длина цепочки в одной корзине превышает TREEIFY_THRESHOLD (по умолчанию 8), связный список преобразуется в сбалансированное красно-черное дерево (реализация TreeNode). Это уменьшает время поиска с O(n) до O(log n).

Визуализация:

table[]
[0] -> null
[1] -> Node<K1,V1> -> Node<K2,V2> -> Node<K3,V3] // Цепочка из-за коллизий
[2] -> TreeNode<K4,V4> // Преобразованное в дерево
[3] -> null
...

Ключевые моменты:

• Емкость массива (table.length) всегда является степенью двойки.
• При достижении определенного уровня заполнения (load factor, по умолчанию 0.75) происходит ресайзинг — массив увеличивается вдвое, и все элементы перераспределяются по новым корзинам.