Как устроен словарь в Python и почему ключом не может быть список?
Проверила команда Сопровод · Обновлено
Короткий ответ
Словарь — хеш-таблица. По hash(key) Python выбирает ячейку, а совпадение подтверждает через хеш и ==. Поэтому ключ обязан быть хешируемым, и его хеш не должен меняться, пока ключ лежит в словаре. У изменяемого list нет __hash__, и вставка падает с TypeError. Поиск, вставка и удаление в среднем занимают O(1).
Почему этот вопрос задают
Словарь встречается почти в каждом модуле на Python. По ответу видно, знаете ли вы цену операций, правила для ключей и что случится с записью, у ключа которой поменялся хеш.
Как рассуждать
- Назовите структуру: словарь — хеш-таблица с поиском за O(1) в среднем
- Опишите поиск: хеш выбирает ячейку, при совпадении хешей ключи сравниваются через
== - Выведите требование к ключу: хеш постоянный, у равных ключей равные хеши
- Объясните, почему список не подходит, и назовите замену: кортеж или
frozenset
Ответ с примером
Мобильный оператор хранит цены тарифов по паре «регион, тариф». Кортеж из двух строк хешируется, поэтому подходит в ключ. Поиск по новому кортежу с теми же значениями находит цену: у равных кортежей равные хеши, и словарь приходит в ту же ячейку.
Список в роли ключа падает с TypeError сразу при вставке. Представьте, что словарь его принял, а потом в список добавили элемент: хеш стал бы другим, и запись осталась бы в ячейке, куда поиск больше не заглядывает. Кортеж со списком внутри тоже отклоняется, потому что хеш кортежа считается по всем элементам. Последняя строка показывает порядок ключей: словарь отдает их в порядке вставки, это правило языка с версии 3.7.
tariffs = {("Москва", "Базовый"): 450, ("Казань", "Базовый"): 390}
print(tariffs[("Казань", "Базовый")])
for bad_key in (["Москва", "Безлимит"], ("Москва", ["Безлимит"])):
try:
tariffs[bad_key] = 790
except TypeError as e:
print(type(e).__name__, type(bad_key).__name__)
tariffs[("Сочи", "Базовый")] = 420
print(list(tariffs))390
TypeError list
TypeError tuple
[('Москва', 'Базовый'), ('Казань', 'Базовый'), ('Сочи', 'Базовый')]Как ответить сильнее
Что добавит опытный кандидат
Что спросят следом
Доступно по подписке
Приемы опытных и готовые ответы
Частые ошибки
«Ключом может быть только неизменяемый объект»
Уточните, что нужен хешируемый объект с постоянным хешем. Экземпляр обычного класса изменяемый, но хешируется по
idи годится в ключ«Порядок ключей в словаре никак не гарантирован»
Скажите, что с Python 3.7 словарь хранит порядок вставки по правилам языка. Без гарантии порядка живет
set«Поиск в словаре всегда занимает O(1)»
Говорите «в среднем O(1)»: при массовых коллизиях поиск деградирует до O(n). Хеш своего класса считайте по тем же полям, что участвуют в
__eq__«Список можно превратить в строку и взять ее ключом»
Возьмите
tuple(items): кортеж сохраняет элементы и их типы. Строка из"".join(map(str, items))склеит[1, 23]и[12, 3]в один ключ"123"
Сигналы для интервьюера
Сильный ответ
Рассказывает путь поиска ключа от hash до сравнения через == и сам выводит из него правила для ключей
Тревожный сигнал
Перечисляет правила для ключей, а на вопрос, что словарь делает при заполнении таблицы, отвечает общими словами
Красный флаг
Считает, что словарь ищет ключ перебором всех записей, и не может назвать сложность поиска
Как еще могут спросить
- Как работает словарь в Python под капотом?
- Какие объекты могут быть ключами словаря в Python?
- Почему список нельзя использовать как ключ словаря?
- Какая сложность у поиска по ключу в словаре Python?











