Как называется "бакеты плюс листы"

# Структура HashMap: Бакеты и Листы

Общая концепция

"Бакеты плюс листы" — это внутренняя архитектура HashMap в Java. Это комбинированная структура данных, которая объединяет массив (бакеты) со связными списками (листы) для эффективного хранения и поиска данных с O(1) средней сложностью.

Как это работает

1. Массив бакетов (Buckets)

HashMap внутри хранит массив бакетов фиксированного размера. Каждый бакет — это позиция в массиве, где может храниться одна или несколько пар ключ-значение.

private static final int DEFAULT_INITIAL_CAPACITY = 16;
Node<K,V>[] table = new Node[DEFAULT_INITIAL_CAPACITY];

2. Функция хеширования

Когда вы добавляете элемент, HashMap вычисляет хеш-код ключа и преобразует его в индекс бакета:

int index = hash(key) & (table.length - 1);

3. Коллизии и листы (Chains)

Когда два разных ключа могут иметь одинаковый индекс бакета (коллизия хеширования), HashMap использует связный список (или в 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+

До Java 8 коллизии обрабатывались только связными списками (O(n) в худшем случае). С Java 8 HashMap использует красно-чёрное дерево вместо списка, если количество элементов в одном бакете превышает порог (по умолчанию 8):

// При TREEIFY_THRESHOLD = 8 элементов
// Лист преобразуется в дерево для O(log n) поиска

Пример работы

HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);

// Внутри:
// hash("Alice") % 16 → индекс 3 → Node("Alice", 25)
// hash("Bob") % 16 → индекс 7 → Node("Bob", 30)
// Если бы они имели одинаковый индекс:
// Индекс 3 → Node("Alice", 25) → Node("Bob", 30)

Факторы производительности

1. Load Factor (по умолчанию 0.75) — порог, при котором HashMap увеличивает размер (rehashing)
2. Hash Function Quality — хорошо распределённые хеш-коды минимизируют коллизии
3. Tree Conversion — преобразование в дерево защищает от деградации производительности при плохом распределении

Эта архитектура обеспечивает отличный баланс между скоростью доступа и использованием памяти.