Всегда ли бакет (bucket) в `HashMap` реализован как связный список?

Нет, начиная с Java 8 бакет может быть как связным списком, так и сбалансированным деревом. Это было введено для оптимизации производительности в случае большого количества коллизий.

Эволюция структуры бакета в Java:

1. До Java 8: Бакет всегда был односвязным списком (Entry<K,V> с полем next). При коллизиях элементы добавлялись в голову списка.

2. Java 8 и выше: Используется гибридная структура.

   • Пока элементов в бакете мало (<= TREEIFY_THRESHOLD = 8), используется связный список.
   • Если размер бакета превышает порог и общее количество корзин (HashMap) больше MIN_TREEIFY_CAPACITY (64), список преобразуется в красно-черное дерево (TreeNode<K,V>).
   • Если элементы удаляются и размер дерева пажает ниже UNTREEIFY_THRESHOLD (6), оно снова преобразуется в список.

Пример внутренней структуры (Java 8+):

// Узел для списка (используется также как базовый класс для TreeNode)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Ссылка для организации списка
}

// Узел для дерева (наследуется от LinkedHashMap.Entry, который, в свою очередь, наследуется от Node)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // Ссылки для организации красно-черного дерева
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // Нужен для отмены операции treeify
    boolean red;
}

Причина изменений: Преобразование в дерево гарантирует время поиска O(log n) в переполненном бакете вместо O(n) у списка, что критично для защиты от атак, основанных на искусственном создании коллизий хэшей.