set: хеш, равенство и десять ячеек подряд

Если ты знаешь договор hash и ==, почему {1, 1.0, True} - один элемент, что делает NaN в множестве и зачем set проверяет десять ячеек подряд, листай до «Теперь сам».

Как думаешь, сколько элементов

{1, 1.0, True}

Три разных объекта трёх разных типов: целое, дробное, логическое. Сколько элементов в этом множестве? И второй вопрос: nan = float("nan"), известно, что nan == nan ложно. Что вернёт nan in [nan]?

Ответь себе до чтения. Первый ответ - один элемент, второй - True. Оба следуют из того, в каком порядке множество и список сравнивают элементы.

На что это похоже

Охранник у входа сверяет гостей со списком. Сначала он смотрит на браслет - цвет и номер (хеш): если номер не тот, дальше говорить не о чем, это быстро. Если номер совпал, он смотрит, не тот ли это человек, что уже проходил (тот же объект). И только если сомневается - просит паспорт и сверяет его целиком (==), это долго.

Система работает, пока у одинаковых по паспорту людей одинаковые браслеты. Выдай двум одинаковым по паспорту разные номера - охранник пропустит обоих как разных людей.

Механизм: ячейка «хеш + ключ» и линейные пробы

Ячейка таблицы set - два слова: хеш и ссылка на ключ, 16 байт. Первые 8 ячеек лежат прямо внутри объекта множества; когда их мало, таблица выносится отдельно. Порядок вставки не хранится - поэтому нет и массива записей, как у dict.

Поиск ключа с хешем h (set_lookkey в Objects/setobject.c):

i = h & маска
повторять:
    проверить ячейку i и до 9 следующих (если таблица не кончилась):
        пустая ячейка - ключа нет
        хеш совпал и (тот же объект или ==) - нашли
    perturb >>= 5;  i = (5·i + 1 + perturb) & маска

Порядок проверок в ячейке - главное: сравнение == вызывается, только если совпал сохранённый хеш, а перед ним проверяется тождество объекта. Хеш неотрицательного целого - остаток от деления на 2⁶¹ − 1, отрицательного - такой же остаток модуля со знаком минус, (ячейку из хеша выбирает уже таблица - младшими битами по маске), и единственное исключение - -1: в CPython оно занято под сигнал ошибки, поэтому hash(-1) == -2. Числа, равные между собой, хешируются одинаково независимо от типа: hash(1) == hash(1.0) == hash(True).

Перестройка: когда занятых ячеек (вместе с пустышками удалённых) становится 60% таблицы, новый размер - степень двойки больше 4 · элементов (на больших множествах 2 ·). Получается ряд 8, 32, 128, 512.

Правило

Договор: a == b ⇒ hash(a) == hash(b), и хеш не меняется, пока объект лежит в множестве или словаре. Поиск в set сравнивает хеш, потом тождество, потом ==. При коллизии - до десяти ячеек подряд, потом прыжок 5·i + 1 + perturb. Заполнение не больше 60%, рост вчетверо (на больших множествах - вдвое).

Разбор: что множество считает одинаковым

Проверим на Python 3.12 всё из крючка:

print({1, 1.0, True})
print(hash(1), hash(1.0), hash(True))
print(hash(-1), hash(-2))
print(hash(2 ** 61 - 1), hash(2 ** 61), hash(2 ** 61 + 5))
nan = float("nan")
print(nan == nan, nan in [nan], {nan, nan} == {nan},
      len({float("nan"), float("nan")}))

{1}
1 1 1
-2 -2
0 1 6
False True True 2

1, 1.0 и True равны между собой и хешируются одинаково - в множестве остаётся первый пришедший, 1. -1 и -2 сталкиваются всегда - это не ломает ничего, просто коллизия. Хеш берётся по модулю 2⁶¹ − 1, поэтому 2⁶¹ − 1 хешируется в 0.

С nan работает тождество: nan == nan ложно, но список и множество сначала спрашивают «тот же ли это объект» - и находят. Два разных объекта nan для множества различны: у NaN в Python 3.10+ хеш зависит от адреса объекта. Граница правила «множество убирает дубликаты»: NaN из разных вычислений не схлопнутся.

Разбор: зачем десять ячеек подряд

dict при коллизии сразу прыгает, set сначала смотрит соседние ячейки. Сравним на модели: таблица на 1024 ячейки, заполнение 59%, ищем 400 отсутствующих ключей (самый частый вопрос к множеству - «есть ли»). Считаем проверенные ячейки и строки кеша по 64 байта - в строку входят 4 ячейки по 16 байт.

import random

def iskat(tablica, h, linejno):
    # tablica[i] - ключ или -1; ищем ОТСУТСТВУЮЩИЙ ключ с хешем h
    maska = len(tablica) - 1
    i = h & maska
    perturb = h
    proby = []
    while True:
        dlina = 0
        if linejno and i + 9 <= maska:
            dlina = 9                # ячейка i и ещё 9 соседних
        for j in range(dlina + 1):
            proby.append(i + j)
            if tablica[i + j] == -1:
                return proby
        perturb = perturb >> 5
        i = (5 * i + 1 + perturb) & maska

