Какие элементы хранятся в бакете Hash Table

Какие элементы хранятся в бакете Hash Table

Введение

Hash Table (хеш-таблица) — это структура данных, которая реализует ассоциативный массив (dictionary). Она использует хеширование для сопоставления ключей со значениями. Бакет (bucket) — это основной строительный блок хеш-таблицы.

Основная структура Hash Table

Hash Table = Array of Buckets

┌─────────────────────────────────────────┐
│  [0] → ┌──────────────────────────────┐ │
│         │ Bucket 0: цепочка или entry │ │
│  [1] → ├──────────────────────────────┤ │
│  [2] → │ Bucket 1: entry             │ │
│  [3] → ├──────────────────────────────┤ │
│  [4] → │ Bucket 2: цепочка entries   │ │
│  ...   └──────────────────────────────┘ │
│  [n]   │ Bucket n: пусто             │ │
└─────────────────────────────────────────┘

Что хранится в бакете?

1. Элементы Entry (Key-Value пары)

Структура Entry

// Простая структура
public class Entry<K, V> {
    K key;        // ключ
    V value;      // значение
    int hash;     // предварительно вычисленный хеш ключа
    Entry next;   // указатель на следующий элемент (для разрешения коллизий)
}

// Пример в HashMap
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // для chaining
}

Что это означает

• Каждый бакет может содержать одну или несколько пар (key, value)
• При коллизии (когда несколько ключей хешируются на один бакет), элементы хранятся в виде цепочки (linked list) или дерева (tree)

Entry entry1 = new Entry("apple", 100);
Entry entry2 = new Entry("apples", 200);
Entry entry3 = new Entry("apply", 300);

// Все три могут быть в одном бакете, если их hashCode() вернул одинаковое значение
// И будут связаны: entry1 -> entry2 -> entry3

2. Цепочка (Chain / Linked List)

Разрешение коллизий через chaining

Бакет содержит цепочку элементов:

Bucket[2]:
┌──────────┐      ┌──────────┐      ┌──────────┐
│ key="a"  │  ->  │ key="d"  │  ->  │ key="g"  │  -> null
│ val=10   │      │ val=40   │      │ val=70   │
└──────────┘      └──────────┘      └──────────┘

Все три элемента "a", "d", "g" хешируются в bucket[2]

Реализация в Java

public class ChainedHashTable<K, V> {
    private Entry<K, V>[] buckets;
    private int capacity;
    
    public void put(K key, V value) {
        int hash = key.hashCode() % capacity;  // вычислить индекс бакета
        Entry<K, V> entry = new Entry<>(key, value);
        
        if (buckets[hash] == null) {
            buckets[hash] = entry;              // первый элемент в бакете
        } else {
            entry.next = buckets[hash];         // вставить в начало цепочки
            buckets[hash] = entry;
        }
    }
    
    public V get(K key) {
        int hash = key.hashCode() % capacity;
        Entry<K, V> current = buckets[hash];
        
        while (current != null) {               // искать в цепочке
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }
}

3. Red-Black дерево (в Java 8+)

Оптимизация для больших цепочек

В Java 8+ HashMap использует Red-Black дерево вместо linked list при определённых условиях:

// Когда цепочка становится слишком длинной:
// - TREEIFY_THRESHOLD = 8 (если цепочка > 8 элементов)
// - Преобразуется в Red-Black дерево

static 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;     // нужен для двусвязного списка
    boolean red;
}

Структура

Бакет[5] с Red-Black деревом:

            [key="apple", val=1]
           /                      \\
    [key="a"]              [key="apply"]
   /        \\            /          \\
[key...] [key...]  [key...]     [key...]

Преимущество

• Linked List: O(n) для поиска в худшем случае
• Red-Black Tree: O(log n) для поиска

// Преобразование в дерево
if (binCount >= TREEIFY_THRESHOLD - 1) { // -1 для head
    treeifyBin(tab, hash);
}

4. Пустой бакет (null)

Не все бакеты заполнены

HashMap<String, Integer> map = new HashMap<>();
// Создаёт массив из 16 бакетов (по умолчанию)
// Entry<String, Integer>[] buckets = new Entry[16];

// Большинство будут null (пусто)
Bucket[0]:  null
Bucket[1]:  null
Bucket[2]:  null   // может содержать элементы позже
...
Bucket[15]: null

5. Метаданные в бакете

Дополнительная информация

