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

Представьте библиотеку, где не нужно идти вдоль полок — вы сразу знаете, на какой полке лежит книга.

Хеш-таблица не ищет ваш ключ перебором. Она вычисляет, где он должен лежать, и идёт прямо туда.

Проблема: поиск в куче

Допустим, у вас список из миллиона пар «имя — телефон», и нужно найти телефон Ани. Если данные лежат в обычном массиве, придётся проверять элемент за элементом, пока не наткнётесь на нужный. В худшем случае — миллион сравнений. Это медленно, и чем больше данных, тем хуже.

Хочется волшебства: назвал имя — мгновенно получил телефон, не перебирая остальных. Именно это делает хеш-таблица, и на ней построен dict в Python, объекты в JavaScript, HashMap в Java.

Идея: превратить ключ в адрес

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

Ключевое слово — напрямую. Мы не сравниваем «Аню» со всеми именами. Мы один раз считаем, где она должна быть, и сразу туда идём. Поэтому поиск занимает примерно одинаковое время и при тысяче записей, и при миллионе. На языке информатики это называется временем O(1) — «константное».

Что такое хорошая хеш-функция

Она должна, во-первых, для одного и того же ключа всегда давать один и тот же результат. Во-вторых — раскидывать разные ключи по ячейкам как можно равномернее, чтобы они не сбивались в кучу. И в-третьих — считаться быстро. Хорошая функция ведёт себя так, будто перемешивает биты ключа: меняешь в имени одну букву — адрес меняется до неузнаваемости.

Коллизии: когда двое метят в одну ячейку

Ячеек конечное число, а ключей может быть сколько угодно. Рано или поздно два разных ключа дадут один и тот же адрес. Это называется коллизия, и это не ошибка, а неизбежность.

Решают её по-разному. Частый приём — в каждой ячейке держать не одно значение, а маленький список. Если в ячейку попали и «Аня», и «Ваня», там окажется список из двух пар, и среди них уже идёт короткий перебор. Пока списки крошечные, скорость почти не страдает.

Почему таблица иногда «вырастает»

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

Увидеть своими глазами

Наивная хеш-таблица на пару десятков строк — отличный способ понять идею:

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

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:      # ключ уже есть — обновляем
                pair[1] = 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
        return None

d = MiniDict()
d.put("Аня", "+7-900-111")
d.put("Ваня", "+7-900-222")
print(d.get("Аня"))
print(d.get("Петя"))   # такого ключа нет

Здесь _index — наша хеш-функция: берём встроенный hash и сворачиваем по размеру массива остатком от деления. Внутри ячейки — список пар, чтобы пережить коллизии.

Где это в жизни

Хеш-таблицы повсюду, просто незаметно. Кеш браузера ищет страницу по адресу. База данных по индексу мгновенно находит строку. Антивирус сверяет хеш файла со списком известных угроз. Каждый раз, когда что-то находится «сразу, без поиска», под капотом почти наверняка стоит хеш-таблица.

Главная мысль простая: вместо того чтобы искать, хеш-таблица вычисляет место. Этот трюк — «посчитать адрес вместо перебора» — одна из самых полезных идей во всём программировании.