Как устроены словари в Python

Автор: PythonInDepth

Представьте себе огромную библиотеку, в которой вы хотите найти «Пикник на обочине». Как это сделать?

Наивный способ — перебирать. Взять первую книгу, понять, что это не Стругацкие, поставить обратно, взять следующую, … и так далее. В лучшем случае «Пикник на обочине» окажется в первой ячейке и мы справимся за один ход. В худшем придется перебрать все n книг библиотеки, за за O(n) шагов. Но можно быстрее.

Для этого определим функцию, которая получает название книги и возвращает число. Такая функция-справочник:

«Пикник на обочине» -> 1
«Декамерон» -> 2
«Уловка 22» -> 3

Положим «Пикник на обочине» на первую полку, «Декамерон» на вторую, и так далее. Когда нам понадобится книга, мы отправим название в эту функцию и сразу получим номер ячейки. Теперь книгу можно найти всего за два шага:

  1. вычислить номер книги по названию,
  2. найти ее на полке с этим номером.

Получается сложность O(1), и это очень быстро! Положить книгу на свое место тоже можно за фиксированное число шагов, вне зависимости от размера библиотеки. Побочным эффектом такого подхода будет то, что в библиотеке не будет дубликатов книг, ведь все копии «Декамерона» будут попадать в ячейку с одним и тем же адресом.

Функция, которая ставит объекту в соответствие число, называется хеш-функцией. Любая хеш-функция должна удовлетворять требованию:

Если два объекта идентичны, то их хеши равны.

Идеальная хеш-функция должна удовлетворять еще одному требованию:

Если у двух объектов одинаковый хеш, то это одинаковые объекты.

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

«Облачный атлас» -> 10
«Москва-Петушки» -> 10

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

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

И если вдруг оказывается, что «Облачный атлас» и «Москва-Петушки» нужно положить в одну и ту же ячейку, то такую ситуацию называют коллизией.

Способов бороться с хеш-коллизиями концептуально два.

1. Метод цепочки

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

Это как если положить все книги с одинаковым номером на одну полку. Тогда при поиске книги придется найти нужную полку, взять первую книгу и прочитать название. Если не та — проверить следующую, и так далее. В худшем случае все n книг попадут на одну полку и сложность получится O(n).

2. Открытая адресация

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

Говоря языком библиотекаря, в этом случае библиотека получается большая, но полупустая. Потому что если полка, на которую вы хотели положить книгу, оказалась занята, вы выбираете другую свободную полку и кладете книгу туда. А потом по такому же алгоритму вычисляете, где находится нужная книга.

В Python множествах и словарях используется метод открытой адресации.

Какие из всего этого выводы?

  • Ключи словаря должны быть хешируемыми.
  • Словари неэффективны по памяти. Если экономите память, используйте кортежи.
  • Поиск по ключу в итоге не O(1), но все равно очень быстрый.
  • Модифицировать словарь, по которому итерируешься, — плохая идея. Интерпретатор может решить, что пора ресайзить хеш-таблицу, и тогда старые данные переедут в новую табличку. Не стоит.

И все то же самое применимо к множествам, потому что они реализованы похожим образом.

  • А ещё становится понятно, что множества работают сильно быстрее списоков.

python logo

Свежие вакансии по Python

Для тех, кто хочет найти работу Junior Python Developer

×