Как работает алгоритм словаря в Python, его скорость и требования к ключам
Что проверяют
Понимаете ли вы хэш-таблицу в реализации CPython, а не только формулу «O(1)». Следом спрашивают, почему список нельзя сделать ключом, а экземпляр своего класса можно, и что будет при коллизиях.
Как отвечать
Устройство в CPython:
- компактный словарь: с версии 3.6 это два массива, разреженный массив индексов и плотный массив записей (хэш, ключ, значение). Отсюда экономия памяти и порядок вставки, который с 3.7 гарантирован языком;
- открытая адресация: цепочек нет. При коллизии следующая ячейка ищется псевдослучайным пробированием, в формулу подмешиваются старшие биты хэша, чтобы близкие хэши расходились;
- поиск: считается
hash(key), находится ячейка, затем сравнение: сначала по идентичности, потом по совпадению хэша, и только потом__eq__; - удаление: в массиве индексов остаётся метка-заглушка, иначе оборвётся цепочка пробирования для других ключей;
- рост: когда таблица заполнена примерно на две трети, она перестраивается в большую, поэтому вставка стоит O(1) амортизированно.
Поиск, вставка и удаление стоят O(1) в среднем и O(n) в худшем случае, когда много ключей попадает в одни ячейки.
Требование к ключу не «неизменяемость», а хэшируемость: есть __hash__, равные объекты обязаны иметь равные хэши, и хэш не меняется, пока объект лежит в словаре. У списка __hash__ равен None. Экземпляр обычного класса хэшируется по id и ключом быть может. Кортеж хэшируем, только если хэшируемы все его элементы. Хэши строк рандомизируются при каждом запуске процесса (PYTHONHASHSEED), это защита от атак подбором коллизий.
Где спотыкаются
Говорят, что словарь хранит цепочки в корзинах. Это описание хэш-таблицы из учебника или из Java, в CPython открытая адресация.
Переопределяют __eq__ без __hash__. Python тогда выставляет __hash__ = None, и объект перестаёт быть ключом. Обратная ошибка: хэш считается от изменяемого поля, объект меняют, и ключ в словаре «теряется».
Не знают, что 1, 1.0 и True равны и имеют одинаковый хэш, поэтому в словаре это один ключ. Ещё одна частая ошибка: менять размер словаря во время итерации и получать RuntimeError.