Почему поиск по ключам в словаре осуществляется быстро?

Поиск по ключам в словаре Python (или dict) осуществляется быстро благодаря его реализации на основе хэш-таблицы.

При добавлении пары ключ-значение:

1. От ключа высчитывается хэш (целочисленное значение) с помощью встроенной функции hash().
2. Хэш используется для определения индекса (бакета) в массиве, где будет храниться пара.
3. Если в бакете уже есть элементы (коллизия), используется специальный алгоритм для поиска свободного или разрешения конфликта (например, открытая адресация или связные списки, хотя в CPython используется оптимизированная форма открытой адресации).

При поиске значения по ключу:

1. От заданного ключа также высчитывается хэш.
2. Хэш указывает на потенциальный бакет в массиве.
3. Система проверяет элементы в этом бакете. Поскольку хэши могут совпадать для разных ключей (коллизии), дополнительно сравнивается сам ключ (использу