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

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

Пример:

d = {'a': 1, 'b': 2}
print(d['a'])  # Быстрый доступ по хэшу

Нюансы:

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

Для больших словарей Python автоматически увеличивает размер таблицы, чтобы минимизировать коллизии.