Где ломается dict

В прошлом уроке мы узнали свойства хорошей хеш-функции: detereministic, uniform, fast. Сейчас разберём, что случается, когда хотя бы одно из них нарушается. Это не теория — на каждом из трёх свойств в реальной практике data engineer’ов ломаются прод-системы.

Что значит «плохой хеш»

Плохая хеш-функция — это функция, у которой хотя бы одно из трёх:

1. Слишком много коллизий — много разных ключей дают одинаковый хеш.
2. Неравномерность — хеши концентрируются в небольшой области.
3. Медлительность — хеш считается дольше, чем линейный поиск.

Каждое из этих свойств в отдельности превращает dict из O(1) в O(n) или хуже. Разберём по одному.

Коллизия: два разных ключа, один хеш

Коллизия — ситуация, когда hash(a) == hash(b) при a != b. Из-за

Вопрос не «бывают ли коллизии», а «как часто и насколько катастрофически». Для случайной hash-функции на 64 битах

# случайный пример коллизии в hash() для строк
# (зависит от seed, может потребоваться брутфорс)
import hashlib
for i in range(1_000_000):
    s = str(i)
    h = hash(s)
    # ищем строки с одним и тем же младшим байтом — это "псевдоколлизия"
    # внутри одного бакета dict

В реальной dict-таблице коллизии разрешаются

Эксперимент: что делает плохой хеш

Представьте, что вы реализовали свой класс User и определили __hash__ как «всегда 0»:

class BadUser:
    def __init__(self, user_id):
        self.user_id = user_id
    def __hash__(self):
        return 0   # ВСЕ user'ы имеют hash 0
    def __eq__(self, other):
        return self.user_id == other.user_id

# теперь положим в dict 10000 объектов
import time
d = {}
start = time.perf_counter()
for i in range(10_000):
    d[BadUser(i)] = i
elapsed = time.perf_counter() - start
print(f"{elapsed:.2f}s for 10K inserts")   # ~5-10 секунд

Вместо O(1) на вставку получаем O(n) — каждый раз dict приходится пробежать все занятые слоты. Это деградация до O(n^2) на полной вставке. С хорошим __hash__ это занимает ~5 миллисекунд. Разница — в 1000 раз.

Неравномерность

Даже если коллизий нет, хеш может быть «искажённым» — концентрировать значения в одной части диапазона. Пример: hash, который игнорирует первые 32 бита и хеширует только последние:

def bad_hash(s):
    return ord(s[0]) if s else 0   # хешируем только первую букву

# 26 уникальных значений на любой набор строк
# любой dict с такими строками будет иметь ~25 строк в каждом слоте уже на 600 ключах

Эту проблему сложно обнаружить визуально — хеши выглядят разными. Но если построить распределение hash(k) % 256 для 1000 ключей, видно, что вместо ~4 в каждом бакете оказывается по 40 в немногих и 0 в остальных.

Реальный случай — старые языковые хеши Java HashMap (до Java 8): хеши строк были предсказуемо плохими для определённых паттернов, и до Java 8 chaining не использовал tree, отчего lookup на коллизиях деградировал до O(n). Это и был источник

Медленный хеш

Третья проблема — хеш, который слишком долго считается. Если стоимость hash(k) сравнима со стоимостью линейного поиска по таблице, dict теряет преимущество.

import hashlib

class CryptoKey:
    def __init__(self, data):
        self.data = data
    def __hash__(self):
        # SHA-256 — криптографически стойкий, но в 50 раз медленнее SipHash
        return int.from_bytes(hashlib.sha256(self.data.encode()).digest()[:8], 'big')
    def __eq__(self, other):
        return self.data == other.data

# timeit показывает: на 1M операций SHA-256 хеш медленнее SipHash в 30-50 раз

Это легально, но платите вы за это в каждой операции с dict. Если у вас 10 миллионов lookup’ов, разница 50ns vs 2000ns даёт 20 секунд против 0.5. На прод-сервере это секундный лаг ответа.

Cryptographic vs non-cryptographic

Понимать разницу между двумя классами хеш-функций — must для DE.

В DE вы будете использовать обе:

• Non-cryptographic — в dict, set, для shuffle/partition в Spark, для dedup в потоке.
• Cryptographic — для дедупа по содержимому файлов (как в git: «один и тот же контент = один объект»), для верификации данных (etag в S3, checksum в HDFS), для подписи событий.

Почему Python hash для int — тождество

Может казаться странным: «hash(42) == 42». А не должна ли хеш-функция перемешивать биты?

Это дизайн-решение Python. Причины:

1. Скорость. hash(int) — самая частая операция в Python. Сделать её бесплатной — большой выигрыш.
2. Защиты от hash-flooding для int не нужно. Чтобы атаковать сервер коллизиями int, нужно подсовывать одно и то же число — это не атака, а просто повторение.
3. dict сам перемешивает через probing с perturbation (см. урок про probing). Даже если все ключи 0, 1, 2, ..., n, dict распределит их равномерно через специальную последовательность.

