Автор: CoolPython
Представьте себе огромную библиотеку, в которой вы хотите найти «Пикник на обочине». Как это сделать?
Наивный способ — перебирать. Взять первую книгу, понять, что это не Стругацкие, поставить обратно, взять следующую, … и так далее. В лучшем случае «Пикник на обочине» окажется в первой ячейке и мы справимся за один ход. В худшем придется перебрать все n книг библиотеки, за за O(n) шагов. Но можно быстрее.
Для этого определим функцию, которая получает название книги и возвращает число. Такая функция-справочник:
«Пикник на обочине» -> 1
«Декамерон» -> 2
«Уловка 22» -> 3
…
Положим «Пикник на обочине» на первую полку, «Декамерон» на вторую, и так далее. Когда нам понадобится книга, мы отправим название в эту функцию и сразу получим номер ячейки. Теперь книгу можно найти всего за два шага:
- вычислить номер книги по названию,
- найти ее на полке с этим номером.
Получается сложность O(1), и это очень быстро! Положить книгу на свое место тоже можно за фиксированное число шагов, вне зависимости от размера библиотеки. Побочным эффектом такого подхода будет то, что в библиотеке не будет дубликатов книг, ведь все копии «Декамерона» будут попадать в ячейку с одним и тем же адресом.
Функция, которая ставит объекту в соответствие число, называется хеш-функцией. Любая хеш-функция должна удовлетворять требованию:
Если два объекта идентичны, то их хеши равны.
Идеальная хеш-функция должна удовлетворять еще одному требованию:
Если у двух объектов одинаковый хеш, то это одинаковые объекты.
На практике даже хорошую хеш-функцию написать сложно. Поэтому иногда бывает так, что хеш-функция возвращает два одинаковых числа для разных входных данных. Например, если хеш-функция вернула
«Облачный атлас» -> 10
«Москва-Петушки» -> 10
то это значит, что мы должны поставить две разные книги на одну полку. И когда мы приходим за книгой с номером 10, становится непонятно, какую из книг выбрать.
Какое отношение эта проблема имеет к Python? Дело в том, что множества и словари в Python реализованы как хеш-таблицы, — то есть, ровно такие библиотеки с книгами на полках. Когда вы помещаете пару ключ-значение в словарь, интерпретатор вычисляет хеш ключа и кладет значение в ячейку памяти с адресом, совпадающим с результатом работы хеш-функции.
И если вдруг оказывается, что «Облачный атлас» и «Москва-Петушки» нужно положить в одну и ту же ячейку, то такую ситуацию называют коллизией.
Способов бороться с хеш-коллизиями концептуально два.
1. Метод цепочки
В этом методе каждая ячейка массива — это указатель на связный список пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной больше одного элемента.
Это как если положить все книги с одинаковым номером на одну полку. Тогда при поиске книги придется найти нужную полку, взять первую книгу и прочитать название. Если не та — проверить следующую, и так далее. В худшем случае все n книг попадут на одну полку и сложность получится O(n).
2. Открытая адресация
В этом случае в ячейки помещаются не указатели на списки, а сами пары ключ-значение. Алгоритм такой: вычисляем хеш-функцию, проверяем нужную ячейку. Если искомого элемента нет, то ищем в следующей ячейке. Следующую ячейку выбирают разными методами: это может быть просто фиксированный интервал до следующей ячейки, повторное хеширование вспомогательной хеш-функцией или другие методы.
Говоря языком библиотекаря, в этом случае библиотека получается большая, но полупустая. Потому что если полка, на которую вы хотели положить книгу, оказалась занята, вы выбираете другую свободную полку и кладете книгу туда. А потом по такому же алгоритму вычисляете, где находится нужная книга.
В Python множествах и словарях используется метод открытой адресации.
Какие из всего этого выводы?
- Ключи словаря должны быть хешируемыми.
- Словари неэффективны по памяти. Если экономите память, используйте кортежи.
- Поиск по ключу в итоге не O(1), но все равно очень быстрый.
- Модифицировать словарь, по которому итерируешься, — плохая идея. Интерпретатор может решить, что пора ресайзить хеш-таблицу, и тогда старые данные переедут в новую табличку. Не стоит.
И все то же самое применимо к множествам, потому что они реализованы похожим образом.
- А ещё становится понятно, что множества работают сильно быстрее списоков.
