Что такое словарь (dict) в Python, как он устроен и какие типы могут быть ключами

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

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

Как отвечать

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

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

Не годятся списки, словари и множества: они изменяемы, и хеш перестал бы соответствовать содержимому.

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

Важное про порядок: начиная с Python 3.7 словарь сохраняет порядок вставки, и это уже часть языка, а не деталь реализации. Заодно в 3.6 его сделали компактнее по памяти.

Полезно упомянуть, что требование к ключам то же, что к equals/hashCode в Java: равные объекты обязаны иметь равный хеш, иначе поиск сломается.

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

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

Не знают про сохранение порядка и по привычке называют словарь неупорядоченным.

Забывают, что при коллизии внутри ячейки ключи сравниваются через ==, поэтому объект с испорченным __eq__ ломает словарь так же, как испорченный __hash__.