# демонстрация
print(hash(0))      # 0
print(hash(1))      # 1
print(hash(2**61))  # 0 — вырождение, потому что hash моделируется по mod (2^61 - 1)
print(hash(-1))     # -2, потому что -1 зарезервировано как маркер ошибки

Почему Python hash для str — SipHash 1-3

Для строк всё иначе. Строки приходят извне (от пользователя, из файла, по сети) — это значит, что злоумышленник может подобрать входы. Если бы hash был детерминистичный и публично известный, атакующий послал бы кучу строк с одинаковым хешем, и сервер виснет.

SipHash 1-3 решает это так:

1. Использует секретный ключ, который рандомизируется при старте Python. Без ключа предсказать хеш нельзя.
2. Достаточно быстрый — ~1 ns/байт, в 20-30 раз быстрее SHA-256.
3. Достаточно стойкий — найти коллизию практически невозможно без знания ключа.

«1-3» в названии — два числа раундов: 1 раунд compression на блок входа, 3 раунда finalization. Это компромисс между скоростью и стойкостью. Полный SipHash-2-4 был бы стойче, но Python предпочёл скорость.

# почему хеш строк меняется между запусками
# запустите дважды:
python -c "print(hash('data'))"
# 7283746273647262
python -c "print(hash('data'))"
# -1928374659283746

Если установить PYTHONHASHSEED=0, рандомизация отключается:

PYTHONHASHSEED=0 python -c "print(hash('data'))"
# всегда одно и то же число

Используйте PYTHONHASHSEED=0 только для отладки и тестов, никогда в продакшене.

Свой __hash__: правила, которые легко нарушить

Когда вы определяете __hash__ у класса, обязаны соблюдать три инварианта:

1. Если a == b, то hash(a) == hash(b). Иначе dict не найдёт ключ.
2. Hash не должен меняться за время жизни объекта. Поэтому считайте его от immutable полей.
3. hash и eq должны быть согласованы. Если переопределили один, переопределите второй.

Пример правильного __hash__:

class User:
    def __init__(self, user_id, name):
        self.user_id = user_id
        self.name = name

    def __hash__(self):
        # хешируем по user_id — это immutable бизнес-ключ
        return hash(self.user_id)

    def __eq__(self, other):
        if not isinstance(other, User):
            return NotImplemented
        return self.user_id == other.user_id

# теперь User можно класть в set и dict
users = {User(1, "Anna"), User(2, "Boris"), User(1, "Anna_v2")}
print(len(users))   # 2 — дубль по user_id отсеян

Если поле, по которому вы хешируете, изменится — объект потеряется в dict. Поэтому лучше всего делать dataclass(frozen=True), который заодно генерирует __hash__ и __eq__:

from dataclasses import dataclass

@dataclass(frozen=True)
class User:
    user_id: int
    name: str

# auto: __hash__ от (user_id, name), __eq__ по всем полям, нельзя менять

Попробуй сам

# 1. Сравните скорость хеша для разных длин строк
import timeit
for n in [10, 100, 1000, 10000, 100000]:
    s = "a" * n
    t = timeit.timeit(lambda: hash(s), number=1_000_000)
    print(f"len={n}: {t*1e9/1_000_000:.0f} ns per call")

# 2. Создайте dict с плохим __hash__ и измерьте время
class BadKey:
    def __init__(self, x): self.x = x
    def __hash__(self): return 1
    def __eq__(self, o): return self.x == o.x

import time
d = {}
start = time.perf_counter()
for i in range(5000):
    d[BadKey(i)] = i
print(f"bad: {time.perf_counter() - start:.2f}s")

# то же с хорошим хешем
d = {}
start = time.perf_counter()
for i in range(5000):
    d[i] = i
print(f"good: {time.perf_counter() - start:.4f}s")

# 3. Криптографический vs non-cryptographic
import hashlib
data = b"a" * 1000

t1 = timeit.timeit(lambda: hash(data), number=100_000)
t2 = timeit.timeit(lambda: hashlib.sha256(data).digest(), number=100_000)
print(f"SipHash:  {t1*1e9/100_000:.0f} ns")
print(f"SHA-256:  {t2*1e9/100_000:.0f} ns")

Ожидаемые наблюдения:

• Хеш строк растёт линейно от длины.
• Плохой hash замедляет dict в 100-1000 раз.
• SHA-256 медленнее SipHash в 5-15 раз для строки 1KB.

В следующем уроке посмотрим на dict как ADT — операции get/set/del и их сложность. А в модуле 9 уже залезем внутрь Python dict — увидим, как именно перемешиваются биты в probing и почему resize важен.