В чем разница между бакетом и списком?

Бакет vs Список: Различия и применение

Бакет (bucket) и список (list) — это две важные концепции в Java, используемые в разных контекстах структур данных.

Что такое Бакет?

Бакет — это контейнер в хеш-таблице (HashMap, HashTable), который хранит несколько элементов, отображаемых на один хеш-код. Это основной механизм разрешения коллизий в хешировании.

// Структура HashMap с бакетами
// Массив бакетов:
// [0] -> Список элементов с hash % size == 0
// [1] -> Список элементов с hash % size == 1
// [2] -> Список элементов с hash % size == 2
// ...

Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);  // hash("Alice") -> бакет [5]
map.put("Bob", 30);    // hash("Bob") -> бакет [5] (коллизия!)
map.put("Charlie", 35); // hash("Charlie") -> бакет [7]

Что такое Список?

Список — это структура данных (List), которая хранит элементы в определённом порядке и обеспечивает доступ по индексу. Список может быть реализован как массив (ArrayList) или связный список (LinkedList).

List<String> list = new ArrayList<>();
list.add("Alice");    // Индекс 0
list.add("Bob");      // Индекс 1
list.add("Charlie");  // Индекс 2

String name = list.get(1);  // "Bob" — доступ по индексу

Ключевые различия

Как бакеты работают в HashMap

public class HashMap<K, V> {
    private Node<K, V>[] table;  // Массив бакетов
    private int capacity = 16;    // Начальная ёмкость
    
    public V put(K key, V value) {
        int hash = hash(key);              // Вычисляем хеш
        int index = hash % capacity;       // Определяем индекс бакета
        Node<K, V> bucket = table[index];  // Получаем бакет (список)
        
        // Если в бакете уже есть элементы (коллизия),
        // добавляем новый элемент в связный список
        while (bucket != null) {
            if (bucket.key.equals(key)) {
                return bucket.value = value;  // Обновляем значение
            }
            bucket = bucket.next;
        }
        // Если ключ не найден, добавляем новый узел
        table[index] = new Node<>(key, value, table[index]);
        return null;
    }
}

Java 8+: Оптимизация бакетов

Начиная с Java 8, HashMap оптимизирован:

// Когда в бакете > 8 элементов, связный список
// преобразуется в красно-чёрное дерево (TreeMap)

if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

// Это улучшает производительность при множественных коллизиях:
// - LinkedList поиск: O(n)
// - TreeMap поиск: O(log n)

Практический пример различия

// Список — упорядоченный доступ
List<String> list = new ArrayList<>();
list.add("первый");
list.add("второй");
list.add("третий");

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // Доступ по индексу
}

// Бакеты в HashMap — быстрый поиск по ключу
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 25);
map.put("Bob", 30);

Integer age = map.get("Alice");  // O(1) поиск через бакет

Когда использовать

Используй Список когда:

• Нужен упорядоченный доступ к элементам
• Требуется индексный доступ
• Нужно сохранить порядок вставки

Бакеты (HashMap) когда:

• Нужен быстрый поиск по ключу
• Не важен порядок элементов
• Требуется O(1) производительность поиска