Как происходит сохранение ключа и значения в массиве при вставке в хэш-таблицу

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

Понимаете ли вы, что происходит между d[key] = value и записью в память: хэш, индекс, коллизия, расширение. Для Python-разработчика следом почти всегда идёт вопрос, как устроен именно dict и почему он хранит порядок вставки.

Как отвечать

Общая схема:

• хэш: hash(key) превращает ключ в целое число. Ключ обязан быть хэшируемым: list в ключ не пройдёт, tuple из неизменяемых пройдёт;
• индекс: хэш сводится к размеру таблицы. В CPython размер всегда степень двойки, поэтому вместо деления берутся младшие биты: hash & (size - 1);
• коллизия: если слот занят другим ключом, есть два подхода. Цепочки хранят в слоте список пар, открытая адресация ищет другой слот по правилу пробирования;
• сравнение: при совпадении слота сначала сравниваются хэши, потом идентичность is, и только потом __eq__. Отсюда правило: равные объекты обязаны иметь равный хэш;
• расширение: когда таблица заполнена примерно на две трети, CPython выделяет больший массив и перекладывает записи. Поэтому вставка в среднем O(1), а отдельная может стоить O(n).

В CPython с 3.6 dict состоит из двух массивов. Разреженный массив индексов и плотный массив записей с ключом и значением в порядке вставки; хэш не пересчитывается, он хранится в записи или закэширован в самом объекте строки. Слот первого массива хранит номер записи во втором. Коллизии решаются открытой адресацией, но не линейной: следующий слот зависит от старших битов хэша (переменная perturb), чтобы близкие хэши не слипались в кластеры. При удалении в индексе остаётся метка, иначе поиск оборвался бы на дыре. Порядок вставки гарантирован языком с 3.7.

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

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

Думают, что в слоте хранится только значение. Ключ лежит рядом, иначе коллизию нельзя было бы распознать.

Переопределяют __eq__ и удивляются TypeError: unhashable type: без явного __hash__ Python убирает хэш у класса. Хуже, когда хэш считают по изменяемому полю: после изменения объект в словаре не найти.