dict реализован как хэш-таблица с оптимизацией памяти и быстрого доступа. Ключ хешируется, из хеша выбирается слот, а коллизии разрешаются с помощью внутреннего алгоритма зондирования.
Практические последствия:
- среднее время доступа близко к
O(1);
- качество
__hash__ и __eq__ влияет на поведение;
- Изменяемые объекты не могут использоваться в качестве ключей.
Суммируя:
dict — это высокопроизводительная структура на основе хеша.- Его скорость зависит от хеширования.
- Ключи должны быть хешируемыми и стабильными.
Итог
dict реализован как хэш-таблица с оптимизацией памяти и быстрого доступа.
