Как устроен и работает словарь (dict) в Python

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

Знаете ли вы, что это хеш-таблица с открытой адресацией, и понимаете ли, откуда взялся гарантированный порядок вставки.

Как отвечать

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

Коллизии разрешаются открытой адресацией: при занятой ячейке проба идёт дальше по псевдослучайной последовательности, зависящей от полных битов хеша. Цепочек, как в Java, здесь нет.

С версии 3.6 (официально с 3.7) словарь сохраняет порядок вставки. Это следствие компактной реализации: сами пары лежат в плотном массиве по порядку добавления, а хеш-таблица хранит лишь индексы в этот массив. Побочный эффект оказался и экономией памяти примерно на треть.

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

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

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

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

Считают, что порядок вставки это случайная деталь реализации, на которую нельзя полагаться: с 3.7 это часть языка.

Пытаются использовать список ключом.

Уверены, что словарь всегда даёт постоянное время, забывая про перестроение.

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