Что происходит при вставке ключа и значения в dict в Python

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

Понимаете ли вы, что стоит за строчкой d[k] = v: хеш, таблица, коллизии, пересборка. Обычно вопрос ведут к тому, почему словарь быстрый, почему ключ обязан быть неизменяемым и откуда берётся порядок при переборе.

Как отвечать

По шагам:

• считается hash(k). Если у объекта нет __hash__, сразу TypeError: список и словарь ключами быть не могут, кортеж из неизменяемых может;
• младшие биты хеша дают позицию в разреженной таблице индексов. Если позиция занята, идёт проба следующей по правилу, которое подмешивает старшие биты хеша, а не просто берёт соседнюю ячейку;
• в занятой позиции ключи сравниваются сначала по хешу, потом по тождеству, потом по равенству. Совпало, значит это тот же ключ: меняется только значение, а объект ключа остаётся тот, что вставили первым;
• новый ключ дописывается в плотный массив записей в порядке вставки, а в таблицу индексов кладётся его номер. Отсюда и сохранение порядка перебора, и экономия памяти;
• когда заполненность переваливает за две трети, выделяется таблица побольше, записи уплотняются, индексы пересчитываются. Поэтому вставка это O(1) амортизированно, а отдельная вставка может оказаться дорогой.

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

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

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

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