При каких условиях доступ к элементу в словаре осуществляется за линейное время?

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

Это происходит, если хеш-функция плохо распределяет ключи или если злоумышленник специально подбирает ключи с одинаковым хешем. В таких случаях поиск элемента сводится к последовательному перебору элементов в одной корзине.

Таким образом, доступ к элементу в словаре будет за линейное время при сильных коллизиях хешей и отсутствии эффективного разрешения коллизий.