Почему ключи словаря должны быть неизменяемыми?

Question

Словарь хранит элементы так, чтобы быстро находить их по ключу, используя хеш ключа. Если ключ можно менять, его хеш и сравнение могут измениться после добавления в словарь. Тогда элемент окажется “не там”, где словарь ожидает его найти, и поиск начнёт работать неправильно. Поэтому ключ должен быть неизменяемым и иметь стабильный __hash__ и корректный __eq__.

YeaHub · Accepted Answer

Словарь (dict) устроен как хеш-таблица: он вычисляет hash(key) и по нему выбирает место, где хранить значение.Определение: хеш (hash) — число, которое вычисляется из объекта и используется для быстрого распределения по “корзинам” внутри словаря.Как словарь использует ключПеред тем как положить пару key -> value, словарь делает следующее:Вычисляет h = hash(key).По h выбирает позицию (и при коллизиях — пробует следующие позиции).При необходимости сравнивает ключи через ==, чтобы отличать разные ключи с одинаковым хешем.Почему изменяемый ключ ломает поискЕсли ключ изменится после вставки, обычно меняется и его хеш/сравнение:словарь “помнит” старое размещение, связанное со старым hash(key);поиск по обновлённому ключу пойдёт по другому пути и не найдёт элемент, либо начнёт вести себя непредсказуемо.Мини-пример проблемы# Список изменяемый, поэтому не может быть ключом
d = {}
# d[[1, 2]] = "x"  # TypeError: unhashable type: 'list'
Что подходит в ключиНеизменяемые типы: int, str, tuple (если внутри тоже неизменяемое), frozenset.Пользовательские объекты: если они “ведут себя как неизменяемые” и у них корректно определены __hash__ и __eq__.ВыводКлючи должны быть неизменяемыми, потому что словарь опирается на стабильные hash и сравнение ключа для корректного и быстрого поиска.