Что такое хэшмап

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

Знаете ли вы, что за dict стоит конкретная структура с конкретной ценой, а не магия. Спрашивают на любом уровне, и по ответу видно, читали ли вы что-то про амортизацию и худший случай или запомнили только формулу про доступ за O(1).

Как отвечать

Хэш-таблица это массив ячеек плюс хэш-функция, которая переводит ключ в индекс. Вставка, поиск и удаление по ключу в среднем за O(1), в худшем случае, когда все ключи попали в одну позицию, за O(n).

Про Python отвечайте предметно. Встроенный dict разрешает коллизии открытой адресацией, а не связанными списками: реализация ищет следующую позицию по правилу, которое подмешивает старшие биты хэша. Когда заполненность переваливает примерно за две трети, таблица растёт и все ключи перераскладываются, поэтому отдельная вставка иногда стоит дорого, а средняя цена остаётся константной.

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

Ключом кладётся только хэшируемый объект, а обращение к отсутствующему ключу это KeyError. Мягкие формы дают get, setdefault и defaultdict.

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

Отвечают, что всегда O(1), и не могут назвать худший случай. Именно на нём строилась атака на веб-приложения подобранными ключами, из-за которой хэш строк и солится.

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

Меняют словарь во время итерации по нему, ловят RuntimeError и объясняют это случайностью. Перебор идёт по внутреннему массиву, а вставка может вызвать его пересборку, поэтому удалять безопасно только по копии ключей.