Какую структуру данных хранит бакет (bucket) в Java HashMap?

В Java HashMap каждый бакет хранит либо связный список, либо красно-черное дерево (с Java 8) объектов Node<K,V>, представляющих записи мапы.

Структура узла (Node):

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

Логика работы бакета:

1. При коллизиях (одинаковый индекс бакета для разных ключей) элементы добавляются в связный список.
2. При достижении порога (TREEIFY_THRESHOLD = 8) и если размер мапы превышает MIN_TREEIFY_CAPACITY (64), список в бакете преобразуется в красно-черное дерево (объекты TreeNode). Это оптимизирует поиск с O(n) до O(log n) для длинных цепочек.
3. При уменьшении размера (UNTREEIFY_THRESHOLD = 6) дерево может быть преобразовано обратно в список.

Почему именно так? Это компромисс между памятью и скоростью. Списки эффективны для малого числа коллизий, деревья защищают от деградации производительности при атаках, приводящих к множественным коллизиям.