Как ищет элемент обычный список

Список представляет собой непрерывный массив указателей на объекты в оперативной памяти. Когда программе требуется найти элемент по его содержимому или найти кортеж с нужным идентификатором, у интерпретатора нет встроенного знания о том, где именно лежит искомое значение.

Компьютер начинает проверку с нулевого индекса, сравнивает текущий элемент с образцом, переходит к первому, второму и так далее. Если целевой элемент находится в самом конце коллекции или вовсе отсутствует, алгоритм выполняет ровно столько проверок, сколько элементов хранится в списке. Такую сложность в теории алгоритмов обозначают как O(n), где n равно общему числу записей. В среднем для нахождения ключа в массиве из 1000 элементов требуется около 500 операций сравнения.

Внутреннее устройство хеш-таблицы

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

Когда ты запрашиваешь значение по ключу, процессор не сканирует память подряд. Сначала ключ передается во встроенную хеш-функцию, которая преобразует произвольные данные вроде строки или числа в одно целое число фиксированной разрядности. В Python для этого используется встроенная функция hash(). Полученный хеш с помощью операции взятия остатка от деления или побитового умножения на маску размера таблицы превращается в конкретный индекс строки во внутреннем массиве словаря.

Зная точный индекс, программа сразу обращается к нужной ячейке памяти по прямому смещению адреса. Такая операция занимает фиксированное количество машинных инструкций вне зависимости от того, сколько записей хранится в структуре данных. Это поведение называют константным временем доступа и записывают как O(1).

Механизм разрешения коллизий

Количество возможных строк или чисел бесконечно, а размер таблицы в памяти строго ограничен. Рано или поздно два совершенно разных ключа при делении хеша выдают один и тот же индекс. Такую ситуацию называют коллизией.

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

Реальная разница в скорости на 1000 записей

Различие между O(1) и O(n) наглядно проявляется при прямом замере времени через стандартный модуль timeit.

Если создать список из 1000 пар ключ-значение и искать элемент ближе к концу списка, операция проверки условия равенства занимает в среднем от 10 до 25 микросекунд на современном процессоре. Поиск того же самого ключа в словаре аналогичного объема занимает около 30–50 наносекунд. Словарь опережает линейный перебор примерно в 300–500 раз.

С ростом объема данных этот разрыв увеличивается пропорционально. В коллекции на миллион записей список потратит на поиск уже десятки миллисекунд, заставляя интерфейс программы подвисать, тогда как словарь выдаст результат за те же самые 40 наносекунд.

Плата за скорость

Высокое быстродействие словаря достигается ценой повышенного расхода оперативной памяти. Хеш-таблица сохраняет скорость O(1) только при условии, что часть ее внутренних ячеек остается пустой. Если таблица заполнится полностью, поиск выродится в длинную цепочку разрешения коллизий.

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

Частые вопросы

Почему в качестве ключа словаря нельзя использовать список?

Ключ хеш-таблицы обязан обладать постоянным хеш-значением на протяжении всей жизни объекта. Списки относятся к изменяемым типам данных. Если добавить элемент в список-ключ, его внутреннее состояние изменится, а старый вычисленный хеш перестанет соответствовать ячейке памяти, что приведет к потере доступа к данным.

Что произойдет, если хеш-функция начнет выдавать одинаковые числа?

В худшем сценарии все добавленные элементы попадут в одну цепочку коллизий. В такой ситуации сложность поиска по ключу упадет с O(1) до O(n), и словарь станет работать с той же скоростью, что и медленный список.

Когда выгоднее выбрать список вместо словаря?

Список предпочтительнее в задачах, где важен минимальный расход оперативной памяти, требуется строгий порядок добавления элементов с частой вставкой в конец, либо доступ всегда идет по целочисленному индексу от нуля до конца коллекции.

Почему современные словари в Python сохраняют порядок добавления элементов?

Начиная с версии Python 3.6 реализацию словарей оптимизировали. Данные ключей и значений теперь хранятся в плотном упорядоченном массиве, а сама разреженная хеш-таблица содержит только небольшие числовые индексы, указывающие на этот массив. Это новшество сократило потребление памяти на треть и сделало сохранение порядка ключей естественным свойством словаря.