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

Словарь в Python находит значение по ключу за одно и то же время, даже если ключей миллиард — и это одна из самых недооценённых идей в программировании.

Хеш-таблица — это попытка превратить «искать» в «вычислять адрес напрямую».

Проблема: где хранить, чтобы быстро искать

Чтобы найти элемент в неупорядоченном списке, надо перебрать всё — $O(n)$. В отсортированном массиве выручает бинарный поиск — $O(\log n)$. Но можно ли искать за постоянное время, не зависящее от размера? Если бы мы заранее знали точный адрес ячейки, где лежит значение, поиск свёлся бы к одному обращению по адресу. Хеш-таблица именно это и устраивает.

Идея: пусть ключ сам подскажет адрес

Возьмём массив (его называют корзинами, buckets) и функцию, которая по ключу выдаёт индекс в этом массиве. Эта функция и есть хеш-функция. Хотим сохранить пару «ключ → значение»? Вычисляем $h(\text{ключ})$, получаем индекс, кладём туда. Хотим найти? Снова вычисляем $h(\text{ключ})$ — и сразу знаем, в какой корзине смотреть. Никакого перебора. Хорошая хеш-функция должна разбрасывать ключи равномерно и считаться быстро:

$$\text{индекс} = h(\text{ключ}) \bmod m, \quad m = \text{число корзин}$$

Коллизии: два ключа в одну корзину

Корзин конечное число, а ключей может быть сколько угодно. Рано или поздно два разных ключа дадут один индекс — это коллизия, и она неизбежна (по принципу Дирихле: если объектов больше, чем ящиков, какой-то ящик получит двоих). Вся инженерия хеш-таблиц — про то, как с коллизиями жить. Самый наглядный способ — метод цепочек: в каждой корзине лежит маленький список, и при коллизии новые пары просто дописываются туда. При поиске мы вычисляем корзину, а внутри неё перебираем короткий список.

class HashTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]  # цепочки

    def _index(self, key):
        return hash(key) % self.size              # хеш -> индекс корзины

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)          # обновляем существующий
                return
        bucket.append((key, value))               # либо добавляем новый

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for k, v in bucket:                       # перебор только внутри корзины
            if k == key:
                return v
        raise KeyError(key)

t = HashTable()
t.put("яблоко", 50)
t.put("банан", 30)
t.put("вишня", 80)
print(t.get("банан"))   # 30
print(t.get("вишня"))   # 80

Почему в среднем O(1)

Если ключи раскиданы по корзинам равномерно, то в каждой корзине лежит в среднем $\alpha = n / m$ элементов — это коэффициент заполнения. Пока $\alpha$ держится небольшим (обычно таблица растёт и перехешируется, когда заполнение превышает порог вроде 0,7), длина каждой цепочки — почти константа. Тогда и вставка, и поиск — $O(1)$ в среднем. Именно поэтому словарь на миллион ключей ищет так же быстро, как на десять: размер цепочки не растёт, потому что вместе с числом ключей растёт и число корзин.

Тёмная сторона: худший случай O(n)

Если хеш-функция плохая или злоумышленник специально подберёт ключи, дающие один и тот же индекс, все элементы свалятся в одну корзину. Тогда хеш-таблица выродится в обычный список, и поиск станет $O(n)$. На этом основаны реальные DoS-атаки на веб-серверы (Hash Flooding): подсунуть запрос с ключами-коллизиями и заставить сервер перебирать гигантскую цепочку. Защита — криптостойкие или рандомизированные хеши с секретным зерном, которое атакующий не знает.

Где она повсюду

Хеш-таблица — это dict в Python, HashMap в Java, объекты в JavaScript, индексы в базах данных, кеши, множества уникальных элементов. Когда вы пишете if key in cache и это срабатывает мгновенно — спасибо хешированию. Это, возможно, самая используемая нетривиальная структура данных в мире.

Мораль

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