# Хеш-таблица

> Структура данных «ключ → значение», которая с помощью хеш-функции находит ячейку по ключу в среднем за O(1); основа словарей и множеств почти во всех языках.

Источник: https://llmdocs.ru/wiki/hash-table/ · обновлено 2026-11-09 · лицензия CC BY-SA 4.0

- **Тип**: ассоциативный массив
- **Поиск, вставка, удаление**: O(1) в среднем, O(n) в худшем случае
- **Память**: O(n)
- **Разрешение коллизий**: цепочки, открытая адресация
- **Ключевой параметр**: коэффициент заполнения (load factor)
- **Реализации**: dict (Python), map (Go), HashMap (Rust, Java), Object/Map (JS)
**Хеш-таблица** (англ. *hash table*, *hash map*) — [структура данных](https://llmdocs.ru/wiki/data-structures.md), хранящая пары «ключ → значение» и позволяющая находить, добавлять и удалять элемент по ключу в среднем за постоянное время, O(1) (см. [Алгоритм и O-нотация](https://llmdocs.ru/wiki/big-o.md)). Для этого ключ превращается [хеш-функцией](https://llmdocs.ru/wiki/hash-function.md) в число, а число — в номер ячейки массива.[1] На хеш-таблицах построены `dict` и `set` в [Python](https://llmdocs.ru/wiki/python.md), `map` в [Go](https://llmdocs.ru/wiki/go.md), `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-дерево](https://llmdocs.ru/wiki/b-tree.md) (см. [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)).

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

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

## Примеры

```python
# 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
// 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`.

## Применения

- словари, множества, подсчёт частот, удаление дубликатов;
- [кэши](https://llmdocs.ru/wiki/cache.md) и мемоизация, в том числе LRU-кэш (хеш-таблица + двусвязный список);
- индексы в СУБД (хеш-индексы в [PostgreSQL](https://llmdocs.ru/wiki/postgresql.md)) и хранилищах «ключ — значение» вроде [Redis](https://llmdocs.ru/wiki/redis.md);
- таблицы символов в [компиляторах и интерпретаторах](https://llmdocs.ru/wiki/compiler-interpreter.md);
- распределённые системы — согласованное хеширование для распределения ключей по узлам.

## См. также

- [Хеш-функция](https://llmdocs.ru/wiki/hash-function.md)
- [Структуры данных](https://llmdocs.ru/wiki/data-structures.md)
- [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)
- [Индекс (базы данных)](https://llmdocs.ru/wiki/database-index.md)

## Источники

1. [Cormen et al. — Introduction to Algorithms, 4th ed., ch. 11 Hash Tables (MIT Press)](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/)
2. [Python — dictobject.c, notes on dict implementation](https://github.com/python/cpython/blob/main/Objects/dictobject.c)
3. [Go Blog — Faster Go maps with Swiss Tables](https://go.dev/blog/swisstable)
4. [Rust std::collections::HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html)
5. [Crosby, Wallach — Denial of Service via Algorithmic Complexity Attacks (USENIX Security 2003)](https://www.usenix.org/legacy/events/sec03/tech/full_papers/crosby/crosby.pdf)
6. [Aumasson, Bernstein — SipHash: a fast short-input PRF](https://cr.yp.to/siphash/siphash-20120918.pdf)