Хеш-таблица: как работает, коллизии и реализация на Python

Хеш-таблица хранит пары ключ-значение в массиве и вычисляет индекс прямо из ключа, поэтому поиск, вставка и удаление элементов в среднем выполняются за константное время O(1). В худшем случае, когда много элементов попадает в одну ячейку, те же операции хеш-таблицы стоят O(n). Код прогнан на 64-битном CPython 3.14.3 под Windows 10.

Что такое хеш-таблица простыми словами

Хеш-таблица состоит из двух частей: массива заданного размера, позиции которого называют корзинами (bucket), и хеш-функции, которая превращает ключ в целое число. Из числа получают индекс массива, туда и ложится пара ключ-значение.

Чтобы найти строку в списке из миллиона элементов, программа в худшем случае просмотрит их все. Бинарный поиск по отсортированному массиву сделает около 20 сравнений. Хеш-таблица в среднем смотрит одну-две позиции. Платят за это памятью (часть массива всегда пустая) и порядком: для диапазона ключей (все от A до B) лучше отсортированный массив или дерево.

Как работает хеш-таблица: от ключа к индексу

hash(key) даёт целое число, а остаток от деления на размер массива даёт индекс. При размере массива в степень двойки остаток заменяют маской: берут младшие биты. Свойства функции разобраны в статье про хеш-функции. Для работы хеш-таблицы важны два правила: равные ключи дают одинаковый hash, и hash ключа не меняется, пока ключ лежит в таблице. Поэтому список ключом словаря быть не может: он изменяемый, и попытка падает с TypeError: unhashable type: 'list'.

У небольших неотрицательных целых чисел в CPython hash равен самому числу, например hash(3) возвращает 3. Здесь в примерах ключи целые, чтобы раскладка совпадала с выводом при любом запуске: hash строки солится случайным значением при каждом старте интерпретатора.

Коллизии и почему худший случай O(n)

Ключей бесконечно много, а корзин конечное число, поэтому два ключа рано или поздно получат один индекс. Совпадение называют коллизией: например, при восьми корзинах у ключей 3, 11 и 19 одинаковый остаток от деления, 3. Хорошая хеш-функция делает коллизии редкими, но не убирает, и реализация хеш-таблицы обязана их разрешать. Основных способов два: метод цепочек и открытая адресация.

Оценка O(1) держится на допущении, что элементы разбросаны по массиву равномерно. Если у всех элементов один hash, хеш-таблица превращается в список, и каждый новый сравнивается со всеми, кто уже лежит в этой корзине.

Метод цепочек: реализация на Python

В методе цепочек (chaining) корзина хранит список пар, и коллизия просто удлиняет его. Поиск считает индекс, затем идёт по короткому списку. Наша хеш-таблица перестраивается (rehash), когда количество элементов превышает 0,75 от числа корзин:

class ChainHashTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        chain = self.bucket(key)
        for pair in chain:
            if pair[0] == key:           # ключ уже есть: меняем значение
                pair[1] = value
                return
        chain.append([key, value])
        self.count += 1
        if self.count > 0.75 * len(self.buckets):
            self.rehash()

    def get(self, key):
        for k, v in self.bucket(key):
            if k == key:
                return v

    def rehash(self):
        old = [pair for chain in self.buckets for pair in chain]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        for pair in old:                 # индексы считаем заново
            self.bucket(pair[0]).append(pair)


table = ChainHashTable()
for key in (3, 11, 19):                  # 3 % 8, 11 % 8 и 19 % 8 дают 3
    table.put(key, key * 10)
print(table.buckets[3])
print(table.get(11), table.get(27))
for key in range(100, 106):
    table.put(key, key)
print(len(table.buckets))

[[3, 30], [11, 110], [19, 190]]
110 None
16

Три ключа легли цепочкой в корзину 3. get(11) прошёл по ней и вернул 110, а get(27) проверил ту же корзину (27 % 8 тоже 3), не нашёл ключ и вернул None. Потом к трём элементам добавили шесть. Когда элементов стало семь, 7 > 0,75 × 8, и rehash удвоил таблицу до 16 корзин. Индекс при перестройке считается заново: он зависит от размера массива. Удаление в цепочке простое: найти пару в списке и вырезать её. Заполнение больше единицы цепочки тоже терпят.

Открытая адресация

При открытой адресации (open addressing) в каждой позиции массива не больше одной пары, а при коллизии элемент ищет другое место по заданному правилу. Последовательность проверенных позиций называют пробированием:

