Визуализация
Сценарий: Вставка ключей
Легенда цветов
Как работает хеш-таблица методом цепочек
Идея структуры: Хеш-таблица использует массив списков (называемых "корзинами"). Чтобы добавить или найти элемент, специальная хеш-функция преобразует ключ в число - индекс корзины. Так мы можем за одно вычисление мгновенно понять, где лежит элемент.
Коллизии. А если двум разным ключам выпадет одна и та же корзина? Это называется коллизией. В методе цепочек (separate chaining) мы просто связываем такие элементы друг за другом в связный список (цепочку). При поиске мы вычисляем корзину, а затем проходим по ее цепочке, пока не найдем нужный ключ.
Новый ключ встает в голову. Заметьте, куда именно добавляется узел: не в конец цепочки, а в ее начало. До конца пришлось бы идти по всем ссылкам, а голова доступна сразу - новый узел ссылается на бывшую голову, корзина ссылается на новый узел. Поэтому вставка стоит одинаково и в пустой корзине, и в корзине с десятком ключей.
Коэффициент загрузки (Load Factor). Это отношение числа элементов к числу корзин. Если элементов станет слишком много, цепочки станут длинными, и поиск замедлится. Поэтому в реальных хеш-таблицах при высоком коэффициенте загрузки происходит автоматическое увеличение числа корзин (перехеширование).
Другой путь. Цепочки - не единственный способ разойтись при коллизии. В открытой адресации списков нет вовсе: ключ ищет себе свободное место прямо в массиве таблицы. У каждого подхода своя цена - сравните обе анимации.
Синонимы названия: Метод цепочек, separate chaining, хеширование с цепочками.
Сложность
Сложность - это оценка того, как быстро растет потребление ресурса при росте числа элементов n. Ресурса у структуры два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
Производительность хеш-таблицы зависит от качества хеш-функции. Если она хорошо перемешивает ключи, цепочки остаются короткими.
По времени
| Операция | В среднем | В худшем случае |
|---|---|---|
| Поиск ключа | O(1) | O(n) - если все элементы попали в одну корзину |
| Вставка | O(1) | O(1) - узел встает в голову, длина цепочки не важна. Проверка дубликатов, если она нужна, стоит отдельно и превращает вставку в поиск |
| Удаление | O(1) | O(n) - проход по длинной цепочке до элемента |
По памяти
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Затраты по памяти | O(n + K) | Где n - число элементов, K - число корзин. Память тратится на сами узлы (n) и массив корзин (K). |
Свойства
| Свойство | Значение | Комментарий |
|---|---|---|
| Разрешение коллизий | Метод цепочек | Элементы с одинаковым хешем помещаются в связный список соответствующей корзины массива. |
| Коэффициент загрузки | α = n / K | Среднее число элементов в корзине: n ключей на K корзин. Чем выше α, тем длиннее цепочки и тем медленнее поиск. |
| Рехеширование | Динамическое | При превышении порога загрузки размер массива корзин увеличивается с перерасчетом хешей. |
Примеры реализации: Хеш-таблица методом цепочек (Separate Chaining)
Код на C
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 5
// Узел для связного списка (цепочки коллизий)
typedef struct Node {
int key;
struct Node* next;
} Node;
// Сама хеш-таблица - это массив указателей на узлы
Node* hashTable[TABLE_SIZE] = {NULL};
// Простая хеш-функция: остаток от деления
int hash(int key) {
return key % TABLE_SIZE;
}
// Вставка ключа в таблицу (O(1) в среднем)
void insert(int key) {
int idx = hash(key); // Вычисляем индекс корзины
// Создаем новый узел
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
// Вставляем его в начало цепочки (это быстрее всего - O(1))
// Новый узел указывает на старую голову цепочки
newNode->next = hashTable[idx];
// Обновляем голову корзины
hashTable[idx] = newNode;
}
// Поиск ключа в таблице (O(1) в среднем, O(N) в худшем)
int search(int key) {
int idx = hash(key); // Находим нужную корзину
Node* current = hashTable[idx];
// Проходим по цепочке
while (current != NULL) {
if (current->key == key) {
return 1; // Ключ найден
}
current = current->next;
}
return 0; // Ключ не найден
}Код на Python
# В Python стандартный словарь (dict) использует хеш-таблицу.
# Но для понимания алгоритма напишем свою реализацию метода цепочек.
class Node:
def __init__(self, key):
self.key = key
self.next = None
class HashTable:
def __init__(self, size):
self.size = size
# Создаем массив корзин, изначально заполненный None
self.table = [None] * size
# Вычисление индекса корзины
def hash_func(self, key):
return key % self.size
# Вставка ключа (O(1) в среднем)
def insert(self, key):
idx = self.hash_func(key)
new_node = Node(key)
# Вставляем узел в начало цепочки выбранной корзины
new_node.next = self.table[idx]
self.table[idx] = new_node
# Поиск ключа
def search(self, key):
idx = self.hash_func(key)
current = self.table[idx]
# Перебор элементов цепочки в корзине
while current is not None:
if current.key == key:
return True
current = current.next
return False
# Использование
ht = HashTable(5)
ht.insert(12)
ht.insert(22) # Коллизия с 12 (при size=5), 12 и 22 будут в одной цепочкеКод на JavaScript
// В JS есть встроенный класс Map, но мы напишем свою
// учебную реализацию метода цепочек (Separate Chaining).
class Node {
constructor(key) {
this.key = key;
this.next = null;
}
}
class HashTable {
constructor(size) {
this.size = size;
// Массив корзин (buckets)
this.table = new Array(size).fill(null);
}
// Хеш-функция
hash(key) {
return key % this.size;
}
// Вставка ключа - O(1) в среднем
insert(key) {
const idx = this.hash(key);
const newNode = new Node(key);
// Вставляем в начало цепочки, чтобы избежать O(N) прохода в конец
newNode.next = this.table[idx];
this.table[idx] = newNode;
}
// Поиск ключа
search(key) {
const idx = this.hash(key);
let current = this.table[idx];
// Проходим по связному списку в корзине
while (current !== null) {
if (current.key === key) {
return true; // Нашли
}
current = current.next;
}
return false; // Не нашли
}
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про методы рехеширования - с подробной теорией, задачами и проверочными вопросами.