Как реализована структура хранения элементов в HashMap?

В Java структура хранения элементов в HashMap основана на массиве бакетов (bucket array), где каждый бакет хранит элементы с одинаковым хеш-кодом по индексу.

Как это работает:

1. Для ключа вычисляется хеш-код (hashCode).
2. Хеш-код преобразуется в индекс массива бакетов (обычно с помощью операции по модулю или битовой маски).
3. В бакете хранятся пары ключ-значение. Если несколько ключей попадают в один бакет (коллизия), они хранятся в связном списке или, начиная с Java 8, в сбалансированном дереве (TreeNode) для повышения производительности.

Пример упрощённой структуры:

class HashMapNode<K, V> {
    final int hash;
    final K key;
    V value;
    HashMapNode<K, V> next; // для коллизий
}

HashMap хранит массив таких узлов, и при добавлении или поиске ключа идет по цепочке в соответствующем бакете.

Таким образом, HashMap обеспечивает быстрый доступ к элементам — в среднем за O(1), но при большом числе коллизий может деградировать до O(n).