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