Как реализован dict в интерпретаторе Python

Словарь (ассоциативный массив / хэш-таблица / dict) — это такая замечательная структура данных в Python, которая поддерживает обращение, вставку и удаление в среднем за константное время O(1).

Возьмем в качестве примера словарь, который отображает реальное имя человека в его игровой никнейм.

nickname = {
  "Gena": "Машина",
  "Ivan": 12, 
  "Vazgen": "Gorniy Orel 228"
}

Визуально очень похоже на JSON. Ключами выступают "Gena", "Ivan", значениями "Машина", 12 и тд. Причем последние могут быть чем угодно: объектами, числами, строками, списками, словарями.

Ключи же должны быть хэшируемыми типами данных — такими, у которых определен метод __hash__. Обычно эти объекты являются неизменяемыми. Т.е. tuple может выступать в качестве ключа, а list — нет. Хотя в пользовательских классах можно наворотить все что угодно.

Что происходит на уровне интерпретатора CPython при добавлении нового ключа? Например, мы выполнили строчку nickname["Dima"] = "Арчибальд Шпицен-Дроссель".

На уровне C есть просто два массива фиксированной длины: dk_indices — хранит индексы и dk_entries — хранит пары ключ-значение, плюс несколько вспомогательных полей с размером самого словаря, типами данных и тд.

При вставке для объекта "Dima" вызывается функция PyObject_Hash, которая залезает в PyTypeObject — структуру с основными свойствами объекта (в Python все есть объект) и находит там хэш-функцию unicode_hash (строки из примера под капотом unicode). Применяя ее к "Dima", получает некоторое большое по модулю число. Кстати, сложность хэширования O(k), но мы предполагаем, что длина ключей в среднем сильно меньше размера словаря k << n.

Чтобы найти слот для hash("Dima") в dk_indices, берется остаток от деления на длину dk_indices. Если соответствующая ячейка в массиве пуста, то в dk_entries добавляется пара ("Dima", "Арчибальд Шпицен-Дроссель"). Если же ячейка занята, это означает что произошла коллизия. В простейшем случае можно было бы хранить в dk_entries не просто ключ-значение, а связный список из ключей и значений. Тогда при коллизиях мы бы просто делали append в конец списка.

Но в CPython используется алгоритм сдвига с пертурбацией. В случае коллизии он вычисляет новый индекс по формуле

    perturb >>= PERTURB_SHIFT;
    j = (5*j) + 1 + perturb;
    use j % 2**i as the next table index;

И повторяет процедуру до тех пор, пока не найдет свободную ячейку.

Такие дела. Все вышеперечисленное не претендует на истину в последней инстанции. Там еще есть PyDictKeyEntry vs PyDictUnicodeEntry, 6000 строк реализации dictobject.c и куча прочих нюансов. Но основная идея такая, если я нигде не наврал. А если наврал, пишите замечания в комментариях!