Что такое хеш-таблица, как она устроена и почему поиск в ней O(1)?

Хеш-таблица — структура данных, хранящая пары ключ-значение. Индекс, по которому лежит значение, вычисляется из ключа хеш-функцией, поэтому доступ, вставка и удаление в среднем занимают O(1) (амортизированно), а не O(n) как при переборе. В Python хеш-таблица — это dict (и set под капотом).

Ещё вопросы по теме «Python»

• Что такое RVM?
• Назови главное отличие между 2-ой и 3-ей версией Python?
• Чем итератор отличается от генератора? Что такое протокол итератора и ленивость?
• Чем кортеж отличается от списка? Когда что использовать?
• Что такое декоратор, как он работает и зачем нужен?
• Что такое None и почему сравнивать с ним нужно через `is`, а не `==`?