Что происходит внутри dict при добавлении нового элемента

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

Знаете ли вы, как устроен dict в CPython, а не только что «там хеш-таблица». Интервьюер хочет услышать про открытую адресацию, порядок вставки и цену расширения. Следом часто спрашивают, почему ключ обязан быть хешируемым.

Как отвечать

С Python 3.6 словарь компактный и состоит из двух массивов:

• записи (entries): плотный массив пар ключ и значение (для нестроковых ключей рядом хранится и хеш) в порядке вставки. Отсюда сохранение порядка, в языке он гарантирован с 3.7;
• индексы: разреженная таблица размером в степень двойки, в ячейках номера записей. Ширина ячейки от 1 до 8 байт, поэтому пустые слоты дёшевы.

Вставка d[key] = value идёт так:

• хеш: вызывается hash(key), для list и других нехешируемых ключей сразу TypeError;
• слот: стартовый индекс равен hash & mask. При коллизии CPython перебирает ячейки по формуле с perturb, куда постепенно подмешиваются старшие биты хеша. Это открытая адресация, цепочек нет;
• сравнение: в занятой ячейке сначала проверяется идентичность ключа, затем равенство хешей и только потом __eq__. Ключ совпал, значит меняется значение, порядок остаётся прежним;
• запись: новая пара дописывается в конец entries, её номер кладётся в найденную ячейку;
• расширение: когда свободные записи кончились (это около 2/3 таблицы), выделяется таблица под used * 3, округлённая до степени двойки. Хеши не пересчитываются: они лежат в записях, а у строк закешированы в самом объекте. Заново раскладываются только индексы, удалённые записи выбрасываются.

Итог: O(1) в среднем с амортизацией, O(n) в худшем случае на плохих хешах.

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

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

Путают требования к ключу и значению. Изменяемым может быть значение, но не ключ, а кортеж хешируем, только если хешируемы все его элементы: (1, [2]) в роли ключа даст TypeError.

Меняют размер словаря внутри for k in d и получают RuntimeError: dictionary changed size during iteration. Обходить нужно копию, например list(d).