1. Линейное: i, i+1, i+2 и дальше по кругу. Самый простой вариант, но занятые ячейки слипаются в участки: элемент, чей индекс попал в участок, ложится в первую свободную ячейку за ним и удлиняет его.
2. Квадратичное: шаг растёт на единицу, смещения 1, 3, 6, 10. При размере таблицы, равном степени двойки, такая последовательность обходит все ячейки, а от слипания такое пробирование страдает меньше линейного.
3. Двойное хеширование: шаг даёт вторая хеш-функция, у каждого элемента свой. Шаг не может быть нулём и должен быть взаимно прост с размером таблицы; при размере 2^k достаточно нечётного.

Удаление элемента и надгробия

Поиск идёт по последовательности проб до первого пустого места. Если при удалении элемента просто очистить позицию в её середине, элементы за ней станут невидимы. Поэтому на месте удалённого элемента оставляют метку-надгробие (tombstone), которую поиск проходит насквозь:

DELETED = (object(), None)               # надгробие: его ключ не равен ничему


class OpenHashTable:
    def __init__(self, size=8):
        self.slots = [None] * size       # None, DELETED или (key, value)

    def find(self, key):                 # линейное пробирование: i, i+1, i+2...
        i = hash(key) % len(self.slots)
        while self.slots[i] is not None and self.slots[i][0] != key:
            i = (i + 1) % len(self.slots)
        return i                         # найденная или первая пустая позиция

    def put(self, key, value):           # без rehash: заполнение держим ниже 1/2
        self.slots[self.find(key)] = (key, value)

    def get(self, key):
        slot = self.slots[self.find(key)]
        return None if slot is None else slot[1]

    def delete(self, key, tombstone=True):
        i = self.find(key)
        if self.slots[i] is not None:
            self.slots[i] = DELETED if tombstone else None


for tombstone in (False, True):
    table = OpenHashTable()
    for key in (1, 9, 17):               # всем трём нужна позиция 1
        table.put(key, key * 10)
    table.delete(9, tombstone)
    print(["x" if s is DELETED else s and s[0] for s in table.slots], table.get(17))

[None, 1, None, 17, None, None, None, None] None
[None, 1, 'x', 17, None, None, None, None] 170

Ключ 1 занял позицию 1, 9 ушёл во вторую, 17 в третью. В первой строке 9 удалили очисткой: поиск 17 дошёл до пустой позиции 2 и вернул None, хотя элемент на месте. Во второй строке там надгробие 'x': его ключ не совпадает ни с одним, find идёт дальше и находит 170. Наша put надгробия не занимает. Занимать их можно, но только после проверки, что дальше в последовательности проб такого ключа нет, иначе в таблице окажутся два одинаковых.

Надгробия входят в заполнение так же, как живые элементы. При частых удалениях и вставках массив забивается метками, поэтому их учитывают в коэффициенте и выбрасывают при перестройке.

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

Коэффициент заполнения (load factor) α равен количеству элементов, делённому на размер массива. Для линейного пробирования теоретическая оценка такая: успешный поиск около ½(1 + 1/(1-α)) проб, промах около ½(1 + 1/(1-α)²). Проверим три способа на хеш-таблице из 16 384 ячеек со случайными целыми числами: ищем все вставленные элементы и столько же отсутствующих.

import random
import time

SIZE = 2 ** 14                           # 16 384 ячейки

