dict и хешируемость

Потому что порядок в словаре появился как побочный эффект полезной оптимизации, а у множества такой оптимизации не было.

Компактная раскладка 3.6 разделила словарь на две части: плотный массив записей в порядке вставки и разреженный массив индексов в него. Это сделали ради памяти — экономия вышла 20–25%. Порядок вставки получился бесплатно: записи и так лежат подряд.

Множество устроено иначе — это по-прежнему одна разреженная таблица, где позиция определяется хешем. Плотного массива в порядке вставки там нет, и делать его незачем: экономии не будет, потому что нет значений.

print({"b": 1, "a": 2})           # → {'b': 1, 'a': 2}   порядок вставки 🔒
print({3, 1, 2})                  # → {1, 2, 3}          похоже на сортировку
print({"три", "один", "два"})     # → порядок зависит от хешей и соли

Маленькие целые выглядят «отсортированными» потому, что hash(n) == n и они ложатся по своим индексам. Это совпадение, а не свойство.

Главное в этой истории не порядок, а прецедент. В 3.6 это была деталь реализации 🔧 с прямым предупреждением в release notes; к 3.7 на неё оперлось столько кода, что её сделали гарантией 🔒. Реализация превратилась в спецификацию — ровно потому, что люди начали ею пользоваться. Тот же путь сейчас проходит детерминированное разрушение по счётчику ссылок, и вот его как раз не гарантируют.

Это защита от отказа в обслуживании, добавленная в 3.3 после публичной атаки.

Словарь деградирует до линейного поиска, если все ключи попадают в одну корзину. Зная функцию хеширования, злоумышленник может подобрать тысячи строк с одинаковым хешем и отправить их как поля формы или ключи JSON — и обработка запроса из миллисекунд превращается в секунды. Уязвимость затронула почти все языки разом.

Ответ: хеш строк и байтов солится случайным значением, своим на каждый запуск процесса.

$ python3 -c "print(hash('abc'))"
$ python3 -c "print(hash('abc'))"
# два разных числа

$ PYTHONHASHSEED=0 python3 -c "print(hash('abc'))"
$ PYTHONHASHSEED=0 python3 -c "print(hash('abc'))"
# одинаковые

Практические следствия. Хеш строки нельзя сохранять на диск, класть в кеш, использовать для шардирования между процессами или сравнивать между запусками — для этого есть hashlib, который стабилен по определению. И тест, проверяющий порядок обхода множества строк, будет зелёным ровно до следующего запуска 🕳.

PYTHONHASHSEED=0 отключает соль — иногда нужно для воспроизводимости отладки, но в проде это возвращает уязвимость.

Можно было бы — ровно один раз. Проблема во втором разе.

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

class Sneaky(list):
    __hash__ = lambda self: hash(tuple(self))   # «давайте всё-таки хешировать»

d = {Sneaky([i]): i for i in range(200)}
k = Sneaky([500])
d[k] = "значение"

k.append(1)                                     # ключ изменился на месте
print(d[k])
# → KeyError: [500, 1]        не находится даже по тому же объекту
print("значение" in d.values(), len(d))
# → True 201                  запись на месте и недостижима

Запись не потеряна и не повреждена — она просто больше никогда не найдётся. Ни исключения в момент поломки, ни способа это обнаружить. Это худший вид ошибки: тихая и отложенная.

На маленьком словаре тот же код может случайно сработать: индексный массив короткий, старый и новый хеш попадают в одну ячейку, и совпадение находится по идентичности. Это делает ошибку ещё хуже — она проявляется при росте данных.

Поэтому изменяемые встроенные типы принудительно объявлены нехешируемыми — __hash__ = None. Не потому, что вычислить хеш нельзя, а потому, что удержать контракт невозможно. Нужен ключ из последовательности — tuple; нужен ключ из множества — frozenset; нужен ключ из своего класса — реализуй __hash__ только по полям, которые не меняются.

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

Словарь в Python не структура данных из стандартной библиотеки, а несущая конструкция: неймспейс модуля, __dict__ инстанса, таблица методов класса, keyword-аргументы — всё это словари. Любое изменение задевает каждую программу, поэтому туда лезут осторожно и с замерами.

Раскладку 3.6 предложил Раймонд Хеттингер в 2012-м, и до релиза она вылёживалась четыре года. Идея: вместо одной разреженной таблицы записей — плотный массив записей плюс отдельный разреженный массив маленьких индексов. Разреженная часть теперь хранит не 24-байтовые записи, а индексы по 1, 2, 4 или 8 байт в зависимости от размера словаря.

import sys
d = {}
prev = -1
for i in range(40):
    if sys.getsizeof(d) != prev:
        prev = sys.getsizeof(d); print(len(d), prev)
    d[i] = i

Это не единственная оптимизация словаря, и остальные тоже пришли поздно: разделяемые ключи для инстансов одного класса (PEP 412, версия 3.3), перенос значений инстанса в преамбулу объекта (3.11), счётчик версий для инлайн-кешей LOAD_GLOBAL (3.11). Все они 🔧 и все меняли раскладку.

Вывод, полезный за пределами словаря: в зрелом языке базовые структуры продолжают переписывать десятилетиями, и любой тест, опирающийся на их байты, — мина замедленного действия.