Хеширование: как устроены dict и set

⏱ 35 мин · 🧩 заданий: 5

Хеш-функция

hash(obj) возвращает целое число — хеш. Требования:

Равные объекты имеют равные хеши: a == b ⇒ hash(a) == hash(b).
Хеш объекта не меняется, пока объект используется как ключ.
Желательно: разные объекты дают разные хеши (но коллизии допустимы).

print(hash(42), hash(42.0), hash(True), hash(1))   # 42 == 42.0, 1 == True → равные хеши
print(hash("abc"), hash((1, 2)))
print(hash(-1), hash(-2))                           # -1 зарезервирован в C-API: hash(-1) == -2
try:
    hash([1, 2])
except TypeError as e:
    print("TypeError:", e)

Хешируемы неизменяемые встроенные типы (и кортежи из хешируемых), а также экземпляры обычных классов (хеш по id). Изменяемые контейнеры не хешируются: если бы список изменился, лежа в словаре, его уже нельзя было бы найти.

Хеш-таблица

Словарь и множество — хеш-таблицы: массив ячеек, где позиция ключа вычисляется из его хеша.

ключ "cat" ──hash()──▶ 7429... ──% 8──▶ ячейка 5 ячейки: 0 1 2 3 4 5 6 7 [ ] [ "dog"] [ ] [ ] [ ] ["cat"] [ ] ["owl"]

Поиск ключа:

Вычислить hash(key).
По младшим битам хеша выбрать ячейку.
Если в ячейке объект с тем же хешем и == ключу — нашли.
Если ячейка занята другим ключом (коллизия) — пробовать следующую ячейку по формуле пробирования.
Пустая ячейка — ключа нет.

Поэтому поиск — O(1) в среднем: хеш вычисляется за постоянное время, а коллизий немного.

Простая модель

class TinyDict:
    """Хеш-таблица с открытой адресацией и линейным пробированием (учебная)."""
    def __init__(self, size=8):
        self.slots = [None] * size
        self.count = 0

    def _find(self, key):
        i = hash(key) % len(self.slots)
        while self.slots[i] is not None and self.slots[i][0] != key:
            i = (i + 1) % len(self.slots)         # коллизия → следующая ячейка
        return i

    def __setitem__(self, key, value):
        if (self.count + 1) * 3 > len(self.slots) * 2:   # заполнено больше чем на 2/3
            self._resize()
        i = self._find(key)
        if self.slots[i] is None:
            self.count += 1
        self.slots[i] = (key, value)

    def __getitem__(self, key):
        slot = self.slots[self._find(key)]
        if slot is None:
            raise KeyError(key)
        return slot[1]

    def _resize(self):
        old = [s for s in self.slots if s]
        self.slots = [None] * (len(self.slots) * 2)
        self.count = 0
        for k, v in old:
            self[k] = v

d = TinyDict()
for word in ["кот", "пёс", "ёж", "лиса", "волк", "сова"]:
    d[word] = len(word)
print(d["лиса"], len(d.slots), d.slots)

Нажмите 👣 Пошагово, чтобы увидеть, как заполняются ячейки и как таблица расширяется.

Как устроен настоящий dict

С Python 3.6 словарь компактный: две части.

indices: [ -, 1, -, -, 0, -, 2, - ] ← маленький массив индексов (хеш-таблица) entries: [ (hash, "a", 1), ← плотный массив записей в порядке вставки (hash, "b", 2), (hash, "c", 3) ]

Хеш-таблица хранит только индексы в массив записей — это экономит память.
Записи лежат в порядке вставки — поэтому dict сохраняет порядок (гарантия языка с 3.7).
Пробирование не линейное, а псевдослучайное с использованием старших битов хеша (perturb), чтобы плохие хеши не создавали длинных цепочек.
Таблица расширяется, когда заполнена примерно на 2/3; при расширении все ключи перераспределяются — поэтому отдельная вставка иногда O(n), но в среднем O(1).

set устроен похоже, но без массива значений.

Контракт eq и hash

class Money:
    def __init__(self, amount, currency):
        self.amount, self.currency = amount, currency

    def __eq__(self, other):
        if not isinstance(other, Money):
            return NotImplemented
        return (self.amount, self.currency) == (other.amount, other.currency)

    def __hash__(self):
        return hash((self.amount, self.currency))     # хеш от тех же полей, что и равенство

prices = {Money(100, "RUB"): "кофе"}
print(prices[Money(100, "RUB")])
print(len({Money(1, "USD"), Money(1, "USD")}))

Правила:

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

Изменяемый ключ

Если изменить поле объекта, от которого зависит хеш, пока объект лежит в словаре, его больше нельзя будет найти — ни по старому, ни по новому значению.

class Key:
    def __init__(self, v): self.v = v
    def __eq__(self, o): return self.v == o.v
    def __hash__(self): return hash(self.v)

k = Key(1)
d = {k: "значение"}
k.v = 2                       # мутировали ключ
print(Key(2) in d, Key(1) in d, len(d))   # потерян!

Коллизии и худший случай

Если у всех ключей одинаковый хеш, каждая операция превращается в перебор — O(n):

import time

class BadHash:
    def __init__(self, v): self.v = v
    def __eq__(self, o): return self.v == o.v
    def __hash__(self): return 42            # у всех одинаковый

class GoodHash(BadHash):
    def __hash__(self): return hash(self.v)

for cls in (GoodHash, BadHash):
    t = time.perf_counter()
    s = {cls(i) for i in range(1500)}
    print(f"{cls.__name__}: {time.perf_counter() - t:.4f} c")

Поэтому хеши строк рандомизированы при каждом запуске (PEP 456, SipHash): злоумышленник не может заранее подобрать тысячи строк с одинаковым хешем и «положить» сервер (атака HashDoS).

Итог

hash() — целое число; равные объекты обязаны иметь равные хеши.
dict и set — хеш-таблицы с открытой адресацией: O(1) в среднем, O(n) в худшем.
Современный dict компактный: массив индексов + массив записей в порядке вставки; расширяется при заполнении ~2/3.
__eq__ без __hash__ делает объект нехешируемым; хеш — от тех же неизменяемых полей.
Не меняйте ключи, лежащие в словаре; хеши строк рандомизированы против HashDoS.

Войдите, чтобы отмечать пройденные уроки.

	Да	Нет
`42`
`"text"`
`(1, "a")`
`(1, [2])`
`[1, 2]`
`frozenset({1})`
экземпляр обычного класса без `__eq__`