Хеш-таблицы: как устроены словари и что делать с коллизиями

Прямой ответ

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

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

1. Метод цепочек (separate chaining). В каждой ячейке хранится список или другая структура со всеми элементами, попавшими в эту позицию. Поиск проходит по цепочке. Просто, устойчиво к переполнению, но добавляет переходы по указателям и расход памяти.

2. Открытая адресация (open addressing). Все элементы лежат прямо в массиве. При коллизии ищется следующая свободная ячейка по правилу:

• Линейное пробирование — следующая ячейка подряд; просто, но вызывает «скопление» занятых ячеек.
• Квадратичное пробирование — шаг растёт квадратично; скопление меньше.
• Двойное хеширование — шаг определяется второй хеш-функцией; распределение лучше всего.

3. Robin Hood hashing и cuckoo hashing. Вариации открытой адресации, выравнивающие длину пробирования или дающие гарантированный O(1) на чтение ценой более дорогой вставки.

Ключевой параметр — load factor (коэффициент заполнения): отношение числа элементов к числу ячеек. При его превышении выполняется rehash — массив увеличивается, обычно вдвое, и все элементы перераспределяются. Это амортизированно O(1) на вставку, но отдельная операция может быть дорогой.

В Python словарь реализован через открытую адресацию с компактным представлением; в Java HashMap использует цепочки, которые при длинной коллизии превращаются в сбалансированное дерево.

# требования к ключу: хеш и равенство должны быть согласованы
class Point:
    __slots__ = ("x", "y")
    def __init__(self, x: int, y: int):
        self.x, self.y = x, y
    def __eq__(self, other) -> bool:
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)
    def __hash__(self) -> int:
        return hash((self.x, self.y))

Практика: что это значит в коде

1. Ключ обязан быть хешируемым и неизменяемым. Если объект изменяется после помещения в словарь, его хеш перестаёт соответствовать позиции, и значение становится ненаходимым. Это частая ошибка при использовании списков или собственных изменяемых классов в качестве ключей.

2. Согласованность __hash__ и __eq__. Если два объекта равны, их хеши обязаны совпадать. Обратное не требуется. Нарушение приводит к дублям, которые выглядят как разные ключи.

3. Плохая хеш-функция превращает O(1) в O(n). Если ключи сосредоточены в небольшом числе ячеек, каждая операция вырождается в обход цепочки. Для строк и чисел стандартные функции работают хорошо; риск возникает при собственных реализациях.

4. Резервируйте ёмкость заранее. Если известно, что в словарь попадёт миллион элементов, создание его с нужной ёмкостью избегает серии rehash. В Python это dict.fromkeys или предварительное заполнение; в других языках — параметр конструктора.

5. В базах данных hash-индекс — узкоспециальный инструмент. Hash-индексы в PostgreSQL поддерживают только проверку на равенство и не поддерживают диапазонные запросы и сортировку. Для большинства задач B-tree лучше — см. устройство B-tree.

CREATE INDEX sessions_token_hash ON sessions USING hash (token);
-- подойдёт только для WHERE token = '...'

6. Хеш как проверка, а не как замена. Хеш-значение удобно для быстрой проверки «изменилось ли», но при совпадении хешей нужна точная проверка. Вероятностная проверка принадлежности без хранения ключей — Bloom-фильтр.

Рекомендации:

1. Не используйте хеш как единственный идентификатор. Коллизии редки, но на больших объёмах становятся вероятными; при совпадении хешей сравнивайте сами данные.
2. Следите за распределением. Если в вашем кэше одна корзина содержит в разы больше элементов, чем другие, — проблема в хеш-функции или в характере ключей.
3. Помните про стоимость удаления при открытой адресации. Физическое удаление разрывает цепочки пробирования, поэтому используются маркеры, которые со временем требуют перестроения.
4. Оценивайте пиковую память. Rehash удваивает массив, поэтому в момент перестроения нужно место и под старый, и под новый массив.

Практический сценарий: деградация кэша после изменения формата ключа

Контекст: локальный кэш в процессе Python держал результаты вычислений. После изменения формата ключа время отклика выросло в четыре раза при том же числе записей.

1. Диагностика. Замерили распределение: из 65 536 корзин заполнены 1 100, но в 30 из них оказалось более 400 элементов.
2. Причина. Новый ключ формировался как строка вида tenant:region:date, где первые два компонента имели всего 12 комбинаций. Собственная хеш-функция брала хеш только от префикса до второго разделителя, поэтому ключи одного клиента попадали в одну корзину.
3. Исправление. Вернулись к стандартному hash() от кортежа (tenant, region, date). Распределение выровнялось: максимум 9 элементов в корзине.
4. Дополнительно. Добавили резервирование ёмкости при создании кэша, чтобы избежать серии rehash на старте, и метрику на максимальную длину цепочки.
5. Проверка. Прогнали тест с 200 тысячами ключей на реальном наборе клиентов и убедились, что распределение равномерное.

Вывод: хеш-таблица даёт O(1) только при равномерном распределении. Любая собственная схема формирования ключей или хеширования требует проверки распределения на реальных данных, а не на синтетических.

FAQ

Чем хеш-таблица отличается от сбалансированного дерева? Дерево даёт O(log n) и поддерживает порядок, диапазоны и обход по возрастанию. Хеш-таблица даёт O(1) в среднем, но не поддерживает порядок. Если нужны диапазонные запросы, хеш-таблица не подходит.

Что происходит при rehash и почему это заметно? Все элементы пересчитываются и переносятся в новый, больший массив. Операция линейна по числу элементов и требует памяти под оба массива одновременно. В системах с жёсткими требованиями к задержке это проявляется как периодические всплески.

Можно ли получить детерминированный порядок обхода? В Python порядок вставки сохраняется начиная с версии 3.7 как часть языковой спецификации. В других реализациях порядок обхода обычно не определён и может меняться после rehash.

Подходит ли хеш-таблица для хранения в памяти кэша? Да, это основная структура большинства кэшей и словарей в памяти, включая Redis-хеши. Но при большом объёме стоит учитывать расход памяти на каждый ключ — см. структуры Redis.

Источники: Python docs (hashable), PostgreSQL docs (hash indexes), Wikipedia (hash table) — ссылки в шапке.