На какой структуре данных основана реализация HashMap в Java?

Основа — массив бакетов (Node<K,V>[] table), где каждый бакет может содержать:

1. Ничего (null).
2. Один узел (коллизии нет).
3. Связный список узлов (решение коллизий методом цепочек).
4. Сбалансированное дерево (TreeBin) в Java 8+ при большом количестве коллизий в бакете.

Внутренний узел (упрощенно):

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

Эволюция при коллизиях (Java 8+):

• При малом количестве элементов в бакете (TREEIFY_THRESHOLD = 8) используется связный список.
• При превышении порога список преобразуется в красно-черное дерево для обеспечения сложности O(log n) вместо O(n) для операций в этом бакете.
• Обратное преобразование (дерево в список) происходит при уменьшении размера (UNTREEIFY_THRESHOLD = 6).