Как работает dict внутри? Почему доступ по ключу обычно O(1)?

Пример

import sys


# Размер таблицы: для пустого dict ~64 байта, после добавления заметно растёт
d = {}
print(sys.getsizeof(d))         # ~64
for i in range(10):
    d[i] = i
print(sys.getsizeof(d))         # ~360


# Иллюстрация коллизий: одинаковый hash, но разные объекты
class Key:
    def __init__(self, value: int):
        self.value = value

    def __hash__(self) -> int:
        return 42  # все ключи в один bucket — open addressing справится, но медленно

    def __eq__(self, other) -> bool:
        return isinstance(other, Key) and self.value == other.value


data = {Key(i): i for i in range(5)}
print(data[Key(3)])  # 3 — но lookup делает много probe шагов

# Hash randomization для строк
# echo $PYTHONHASHSEED  # 0 = выключить, random = включить

Структура CPython dict

С Python 3.6 dict в CPython использует compact представление (PEP 468 + Raymond Hettinger):

• Плотный массив entries с записями (hash, key, value) в порядке вставки.
• Разреженный массив indices (по сути hash-таблица), который хранит индекс в entries. Размер индекса растёт по мере роста dict: int8 → int16 → int32 → int64.
• Таблица заполняется максимум на 2/3, иначе grow (×4 для малых dict, ×2 для больших).

Алгоритм lookup

1. Вычислить h = hash(key).
2. Взять slot h & (n - 1) в indices (n — размер, степень двойки).
3. Если слот пуст — KeyError.
4. Иначе достать индекс, в entries сравнить сначала hash, потом key is candidate or key == candidate (быстрая identity-проверка, потом дорогая __eq__).
5. При коллизии — open addressing с probing: perturb = h; i = (5 * i + 1 + perturb) & mask; perturb >>= 5. Это даёт хорошее распределение и использует старшие биты hash.

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

• Hash распределяет ключи равномерно по таблице → ожидаемое число коллизий низкое.
• Load factor < 2/3 удерживает среднюю длину пробы маленькой.
• Сравнение по identity (is) до __eq__ делает hit практически бесплатным для тех же объектов.

Worst case O(n) достижим, если злоумышленник подсунет ключи с одинаковым hash (hash flooding). Поэтому в CPython hash строк/байт randomized через PYTHONHASHSEED.

Контракт hashable

• Реализуй и __hash__, и __eq__ вместе.
• Если a == b, то hash(a) == hash(b). Иначе lookup не найдёт нужный ключ.
• Hash должен быть стабильным в течение жизни объекта — не зависеть от mutable полей.

Подводные камни

• Использовать mutable объект как ключ и менять hash-влияющие поля — ключ потеряется в таблице.
• Реализовать __eq__ без __hash__ — Python автоматически выставит __hash__ = None, объект станет unhashable.
• Hash, который всегда возвращает константу — все ключи в один bucket, lookup деградирует до O(n).
• Сериализовать dict в JSON и полагаться на порядок ключей при сравнении ответов — порядок есть, но равенство dict-ов от порядка не зависит.
• Считать, что resize «дорогой» — он амортизированно O(1) на вставку.

• Говорить, что dict ищет ключ перебором всех элементов.
• Не объяснять роль hash и eq.
• Игнорировать коллизии.

• Описывает hash-таблицу без лишней реализации CPython.
• Понимает средний и худший случай.
• Связывает dict с hashable.