// В HashMap каждое Entry содержит:
public class HashMap<K, V> {
    static class Node<K, V> implements Map.Entry<K, V> {
        final int hash;           // кэшированный hashCode()
        final K key;              // ключ (immutable)
        V value;                  // значение (может меняться)
        Node<K, V> next;          // для цепочки
        
        // и методы:
        public K getKey() { ... }
        public V getValue() { ... }
        public V setValue(V newValue) { ... }
    }
}

Почему кэшируется хеш?

// Вычисление хеша дорого (может быть сложным объектом)
// Поэтому сохраняем результат
int cachedHash = hash;  // нет нужды пересчитывать

// Для сравнения в коллизии:
if (e.hash == hash && e.key.equals(key)) {
    // совпадение
}

6. LinkedHashMap и порядок

Дополнительно: двусвязный список

// LinkedHashMap сохраняет порядок вставки
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
    LinkedHashMapEntry<K,V> before;  // предыдущий по времени
    LinkedHashMapEntry<K,V> after;   // следующий по времени
}

// Структура:
// Hash Table (быстрый поиск) +
// Двусвязный список (порядок вставки/доступа)

Пример полной работы Hash Table

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 100);
map.put("banana", 200);
map.put("apricot", 150);

// Внутри:
// Compute hash для каждого ключа
int h1 = "apple".hashCode();      // Example: 93029210
int h2 = "banana".hashCode();     // Example: -1012001200
int h3 = "apricot".hashCode();    // Example: 93029300

// Compute bucket index (для capacity = 16)
int idx1 = h1 % 16;  // Example: 2
int idx2 = h2 % 16;  // Example: 8
int idx3 = h3 % 16;  // Example: 4 (или может совпасть)

// Итоговая структура:
/*
Bucket[2]  -> Entry("apple", 100) -> null
Bucket[4]  -> Entry("apricot", 150) -> null  // может быть в цепочке
Bucket[8]  -> Entry("banana", 200) -> null
Бакеты[0,1,3,5-7,9-15] -> null
*/

Практический пример: реализация простой Hash Table

public class SimpleHashTable<K, V> {
    private static final int INITIAL_CAPACITY = 16;
    
    private class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;
        
        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private Entry<K, V>[] buckets;
    private int size;
    
    @SuppressWarnings("unchecked")
    public SimpleHashTable() {
        buckets = new Entry[INITIAL_CAPACITY];
        size = 0;
    }
    
    public void put(K key, V value) {
        int index = hash(key);
        Entry<K, V> entry = buckets[index];
        
        // Проверить, есть ли уже такой ключ в цепочке
        while (entry != null) {
            if (entry.key.equals(key)) {
                entry.value = value;  // обновить значение
                return;
            }
            entry = entry.next;
        }
        
        // Добавить новый элемент в начало цепочки
        Entry<K, V> newEntry = new Entry<>(key, value);
        newEntry.next = buckets[index];
        buckets[index] = newEntry;
        size++;
    }
    
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> entry = buckets[index];
        
        // Поиск в цепочке
        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }
        return null;
    }
    
    private int hash(K key) {
        if (key == null) return 0;
        return Math.abs(key.hashCode()) % buckets.length;
    }
    
    public int size() {
        return size;
    }
}

Анализ производительности

Load Factor = size / capacity

// При load factor >= 0.75 (обычно)
// HashMap увеличивает capacity в 2 раза и rehash все элементы

private static final float LOAD_FACTOR = 0.75f;
private static final int DEFAULT_CAPACITY = 16;

public void put(K key, V value) {
    // ...
    if (++size > LOAD_FACTOR * capacity) {
        resize();  // увеличить capacity и перехешировать все элементы
    }
}

private void resize() {
    // newCapacity = capacity * 2
    // Rehash все элементы в новые бакеты
}

Временная сложность

Средний случай:
- get(): O(1) — константное время
- put(): O(1) — константное время
- remove(): O(1) — константное время

Худший случай (много коллизий):
- get(): O(n) — если все элементы в одном бакете
- put(): O(n)
- remove(): O(n)

С Red-Black деревом (Java 8+):
- get(): O(log n) — даже при много коллизиях

Вывод

Бакет в Hash Table хранит:

1. Entry объекты (пары key-value)
2. Цепочку (linked list) при коллизиях
3. Red-Black дерево (Java 8+) для оптимизации больших цепочек
4. Кэшированный хеш для быстрого сравнения
5. Null для пустых бакетов

Правильное использование Hash Table требует хорошего распределения hashCode() и понимания load factor для поддержания O(1) производительности.