Как устроен словарь в Python и почему ключом не может быть список?

ЗнаниеMiddleЧасто

Проверила команда СопроводОбновлено

Короткий ответ

Словарь — хеш-таблица. По hash(key) Python выбирает ячейку, а совпадение подтверждает через хеш и ==. Поэтому ключ обязан быть хешируемым, и его хеш не должен меняться, пока ключ лежит в словаре. У изменяемого list нет __hash__, и вставка падает с TypeError. Поиск, вставка и удаление в среднем занимают O(1).

Почему этот вопрос задают

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

Как рассуждать

  1. Назовите структуру: словарь — хеш-таблица с поиском за O(1) в среднем
  2. Опишите поиск: хеш выбирает ячейку, при совпадении хешей ключи сравниваются через ==
  3. Выведите требование к ключу: хеш постоянный, у равных ключей равные хеши
  4. Объясните, почему список не подходит, и назовите замену: кортеж или frozenset

Ответ с примером

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

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

Python
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?

Похожие вопросы

ЗнаниеJuniorЧасто

Чем список отличается от кортежа в Python и когда выбрать кортеж?

Список (list) изменяемый: в него добавляют элементы, удаляют их и заменяют. Кортеж (tuple) после создания не меняется, поэтому из хешируемых значений он годится в ключи словаря и элементы множества. Кортеж выбирайте для записи с фиксированными полями, например координат или пары «дата, склад». Список берите для коллекции, которая растет и меняется.

  • Python
  • типы данных
231
ЗнаниеJuniorЧасто

Чем оператор is отличается от == в Python?

== сравнивает значения: вызывает __eq__ и отвечает, равны ли объекты по содержимому. is проверяет, что слева и справа один и тот же объект, и переопределить его нельзя. Для данных берите ==. is оставьте для одиночек: None, True, False и своих объектов-маркеров. Совпадение is у малых чисел и коротких строк — деталь CPython, на нее не опирайтесь.

  • Python
  • операторы
213
ЗадачаMiddleЧасто

Напишите класс денежной суммы, который можно складывать, сравнивать и использовать как ключ словаря

Сделайте класс неизменяемым и храните сумму целым числом копеек вместе с кодом валюты: @dataclass(frozen=True) сам создаст __eq__ и согласованный с ним __hash__. Сложение напишите в __add__: для чужого типа верните NotImplemented, для разных валют бросьте ValueError. Если пишете __eq__ руками, добавьте __hash__ по тем же полям, иначе объект нельзя положить в множество.

  • Python
  • ООП
  • магические методы
222
ЗадачаSeniorИногда

Реализуйте LRU-кэш на N элементов, в котором get и put работают за O(1)

Храните данные в OrderedDict: он помнит порядок ключей и переносит ключ в конец за O(1). В get при попадании вызывайте move_to_end(key), чтобы ключ стал самым свежим. В put записывайте значение, переносите ключ в конец и, если элементов стало больше N, удаляйте самый давний через popitem(last=False). Без OrderedDict то же дают словарь и двусвязный список.

  • Python
  • структуры данных
  • кэш
183

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

Хватит схемы: хеш выбирает ячейку, при коллизии идет поиск следующей, ключ подтверждается через ==, при заполнении таблица растет. Назовите сложность в среднем и в худшем случае. Формулу проб и коэффициент заполнения спросят, если вы сами их упомянете.

Напишите класс с __eq__ и __hash__, положите объект в словарь, поменяйте поле и попробуйте найти запись. Проверьте, что словарь {1: "a", 1.0: "b"} оставит один ключ. Каждый результат объясните вслух через хеш и сравнение.

Вспомните кэш, индекс по идентификатору или группировку через defaultdict. Расскажите, что было ключом, почему выбрали такой тип и как убедились, что ключ не меняется после вставки. Закончите тем, что сломалось бы с изменяемым ключом: вставка упала бы или запись потерялась.

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

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

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

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

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

Расскажите, какие задачи хотите решать через несколько лет и чему для этого научитесь. Свяжите план с тем, что дает эта компания, и покажите первый шаг, который уже сделали. Точную должность называть не обязательно. Важнее, чтобы план был реальным и вел через эту работу, а не мимо нее.

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

Расскажите один реальный конфликт по рабочему вопросу: из-за чего разошлись, чего хотела каждая сторона и как вы договорились. Говорите спокойно, без оценок коллеги. Покажите, что вы искали решение, где-то уступили и сохранили рабочие отношения. Закончите результатом и тем, что теперь делаете, чтобы похожий спор не повторился.

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

Назовите одно достижение, близкое к задачам новой работы, и расскажите его как историю: какая была проблема, что сделали лично вы и что изменилось в цифрах. Сильнее всего звучит результат, который держится и после вас: новый порядок работы, правило, схема. Если результат общий, прямо скажите, какая часть в нем ваша.

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

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

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

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

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

Возьмите одного человека и покажите путь: каким он пришел, какие задачи вы ему давали по нарастающей и чем помогали, кем он стал и за какой срок. Назовите цифру роста: новая должность, своя зона, люди в подчинении. Скажите честно, где он вырос сам, а где сработали ваши решения.

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

Назовите цель с цифрой и честный итог. Главное в ответе — момент, когда вы поняли, что цель срывается, и по какой цифре это увидели. Дальше расскажите, кому и когда сказали, что пересобрали, чтобы спасти главное, и какой один вывод сделали для следующего плана.

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

Назовите два-три показателя, которые отражают то, ради чего существует ваша команда, и их текущие цифры. Добавьте показатель качества, который не дает гнаться за одним числом. Скажите, как часто смотрите на цифры, кто их видит и какое решение вы приняли по ним в последний раз.

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

Возьмите одну цель компании с цифрой и сроком и покажите, как вы ее разбили: на какие части, по какому признаку, какие личные цели получил каждый сотрудник. Расскажите, как следили за ходом и что меняли по дороге. Закончите итогом план-факт честно, даже если цель выполнена не целиком.

  • цели
  • планирование
227