llmdocsсправочник разработчика

Хеш-таблица

Материал из llmdocs — справочник разработчика
Портал: Основы CS
Хеш-таблица
Типассоциативный массив
Поиск, вставка, удалениеO(1) в среднем, O(n) в худшем случае
ПамятьO(n)
Разрешение коллизийцепочки, открытая адресация
Ключевой параметркоэффициент заполнения (load factor)
Реализацииdict (Python), map (Go), HashMap (Rust, Java), Object/Map (JS)

Хеш-таблица (англ. hash table, hash map) — структура данных, хранящая пары «ключ → значение» и позволяющая находить, добавлять и удалять элемент по ключу в среднем за постоянное время, O(1) (см. Алгоритм и O-нотация). Для этого ключ превращается хеш-функцией в число, а число — в номер ячейки массива.[1] На хеш-таблицах построены dict и set в Python, map в Go, HashMap в Rust и Java, индексы в базах данных и кэши.

Принцип работы

Таблица — это массив из m ячеек (корзин, buckets). Чтобы положить пару (k, v):

  1. вычислить хеш h = hash(k) — большое целое число;
  2. получить индекс i = h mod m (или h & (m − 1), если m — степень двойки);
  3. записать пару в ячейку i.

Поиск повторяет те же шаги и сравнивает ключ в найденной ячейке с искомым. Хеш-функция должна быть детерминированной (одинаковые ключи → одинаковый хеш) и равномерно распределять ключи по ячейкам. Ключи должны быть неизменяемыми: если ключ поменяется после вставки, его хеш изменится и элемент «потеряется» — поэтому в Python нельзя использовать список как ключ словаря.

Коллизии

Разные ключи неизбежно попадают в одну ячейку — это коллизия. Два основных способа их разрешать:

  • Метод цепочек (separate chaining) — в каждой ячейке хранится список (или дерево) всех элементов с этим индексом. Просто и устойчиво к высокому заполнению; так устроен HashMap в Java, который превращает длинную цепочку в красно-чёрное дерево.
  • Открытая адресация (open addressing) — все элементы лежат прямо в массиве; при занятой ячейке пробуется следующая по правилу: линейное пробирование (i+1, i+2…), квадратичное или двойное хеширование. Удаление требует пометок-«надгробий» (tombstones). Метод компактнее и дружелюбнее к кэшу процессора, поэтому его выбирают CPython, Rust и Go.

Современные быстрые реализации — Swiss Table (Google Abseil, hashbrown в Rust, map в Go с версии 1.24) — хранят рядом с ячейками короткие метаданные (7 бит хеша) и проверяют сразу 8–16 ячеек одной SIMD-инструкцией.[3][4]

Коэффициент заполнения и рост

Коэффициент заполнения α = n / m (число элементов на число ячеек) определяет скорость: чем он выше, тем больше коллизий. Когда α превышает порог (около 2/3 у CPython, 7/8 у Swiss Table, 0,75 у Java), таблица перестраивается (rehash): выделяется массив примерно вдвое больше, и все элементы вставляются заново. Отдельная перестройка стоит O(n), но происходит редко, поэтому амортизированная стоимость вставки остаётся O(1).

Операция Среднее Худшее
Поиск O(1) O(n)
Вставка O(1) амортизированно O(n)
Удаление O(1) O(n)
Обход по порядку ключей — (нужна сортировка) O(n log n)

Худший случай наступает, если все ключи попали в одну ячейку.

Порядок элементов

Классическая хеш-таблица не гарантирует порядок обхода. Начиная с Python 3.7 словарь сохраняет порядок вставки: CPython хранит записи в плотном массиве, а таблица хешей содержит лишь индексы в нём — это заодно экономит память.[2] В Go порядок обхода map намеренно рандомизирован, чтобы код не полагался на него. Если нужен порядок по ключу или поиск диапазонов, вместо хеш-таблицы используют сбалансированные деревья или B-дерево (см. Дерево и граф).

Безопасность: hash flooding

Если атакующий знает хеш-функцию, он может подобрать множество ключей с одинаковым индексом и превратить O(1) в O(n) на каждую операцию — например, отправив веб-серверу запрос с тысячами специально подобранных параметров. Атаку описали в 2003 году, а в 2011-м продемонстрировали против PHP, Java, Python и Ruby.[5] Защита — хеш-функция со случайным секретным ключом, генерируемым при старте процесса: SipHash в Python, Rust и Ruby.[6] Поэтому hash("abc") в Python меняется между запусками (переменная PYTHONHASHSEED).

Примеры

# Python: dict и set
counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1

seen = set()
unique = [x for x in items if not (x in seen or seen.add(x))]

// Go
ages := map[string]int{"alice": 31}
ages["bob"] = 25
if age, ok := ages["carol"]; !ok { fmt.Println("нет такого ключа", age) }

Чтобы объект своего класса мог быть ключом, у него должны быть согласованы равенство и хеш: в Python — методы __eq__ и __hash__, в Rust — трейты Eq и Hash, в Java — equals и hashCode.

Применения

  • словари, множества, подсчёт частот, удаление дубликатов;
  • кэши и мемоизация, в том числе LRU-кэш (хеш-таблица + двусвязный список);
  • индексы в СУБД (хеш-индексы в PostgreSQL) и хранилищах «ключ — значение» вроде Redis;
  • таблицы символов в компиляторах и интерпретаторах;
  • распределённые системы — согласованное хеширование для распределения ключей по узлам.

См. также

Источники

  1. Cormen et al. — Introduction to Algorithms, 4th ed., ch. 11 Hash Tables (MIT Press)
  2. Python — dictobject.c, notes on dict implementation
  3. Go Blog — Faster Go maps with Swiss Tables
  4. Rust std::collections::HashMap
  5. Crosby, Wallach — Denial of Service via Algorithmic Complexity Attacks (USENIX Security 2003)
  6. Aumasson, Bernstein — SipHash: a fast short-input PRF
Категории: