Зачем смотреть на коллизии глубже
В предыдущих уроках мы упомянули коллизии: разные ключи получают одинаковый хеш, dict ищет следующий слот через probing. Звучит как небольшая неудобство. Но при патологических данных dict теряет O(1) и превращается в O(n) на каждую операцию. Это даёт квадратичную деградацию полной загрузки таблицы.
Этот урок — о том, как именно это происходит, как это увидеть в эксперименте, и какие защиты дают современные hash-таблицы.
Два типа кластеризации
Коллизии вызывают два разных феномена:
- Primary clustering — соседние слоты сливаются в длинные комки. Возникает в linear probing. Решается perturbation в Python.
- Secondary clustering — ключи с одинаковым полным хешем попадают в одну цепочку пробирования. Это нерешаемо в open addressing: одинаковые хеши дают одинаковую probing-последовательность.
Первое — про соседние слоты. Второе — про идентичные хеши.
Эксперимент: подобранные коллизии
Самый драматичный способ показать деградацию — создать класс, чей __hash__ возвращает константу:
class BadKey:
"""Все экземпляры имеют hash == 1. Симулирует атаку коллизиями."""
def __init__(self, value):
self.value = value
def __hash__(self):
return 1
def __eq__(self, other):
return isinstance(other, BadKey) and self.value == other.value
def __repr__(self):
return f"BadKey({self.value})"
# для сравнения — нормальный класс
class GoodKey:
def __init__(self, value):
self.value = value
def __hash__(self):
return hash(self.value)
def __eq__(self, other):
return isinstance(other, GoodKey) and self.value == other.valueТеперь измерим вставку 5000 ключей:
import time
for size in [500, 1000, 2000, 5000, 10000]:
# bad
d = {}
start = time.perf_counter()
for i in range(size):
d[BadKey(i)] = i
t_bad = time.perf_counter() - start
# good
d = {}
start = time.perf_counter()
for i in range(size):
d[GoodKey(i)] = i
t_good = time.perf_counter() - start
print(f"n={size:>5d}: bad={t_bad*1000:>8.1f}ms good={t_good*1000:>6.2f}ms ratio={t_bad/t_good:>6.0f}x")Типичный вывод:
n= 500: bad= 25.4ms good= 0.10ms ratio= 254x
n= 1000: bad= 105.2ms good= 0.21ms ratio= 501x
n= 2000: bad= 425.7ms good= 0.43ms ratio= 990x
n= 5000: bad= 2780.3ms good= 1.05ms ratio= 2648x
n=10000: bad= 11420.5ms good= 2.15ms ratio= 5312xДва важных наблюдения:
- good time растёт линейно: O(n) total, O(1) per insert.
- bad time растёт квадратично: с 2× размером в 4× больше времени. Это O(n²) total, O(n) per insert.
При n=10000 разница уже 5300×. На n=100000 разница достигнет 500000× — bad будет считаться часами.
Откуда O(n²) при одинаковых хешах
Вставка №k делает следующее:
- Hash = 1 (всегда). Начальный slot =
1 & mask. - Если слот занят, probing идёт по
5*j + 1 + perturb. Поскольку perturb тоже одинаков для всех ключей (== 1), последовательность одна и та же! - Когда perturb >>= 5, он быстро становится 0 (за 1 итерацию из 1). Остаётся чисто
5*j + 1 mod size.
Итог: probing-цепочка для всех BadKey одинакова. Вставка k-го ключа должна пройти k-1 занятых слотов в этой цепочке, проверяя для каждого __eq__. Это O(k) на вставку, O(n²) на полную загрузку n ключей.
вставка #1: 1 шаг (нашли пустой slot сразу)
вставка #2: 2 шага (slot занят, прыгнули, нашли пустой)
вставка #3: 3 шага
...
вставка #n: n шагов
общее число шагов = 1 + 2 + ... + n = n(n+1)/2 = O(n²)Hash-flooding атаки в реальной жизни
Этот эксперимент кажется искусственным. Но в 2011 году исследователи показали, что точно такая атака работает на серверах с предсказуемыми hash-функциями. CVE-2011-3414: уязвимость в Apache Tomcat, PHP, Ruby, Python (до 3.3).
Сценарий:
- Атакующий знает алгоритм хеширования (для FNV или SipHash без seed это публично).
- Подбирает тысячи строк с одинаковым хешем.
- Шлёт их сервером как form-параметры или JSON-ключи.
- Сервер кладёт их в HashMap/dict.
- Каждый запрос становится O(n²), CPU виснет.
Один HTTP-запрос с 5000 параметров с одинаковыми хешами займёт у Python pre-3.3 12+ секунд CPU. Несколько таких запросов в секунду — и сервер недоступен.
Защита: рандомизация SipHash seed при старте процесса. Атакующий не может подобрать коллизии заранее, потому что не знает seed. Это и есть «PYTHONHASHSEED=random» по умолчанию.
Demo: dict tools Python
Python предоставляет специальные методы для анализа dict:
import sys
# 1. getsizeof — размер dict в байтах
d = {i: i for i in range(100)}
print(sys.getsizeof(d)) # обычно ~4760 байт
# 2. через ctypes можно посмотреть capacity
import ctypes
class PyDictObject(ctypes.Structure):
_fields_ = [
("ob_refcnt", ctypes.c_ssize_t),
("ob_type", ctypes.c_void_p),
("ma_used", ctypes.c_ssize_t),
("ma_version_tag", ctypes.c_uint64),
("ma_keys", ctypes.c_void_p),
("ma_values", ctypes.c_void_p),
]
# но это hack, и зависит от CPython версии
# 3. Простая оценка load factor через getsizeof + len
def estimate_load_factor(d):
bytes_per_slot = 24 # me_hash + me_key + me_value
overhead = 200 # header dict
bytes_in_slots = sys.getsizeof(d) - overhead
approx_capacity = bytes_in_slots / bytes_per_slot
return len(d) / approx_capacity if approx_capacity > 0 else 0
d = {i: i for i in range(100)}
print(f"load factor ~= {estimate_load_factor(d):.2f}") # ~0.39Что делать, если коллизии возможны
В реальной DE-работе вы редко сталкиваетесь с намеренно подобранными коллизиями. Но случайные коллизии бывают:
- Плохой
__hash__в custom классе. Например, забыли учесть важное поле, и многие объекты получают одинаковый хеш. Это даёт линейную деградацию. - Несбалансированные данные. Например, поле user_id для большинства записей = NULL. Этих записей много, у всех одинаковый хеш(None) = 0.
- Hash-сторонние коллизии в распределённых системах (Spark, Hadoop). Если 70% записей хешируются в один shard — data skew.
Защиты:
- Хороший
__hash__: использоватьhash(tuple of all important fields)или@dataclass(frozen=True). - Salting: для случаев data skew — добавлять случайный суффикс к доминирующим ключам.
- Avoid hash-flood-prone inputs: не делайте dict из пользовательских строк без рандомизированной hash-функции.
Tombstone’ы и удалённые слоты
Тонкая деталь: при del d[k] слот не освобождается, иначе probing после этого слота сломался бы. Вместо этого ставится tombstone — специальная метка «удалено, но не свободно».
Без tombstone (неправильно):
[k1, k2, k3, k4] -- вставили
[k1, ?, k3, k4] -- удалили k2, поставили None
-- но если k3 пришёл сюда через probing от k2,
-- lookup(k3) увидит None и решит "ключ отсутствует"
С tombstone:
[k1, T, k3, k4] -- удалили k2, поставили T
-- lookup(k3) пропустит T и продолжит probing
-- insert k5 может использовать T-слотTombstone’ы освобождаются только при resize. Поэтому dict с интенсивными insert/delete циклами может расти по памяти, даже если число активных элементов не растёт. Решение: периодически делать d = dict(d.items()) или d = d.copy() — это создаст чистый dict.
Если вы определяете __hash__ у custom класса и забываете включить важное поле, можете нечаянно создать сценарий, эквивалентный коллизионной атаке. На 10К объектах разница между хорошим и плохим __hash__ достигает 5000×. Тестируйте: создайте N объектов, положите в dict, измерьте время. Если линейный рост — всё ок; если квадратичный — у вас плохой __hash__.
Попробуй сам
import time
class BadKey:
def __init__(self, v): self.v = v
def __hash__(self): return 1
def __eq__(self, o): return isinstance(o, BadKey) and self.v == o.v
class GoodKey:
def __init__(self, v): self.v = v
def __hash__(self): return hash(self.v)
def __eq__(self, o): return isinstance(o, GoodKey) and self.v == o.v
# 1. Подтвердите O(n²) для BadKey
sizes = [500, 1000, 2000, 4000]
times = []
for n in sizes:
d = {}
start = time.perf_counter()
for i in range(n):
d[BadKey(i)] = i
t = time.perf_counter() - start
times.append(t)
print(f"n={n}: {t*1000:.0f} ms")
# проверьте: time(2n) / time(n) ~= 4 для O(n²)
for i in range(1, len(times)):
ratio = times[i] / times[i-1]
print(f"n={sizes[i]}/n={sizes[i-1]}: ratio = {ratio:.1f} (ожидаем ~4)")
# 2. Полу-плохой ключ: одинаковый хеш для каждых 10 объектов
class HalfBad:
def __init__(self, v): self.v = v
def __hash__(self): return self.v // 10 # коллизия каждых 10
def __eq__(self, o): return isinstance(o, HalfBad) and self.v == o.v
d = {}
start = time.perf_counter()
for i in range(10_000):
d[HalfBad(i)] = i
t = time.perf_counter() - start
print(f"\nHalf-bad: {t*1000:.0f} ms (small constant penalty, NOT O(n^2))")
# 3. Симулируйте data skew
# создайте 100K dict-ключей, где 80% = None
data = [None] * 80_000 + list(range(20_000))
d = {}
for k in data:
d.setdefault(k, []).append(1)
# на этом примере dict[None] получит миллионы элементов
print(f"dict[None] = {len(d[None])} elements")В следующем уроке посмотрим на set — близкого родственника dict, и посчитаем сложность операций union/intersection. А пока запомните: hash-таблица быстрая, пока хеши уникальны. Любая систематическая коллизия превращает O(1) в O(n).