STRATEGIES = {
    "линейное": lambda key, i: (key + i) % SIZE,
    "квадратичное": lambda key, i: (key + i * (i + 1) // 2) % SIZE,
    "двойное": lambda key, i: (key + i * ((key // SIZE) | 1)) % SIZE,
}


def probes(slots, key, probe):           # число проб до совпадения или пустой ячейки
    i = 0
    while slots[probe(key, i)] not in (None, key):
        i += 1
    return i + 1


random.seed(2026)
for load in (0.5, 0.75, 0.9):
    n = int(SIZE * load)
    keys = random.sample(range(2 ** 40), 2 * n)
    present, absent = keys[:n], keys[n:]
    for name, probe in STRATEGIES.items():
        slots = [None] * SIZE
        for key in present:
            slots[probe(key, probes(slots, key, probe) - 1)] = key
        start = time.perf_counter()
        miss = sum(probes(slots, key, probe) for key in absent) / n
        mcs = (time.perf_counter() - start) / n * 1e6
        hit = sum(probes(slots, key, probe) for key in present) / n
        print(f"{load:<5}{name:<13}{hit:5.2f}{miss:7.2f}{mcs:6.1f} мкс")

0.5  линейное      1.49   2.48   0.5 мкс
0.5  квадратичное  1.42   2.13   0.5 мкс
0.5  двойное       1.39   2.01   0.9 мкс
0.75 линейное      2.38   7.59   1.3 мкс
0.75 квадратичное  1.97   4.59   1.0 мкс
0.75 двойное       1.84   4.06   1.1 мкс
0.9  линейное      5.08  43.09   6.9 мкс
0.9  квадратичное  2.85  11.94   2.9 мкс
0.9  двойное       2.55  10.09   3.2 мкс

Колонки: проб на успешный поиск, на промах и время одного промаха. У линейного результат близок к оценке (1,5 и 2,5; 2,5 и 8,5; 5,5 и 50,5), на высоком заполнении замер чуть ниже оценки. На заполнении 0,9 промах стоит ему 43 пробы, квадратичному и двойному 10-12. Время мерили на Core i9-9900KF: при повторных запусках оно расходится на десятые доли, число проб не меняется, генератор зафиксирован random.seed(2026). Время относится к чистому Python, о скорости dict оно не говорит.

Чтобы не доходить до 0,9, таблицу расширяют заранее: выделяют массив вдвое больше и раскладывают все элементы заново. Перестройка стоит O(n), но бывает редко, и в пересчёте на одну вставку остаётся O(1).

Как устроен dict в Python

Встроенный dict в CPython построен на открытой адресации, set устроен похоже. С версии 3.6 словарь компактный: саму хеш-таблицу образует массив индексов dk_indices, а пары лежат в массиве dk_entries в порядке вставки. Язык гарантирует этот порядок с Python 3.7. Удалённый элемент оставляет в массиве индексов метку DKIX_DUMMY, то же надгробие.

Начальный размер таблицы 8, заполнять можно до двух третей. Индекс берётся из младших битов hash, при коллизии следующий считается как j = 5*j + 1 + perturb, где perturb хранит hash и на каждом шаге сдвигается вправо на 5 бит. Код ниже показывает, когда растёт словарь и сколько сравнений стоит худший случай:

import sys

d = {}
last = sys.getsizeof(d)
for n in range(1, 44):
    d[n] = n
    if sys.getsizeof(d) != last:
        last = sys.getsizeof(d)
        print(f"после {n}-й вставки: {last} байт")


class SameHash:                          # у всех объектов один hash
    calls = 0

    def __init__(self, n):
        self.n = n

    def __hash__(self):
        return 42

    def __eq__(self, other):
        SameHash.calls += 1
        return self.n == other.n


for n in (100, 200, 400):
    SameHash.calls = 0
    table = {SameHash(i): i for i in range(n)}
    print(f"{n} элементов: {SameHash.calls} сравнений")

после 1-й вставки: 224 байт
после 6-й вставки: 352 байт
после 11-й вставки: 632 байт
после 22-й вставки: 1168 байт
после 43-й вставки: 2264 байт
100 элементов: 5039 сравнений
200 элементов: 20089 сравнений
400 элементов: 80131 сравнений

Пустой словарь своей таблицы не держит, она появляется с первой вставкой. Дальше размер скачет на 6-й, 11-й, 22-й и 43-й вставке: две трети от 8, 16, 32 и 64 дают 5, 10, 21 и 42 элемента, и следующий уже вызывает расширение.

Последние три строки показывают худший случай: при одном hash на всех новый элемент сравнивается через __eq__ с уже вставленными. Элементов вдвое больше, сравнений вчетверо, примерно n²/2; на 100 тысячах элементов по той же формуле вышло бы около пяти миллиардов. __hash__ с константой годится для такого опыта и вреден в рабочем коде.

Хеш-таблицы в других языках программирования

Готовая хеш-таблица есть и в других языках, и для рабочего кода свою писать незачем. В Java такая структура называется HashMap: коэффициент заполнения по умолчанию 0,75, при превышении корзин становится примерно вдвое больше. В C++ std::unordered_map раскладывает элементы по корзинам по hash ключа. В PowerShell таблицу создают литералом @{ name = value }, порядок ключей в ней не определён.

В стандартной библиотеке C хеш-таблицы нет. В POSIX существует пара hcreate и hsearch, но ключ там только строка и одновременно работает одна таблица. На C хеш-таблицу пишут сами или берут стороннюю библиотеку.

Где пригодится хеш-таблица

Частоту слов считает collections.Counter, подкласс dict, дубликаты ищут через set. @lru_cache хранит результаты в словаре, поэтому аргументы должны быть хешируемыми, пример есть в статье про декораторы Python. Хеш-индекс в PostgreSQL умеет только сравнение на равенство, подробнее в разборе индексов в SQL.

Частые вопросы

Чем метод цепочек отличается от открытой адресации?

В цепочках коллизии складываются в список внутри корзины, удаление простое, заполнение может быть больше единицы. При открытой адресации пары лежат в самом массиве, удаление требует надгробий, заполнение держат заметно ниже единицы. dict в Python использует открытую адресацию.

Какой коэффициент заполнения выбрать для своей таблицы?

Для цепочек ориентир 0,75, как в Java. Для открытой адресации не выше 2/3, как в CPython, а при линейном пробировании лучше около 0,5: в нашем замере на 0,9 промах стоил ему 43 пробы.