HashMap в Java реализован на основе массива бакетов (bucket array) и связных списков или сбалансированных деревьев (TreeNodes) внутри каждого бакета.

Основные компоненты и принцип работы:

Массив бакетов: Каждый элемент массива — это бакет, который хранит элементы с одинаковым хеш-кодом по модулю размера массива.
Хеш-функция: Для ключа вычисляется хеш-код, который затем преобразуется в индекс массива (бакета) с помощью операции по модулю.
Разрешение коллизий: Если несколько ключей попадают в один бакет (коллизия), они хранятся в связном списке или, при большом числе элементов, в сбалансированном дереве (начиная с Java 8).
Поиск: При поиске ключа вычисляется индекс бакета, затем перебираются элементы внутри бакета для поиска совпадения по equals().
Добавление: Новый элемент добавляется в соответствующий бакет. Если размер бакета превышает порог, связный список преобразуется в дерево для повышения производительности.
Ре-хеширование: При достижении определенной загрузки (load factor) массив увеличивается, и все элементы перераспределяются по новым бакетам.

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

class HashMap<K, V> {
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
        // ...
    }

    Node<K, V>[] table;
    int size;
    // ...
}

Таким образом, HashMap обеспечивает быстрый доступ к элементам за амортизированное время O(1) при хорошей хеш-функции и низком числе коллизий.

Какая структура данных лежит в основе реализации HashMap и как она работает?