Как устроен лист в HashMap

В Java HashMap использует массив Node<K,V>[] для хранения данных. Каждый элемент массива (bucket) может содержать связный список или дерево (в Java 8+) для разрешения коллизий.

При добавлении элемента:

1. Вычисляется хэш ключа (hash(key))
2. Определяется индекс корзины: index = (n - 1) & hash, где n - размер массива
3. Если корзина пуста - создается нода
4. При коллизии элементы добавляются в список/дерево

Пример структуры ноды:

static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // конструкторы и методы
}

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