Почему dict в Python обычно работает за O(1)
Объясните, как устроен hash table в Python dict и почему операции lookup/insert обычно O(1), но иногда деградируют.
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
dict использует hash ключа для адресации ячейки; амортизированно lookup/insert O(1), но коллизии и resize дают худшие случаи.
Полный разбор
Python dict - hash table. Для ключа считается hash, по нему выбирается позиция в массиве. Если ячейка занята другим ключом, используется probing. При нормальной load factor среднее число probes мало, поэтому lookup/insert/delete амортизированно O(1).
Деградация возможна при большом числе коллизий или специально подобранных ключах, хотя Python защищается randomized hashing для строк. Resize тоже стоит O(n), но происходит редко, поэтому в амортизированной оценке insert остается O(1).
Важно помнить: ключ должен быть hashable и equality-compatible с hash. Изменяемые объекты как list не могут быть ключом, потому что их hash был бы нестабилен.
Типичные ошибки
- Говорить, что dict всегда строго O(1).
- Забывать про hashable keys.
- Не отличать average и worst case.
Как отвечать на собеседовании
- Скажи amortized average O(1).
- Упомяни collisions, probing и resize.