for linejno in [False, True]:
    random.seed(7)                   # одни и те же ключи для обоих
    tablica = [-1] * 1024
    for n in range(600):             # заполнение 59%
        k = random.randint(0, 10 ** 6)
        proby = iskat(tablica, k, linejno)
        tablica[proby[-1]] = k
    yacheek = 0
    strok = 0
    for z in range(400):
        h = random.randint(10 ** 6, 2 * 10 ** 6)
        proby = iskat(tablica, h, linejno)
        yacheek = yacheek + len(proby)
        raznye = []
        for p in proby:
            if p // 4 not in raznye:  # 4 записи по 16 байт в строке кеша
                raznye.append(p // 4)
        strok = strok + len(raznye)
    imya = "прыжками"
    if linejno:
        imya = "линейно"
    print(imya, "- ячеек на поиск", yacheek / 400,
          "строк кеша", strok / 400)

прыжками - ячеек на поиск 2.55 строк кеша 2.525
линейно - ячеек на поиск 2.975 строк кеша 1.55

Линейные пробы проверяют БОЛЬШЕ ячеек - 2,98 против 2,55: соседние ячейки занятой таблицы чаще заняты, занятые лежат кучками. Но строк кеша они трогают меньше - 1,55 против 2,5, а каждая новая строка - возможный промах, и на настоящей машине промах кеша стоит десятки сравнений. Это граница правила «меньше проб - быстрее»: считать надо то, что дорого. После десяти соседей set всё равно прыгает, иначе кучки росли бы без предела.

Ряд размеров таблицы на настоящем Python:

import sys

s = set()
razmer = sys.getsizeof(s)
print("пустое множество:", razmer, "байт")
for i in range(200):
    s.add(i)
    if sys.getsizeof(s) != razmer:
        razmer = sys.getsizeof(s)
        mest = (razmer - 216) // 16
        print("элементов", len(s), "- байт", razmer,
              "ячеек в таблице", mest)

пустое множество: 216 байт
элементов 5 - байт 728 ячеек в таблице 32
элементов 19 - байт 2264 ячеек в таблице 128
элементов 77 - байт 8408 ячеек в таблице 512

Пустое множество - 216 байт, его восемь ячеек лежат внутри объекта; когда таблица выносится отдельно, (размер − 216) / 16 - число её ячеек. Пятый элемент в таблице на 8: 5 · 5 ≥ 7 · 3, порог 60% пройден, новая таблица - больше 4 · 5 = 20, то есть 32. Девятнадцатый в 32: 19 · 5 ≥ 31 · 3, новая больше 76 - 128.

Что ломается без этого

Три способа нарушить договор и что из этого выходит:

class Tochka:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __eq__(self, drugaya):
        return (self.x, self.y) == (drugaya.x, drugaya.y)


try:
    print({Tochka(1, 2)})
except TypeError as e:
    print("TypeError:", e)


class Tochka2(Tochka):
    def __hash__(self):
        return id(self)          # хеш не согласован с __eq__


print(len({Tochka2(1, 2), Tochka2(1, 2)}))


class Tochka3(Tochka):
    def __hash__(self):
        return hash((self.x, self.y))


p = Tochka3(1, 2)
s = {p}
print(Tochka3(1, 2) in s)
p.x = 5                      # ключ изменён после вставки
print(p in s, Tochka3(1, 2) in s, Tochka3(5, 2) in s)

TypeError: unhashable type: 'Tochka'
2
True
False False False

Определил __eq__ без __hash__ - Python сам отключает хеш, объект в множество не положить. Хеш по адресу при равенстве по полям - две равные точки в множестве. Хеш по изменяемым полям - точка лежит в множестве, но её не находит ни она сама, ни равная ей старая, ни равная новая: поиск идёт не в ту ячейку.

Зачем это в работе

Дедупликация записей через set или ключи dict молча зависит от договора: @dataclass(eq=True) без frozen=True тоже отключает хеш, а frozen=True его включает (если все поля сами хешируются; поле-список даст TypeError) - и это главный довод за неизменяемые записи. Числа, равные по значению, но разных типов (1 и 1.0 из разных источников), схлопываются - иногда это сюрприз в отчёте. NaN в колонке данных не схлопываются, и «уникальных значений» оказывается больше, чем строк без пропусков. А проверка x in множество в цикле вместо x in список - самая дешёвая оптимизация в жизни: O(1) в среднем вместо O(n).

Теперь сам

1. Сколько элементов в {0, 0.0, False, -0.0}?
2. Множество на 32 ячейки, в нём 18 элементов и 0 удалённых. Будет ли перестройка при добавлении девятнадцатого, и какой станет таблица?
3. Почему линейные пробы проверяют больше ячеек, чем прыжки, и всё равно выгодны?