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

HashMap в Java основан на массиве Node<K,V>[] (или Entry<K,V>[] в старых версиях), где каждый элемент представляет собой связный список (или дерево в 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, при достижении определенного порога элементов в бакете (по умолчанию 8), связный список преобразуется в сбалансированное дерево (TreeNode) для улучшения производительности с O(n) до O(log n).