Словарь настоящего языка: что внутри Python dict

Если ты понимаешь, что dict/set - это хеш-таблица со всеми приёмами раздела, почему ключи обязаны быть неизменяемыми и почему hash строки меняется между запусками, листай до «Теперь сам».

Как думаешь, что стоит за строкой d[key]

Ты пишешь d["Иванов"] = 100 и d["Иванов"] - и получаешь значение мгновенно. За этой простой записью работает вся машинерия раздела: строка «Иванов» прогоняется через хеш-функцию (с секретной солью), получается номер ячейки, при коллизии срабатывает пробирование, а когда таблица заполняется - незаметно происходит рехеширование. Понимать, что там внутри, полезно не из любопытства: это объясняет правила, которые иначе выглядят произвольными (почему ключом нельзя сделать список? почему hash("a") разный в разных запусках?), и пределы (почему dict иногда «дёргается», почему он не гарантирует скорость в худшем случае). Разберём, из чего собран настоящий словарь.

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

Автомобиль, на котором ты давно ездишь, не заглядывая под капот. Он просто едет. Но когда знаешь, что внутри двигатель, коробка, тормоза, ты понимаешь правила эксплуатации: почему нельзя лить не то топливо, почему на холодную надо прогреть, что означает лампочка на панели. dict - такой же «автомобиль»: ездит сам, но под капотом - хеш-функция, пробирование, рехеширование. Знание устройства превращает загадочные правила («ключ должен быть неизменяемым») в понятные следствия конструкции, а не в магические запреты.

Механизм: что собрано внутри dict

Настоящий словарь - это все приёмы раздела вместе:

d[key] = value  выполняет:
    1. h = hash(key)              # хеш-функция (для строк - со случайной СОЛЬЮ)
    2. i = h mod m               # номер ячейки в таблице размера m
    3. если ячейка занята другим ключом → ПРОБИРОВАНИЕ (открытая адресация в Python)
    4. положить (key, value); если α превысил порог → РЕХЕШИРОВАНИЕ (m растёт)

d[key]  (чтение):
    1. h = hash(key); i = h mod m
    2. идти по пробам, СРАВНИВАЯ сам ключ (не только хеш), пока не найдём или пусто

Важные детали настоящих реализаций:

• Ключи - только НЕИЗМЕНЯЕМЫЕ (в Python: число, строка, кортеж; НЕ список и не словарь). Причина ниже.
• Соль для строк. hash("строка") использует случайное семя, выбранное при старте процесса (PYTHONHASHSEED), - идея универсального хеширования против HashDoS: функцию выбирают случайно, и атакующий её не знает (сама SipHash - ключевая функция, а не семейство с доказанным Pr ≤ 1/m). Поэтому hash("a") разный в разных запусках.
• Порядок вставки. С Python 3.7 dict СОХРАНЯЕТ порядок добавления ключей (гарантия языка) - за счёт отдельного массива записей; но это свойство реализации, не самой хеш- таблицы (множество set порядок не хранит).

Правило

Словарь настоящего языка (dict, HashMap, unordered_map) - это хеш-таблица со всеми приёмами раздела: хеш-функция (для строк со случайной СОЛЬЮ - защита от HashDoS), разрешение коллизий (Python - открытая адресация ради локальности), контроль α и рехеширование. Ключи обязаны быть НЕИЗМЕНЯЕМЫМИ, потому что номер ячейки вычисляется по содержимому ключа: поменяешь ключ после вставки - его хеш «уедет», и он потеряется. dict даёт O(1) в среднем, не в худшем случае. Знание устройства объясняет правила словаря и его пределы.

Разбор: почему ключ обязан быть неизменяемым

Самое частое «почему нельзя» - и оно прямо следует из механизма. Место ключа в таблице определяется его ХЕШЕМ, а хеш считается по СОДЕРЖИМОМУ. Положили ключ [1, 2] (будь список разрешён) в ячейку hash([1,2]) mod m. Потом изменили список на [1, 2, 3] - его хеш стал другим, значит и «правильная» ячейка другая. Но физически ключ лежит в СТАРОЙ ячейке (мы его не перекладывали). Ищем [1, 2, 3]: считаем НОВЫЙ хеш, идём в НОВУЮ ячейку - а там пусто, ключ «потерялся», хотя он в таблице. Чтобы этого не случилось, языки запрещают изменяемые ключи: список, множество, словарь ключами быть не могут, а число, строка, кортеж (неизменяемые) - могут. Правило «ключ неизменяем» - не каприз, а защита от рассогласования «где лежит» и «где ищем».

Разбор: почему hash строки разный в разных запусках - это защита

Новичка удивляет: запустил программу - hash("abc") одно, перезапустил - другое. Кажется багом (где детерминизм?). На деле это идея универсального хеширования из прошлой главы в действии: при старте процесса Python выбирает случайное СЕМЯ (соль) и подмешивает его в хеш строк. Внутри ОДНОГО запуска хеш детерминирован (одна строка - один номер, словарь работает), но между запусками семя меняется - и злоумышленник не может заранее подобрать строки, сталкивающиеся в твоём словаре (защита от HashDoS, которой веб-серверы клали до 2012 года). Практический вывод: НЕЛЬЗЯ закладываться на конкретные значения hash() или на порядок обхода set между запусками и версиями - это не стабильный контракт, а намеренно рандомизированная величина. Хочешь воспроизводимый хеш (например, для контрольных сумм) - бери явные функции (hashlib), а не встроенный hash().

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

Первая ошибка - пытаться сделать ключом изменяемый объект (список): язык не даст (unhashable type), а если сделать через костыль - ключ потеряется при изменении. Второе - закладываться на конкретные значения hash() или порядок set между запусками: они рандомизированы солью, код сломается непредсказуемо. Третье - считать dict гарантированной константой в худшем случае и ставить его в путь с жёсткими требованиями к задержке: рехеширование даёт редкие O(n)-всплески, а при плохой хеш-функции пользовательских объектов (кривой __hash__) поиск может деградировать. Четвёртое - определить у своего класса __eq__, забыв __hash__ (или наоборот): равные объекты должны иметь равный хеш, иначе словарь их «не узнает».

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

Понимание устройства dict - это грамотная его эксплуатация. Оно объясняет: почему ключом может быть кортеж, но не список (неизменяемость); почему hash() и порядок set пляшут между запусками (соль); почему свой класс, используемый как ключ, должен согласованно определять __hash__ и __eq__ (равные - с равным хешем, иначе не найдётся); почему словарь иногда «дёргается» (рехеширование) и не годится в жёсткий realtime-путь. Всё это - прямые следствия приёмов раздела, собранных вместе. Инженер, знающий, что d[key] - это «хеш с солью → ячейка → пробы → сравнение ключа», не пишет багов вроде изменяемых ключей и не удивляется рандомизированным хешам, а понимает dict как машину, а не как магию.

Теперь сам

Почему в Python кортеж (1, 2) можно сделать ключом словаря, а список [1, 2] - нельзя, хотя они «про одно и то же»?