Что такое хеш-таблица и почему словарь в Python такой быстрый?
Слышал, что словарь (dict) внутри — это хеш-таблица и поэтому поиск по ключу «мгновенный». Как это работает? Почему найти значение по ключу быстрее, чем искать элемент в списке?
3 ответа
Идея такая: когда ты кладёшь ключ в словарь, от ключа считается хеш — число. Это число говорит, в какую «ячейку» памяти положить значение. Когда ищешь по ключу — снова считаешь хеш и сразу прыгаешь в нужную ячейку, не перебирая остальные. Поэтому поиск в среднем O(1) — не зависит от размера словаря.
В списке, чтобы найти элемент, надо в худшем случае пройти все n штук — это O(n). Вот почему x in my_dict намного быстрее, чем x in my_list на больших данных.
Плата за скорость — словарь занимает больше памяти и ключи должны быть хешируемыми (неизменяемыми): строки, числа, кортежи — можно, список — нельзя.
Коротко: список ищет перебором (O(n)), словарь — по адресу из хеша (O(1) в среднем). Поэтому для проверки «есть ли элемент» бери set/dict, а не список.
Бывают коллизии (два ключа дали один хеш), их разруливают внутри, поэтому формально «в среднем» O(1), а в патологическом худшем — O(n). На практике почти всегда O(1).
