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

Что проверяют

Понимаете ли вы, как устроен dict внутри, и знаете ли точное требование к ключу. Формулировка вопроса намеренно неточная: требование не в неизменяемости, а в хешируемости, и хороший кандидат это поправляет.

Как отвечать

dict это хеш-таблица. При вставке Python считает hash(key) и по нему выбирает ячейку, а при поиске повторяет вычисление. Отсюда инвариант: пока объект лежит в словаре ключом, его хеш обязан оставаться прежним, а равные объекты обязаны иметь равный хеш.

Изменяемый объект этот инвариант ломает. Если бы список можно было положить ключом и потом дописать в него элемент, хеш изменился бы, ячейка стала бы не той, и значение перестало бы находиться. Поэтому у list, dict и set метода __hash__ просто нет:

d = {[1, 2]: "x"}   # TypeError: unhashable type: 'list'
d = {(1, 2): "x"}   # кортеж работает

Ключами могут быть числа, строки, кортежи, frozenset, а также экземпляры пользовательских классов: по умолчанию они хешируются по идентичности объекта. Важная тонкость: кортеж хешируем только если хешируемо всё его содержимое, поэтому (1, [2]) ключом не станет.

Формально «изменяемый ключ» возможен: если в своём классе определить __hash__ и потом менять поля, которые в нём участвуют, интерпретатор не помешает. Результат предсказуемый: объект «теряется» в словаре, in возвращает False, при этом сам объект в памяти есть. Отсюда правило: если класс мутабельный, либо не делайте его ключом, либо считайте хеш по неизменяемой части.

Где спотыкаются

Говорят «ключ должен быть неизменяемым» и не могут объяснить, почему тогда работает объект пользовательского класса.

Забывают связку __eq__ и __hash__: переопределили равенство, а хеш нет, и два равных объекта лежат в словаре как разные ключи.

Не знают про frozenset, когда нужен ключ из набора значений.