Хеш-таблица как «поиск»

В модулях 7 и 8 мы детально разбирали хеш-таблицы. Здесь возвращаемся к ним под другим углом: как к алгоритму поиска.

Хеш-таблица отвечает на вопрос «есть ли тут такой ключ?» за O(1) в среднем — это в десять-сто раз быстрее бинарного поиска O(log n). Кажется, что хеш всегда лучше. Это не так. У хеша есть жёсткое ограничение, которое забывают: он работает только с equality, и больше ни с чем.

users = {"alice": 25, "bob": 30, "carol": 35}

# работает: equality
print("alice" in users)          # True, O(1)
print(users.get("bob"))          # 30, O(1)

# НЕ работает: range, min, max, next-after
# нет ни одного способа сделать это за O(1) на dict:
# - сколько ключей лежит между "a" и "c"?
# - какой минимальный ключ?
# - какой ключ идёт сразу после "alice"?

Хеш-таблица «размешивает» ключи по бакетам. После хеширования порядок теряется. Это её сила (O(1) lookup) и одновременно её ограничение (нет порядка — нет range queries).

Главное правило выбора

Если нужны только проверки equality — используйте dict/set. Это самый быстрый случай, O(1).

Если нужны range/min/max/order — используйте sorted-структуры (list+bisect или SortedList). Платите O(log n), но получаете порядок.

Это правило важнее, чем «log n больше единицы». Если хеш не умеет ответить на ваш вопрос — его преимущество в скорости неактуально.

Когда O(1) внезапно становится O(n)

Хеш-таблица обещает O(1) в среднем. В худшем случае — O(n), когда все ключи хешируются в один бакет (коллизии). На практике это редкость, но возможна при:

1. Плохой хеш-функции. Если кто-то реализовал __hash__ так, что много ключей даёт одно значение. Например, hash(obj) = len(obj) — катастрофа.
2. Намеренной атаке (hash collision attack). Злоумышленник подбирает ключи, специально вызывающие коллизии. С Python 3.4+ есть randomized hash для строк — защита от этого. В сетевых сервисах с пользовательским вводом это важно.
3. Очень плотном заполнении. Когда load factor приближается к 1, коллизий много даже при хорошей хеш-функции. Python пересоздаёт таблицу при load factor около 2/3.

В наших дата-задачах коллизии редки. Но если кто-то говорит «у нас dict замедлился» — первое, что я проверяю: какой __hash__ у ключа. Если это самописный объект — возможно, хеш плохой.

Что выбрать в типичных задачах DE

Дедупликация event_id в батче. Equality. set — идеально, O(n).

Поиск ближайшего timestamp в индексе. Range. SortedList или sorted list + bisect.

Range query по времени between(t1, t2). Range. Sorted, без вариантов.

Подсчёт уникальных пользователей. Equality + count. Counter (dict).

Поддержание top-K по active_users. Min/extremum + frequent insert/delete. Heap (модуль 11) или SortedList.

Lookup по user_id для join. Equality. dict, O(1) на каждый lookup.

Объединённое сравнение

Гибридные решения

Часто оптимальное решение — сочетание структур.

dict + SortedList для top-K и lookups. Когда нужен и быстрый поиск по ключу, и top-K по значению.

from sortedcontainers import SortedList

class TopKByScore:
    def __init__(self):
        self.scores = {}                    # user_id -> score
        self.sorted = SortedList()          # отсортированные пары (score, user_id)

    def update(self, user_id, new_score):
        if user_id in self.scores:
            old_score = self.scores[user_id]
            self.sorted.remove((old_score, user_id))   # O(log n)
        self.scores[user_id] = new_score
        self.sorted.add((new_score, user_id))          # O(log n)

    def top_k(self, k):
        return [u for _, u in self.sorted[-k:]]        # O(k)

    def score_of(self, user_id):
        return self.scores.get(user_id, 0)             # O(1)

Здесь dict даёт O(1) lookup по user_id, SortedList — O(log n) on top-K. Оба вместе покрывают все нужные операции.

Bloom filter + dict для дедупликации. Bloom отвечает «точно нет» за O(1) с маленькой памятью, dict — точная проверка для редких случаев «возможно есть». Об этом — модуль 18.

Итог: что когда применять

Сведём в одну таблицу:

В Data Engineering на эти 7 строк приходится примерно 95% всех структур данных. Дальше — heap, deque, graph, и совсем редко — что-то экзотическое.

Попробуй сам

Эксперимент: одни и те же 1 миллион пар (id, timestamp). Нужно:

1. Проверить, есть ли событие с конкретным id (equality).
2. Найти события с timestamp между t1 и t2 (range).
3. Найти самое раннее и самое позднее событие (min, max).

import random
from sortedcontainers import SortedList
import timeit

n = 1_000_000
data = [(i, random.random() * 1_000_000) for i in range(n)]

# вариант A: dict для id-lookup + sorted list для time-range
id_to_ts = {i: ts for i, ts in data}
sorted_by_ts = SortedList(ts for _, ts in data)

# 1. equality по id
print(50_000 in id_to_ts)                        # O(1)

# 2. range query по time
import bisect
left = sorted_by_ts.bisect_left(100_000)
right = sorted_by_ts.bisect_right(200_000)
print(f"events in [100k, 200k]: {right - left}")  # O(log n)

# 3. min, max
print(f"earliest: {sorted_by_ts[0]}")             # O(1) после построения
print(f"latest: {sorted_by_ts[-1]}")              # O(1) после построения

Замерьте, сколько занимают эти операции. Сравните с наивной реализацией через линейный проход — увидите разницу в 1000-10000 раз.