Какова сложность поиска элемента по ключу?
Это зависит от того, какую структуру данных использовать.
В односвязном списке - линейная сложность.
В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.
В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…
А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?
В общем случае - нет. Но если список всех ключей установлен заранее и не изменяется, а хэш-коды у всех ключей различны, то можно построить идеальную хэш-таблицу без коллизий, где поиск любого элемента происходит за несколько тривиальных операций, причём, количество этих операций не зависит от размера хэш-таблицы.
Идеально! Поговорим о том, как это сделать.
Кстати, на курсе «Алгоритмы и структуры данных» на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.
Представьте англо-русский словарь. Английские слова являются ключами, а перевод - значениями. Время поиска любого слова в таком словаре может происходить за константное время, как если бы мы обращались к элементу массива по индексу!
Взял, такой, хэш-код слова “dog”, вычислил хэш-функцию, поколдовал ещё немножко, и, вуаля, в руках уже «собака» на
поводкеуказателе!
Как такое возможно?
Предположим, в словаре 10.000 слов-ключей. Для их хранения мы открываем хэш-таблицу на 10.000 элементов. Возможно ли создать «волшебную» хэш-функцию-биекцию, которая каждый ключ отображала бы на индекс массива, где он должен лежать? Наверное, это возможно, если создать «небольшую» нейронную сеть и обучить её.
Если же ограничиваться простейшей хэш-функцией вида «(A * k + B) % P % N», с возможностью подбора лишь двух коэффициентов A и В, то создать “волшебную” биекцию вряд ли удастся - коллизий не избежать. В этой формуле:k - хэшкод уникального ключа, P - заранее заданное простое число, большее любого возможного ключа k, N - размер хеш-таблицы, то есть количество всех ключей.
Идея идеального хэширования заключается в двухэтапном хэшировании.
На первом этапе находим «квартиру», а на втором этапе - «комнату», где располагается искомое значение.
Это напоминает метод разрешения коллизий методом цепочек. Но если в методе цепочек в каждой “квартире” расположен односвязный список «комнат», то в идеальном хэшировании мы в каждой квартире создадим отдельную хэш-таблицу с матрицей «комнат». Это будут «квадрокомнатные квартиры», но обо всём по порядку.
Первый этап
Минимизация количества «комнат» в «квартирах».
Поскольку список всех ключей известен заранее, то можно подобрать такие коэффициенты, чтобы максимальное количество «комнат» (коллизий) в одной «квартире» было минимальным. Достаточно несколько десятков попыток, чтобы минимизировать максимальное количество коллизий.
Например, за 100 итераций подбора коэффициентов для словаря из 10.000 ключей максимальное количество коллизий для одного элемента не превышает 10.
Итак, на первом этапе мы подбираем глобальные коэффициенты А и В для хэш-функции вида «(A * k + B) % P % N». Эта функция вычисляет номер «квартиры», в которой находится значение для заданного ключа. При этом минимизируется максимальное количество «комнат» (коллизий) в каждой «квартире».
Второй этап
Для размещения K элементов в одной «квартире» мы резервируем K² «комнат». Такая «квадрокомнатная квартира» позволит без особого труда подобрать коэффициенты A и B для размещения K элементов без единой коллизии, потому что значения всех ключей известно заранее (напомним, что хэш-коды всех ключей различны). Коэффициенты подбираются для каждой «квартиры» отдельно и хранятся в каждом элементе первой хэш-таблицы, вместе с количеством «комнат».
Вот и всё!
Для поиска любого элемента в идеальной хэш-таблице необходимо выполнить следующие действия:
Найти номер «квартиры»
iпо хэш-коду ключаk: «(A * k + B) % P % N».Взять коэффициенты для вычисления номера комнаты:
Ai,Bi,K².Найти номер «комнаты» по формуле:
«(Ai * k + Bi) % P % K²»Вернуть значение из найденной «комнаты».
В любом случае (как в лучшем, так и худшем) на поиск элемента потребуется константное количество действий, которое не зависит от общего количества элементов.
Расход памяти
Может показаться, что наличие «квадрокомнатных» квартир потребует слишком много памяти для хранения нашей идеальной хэш-таблицы. Продемонстрируем, что затраты по памяти не превышают линейную сложность (троекратный расход).
Возьмём, для примера, хэш-таблицу из N = 10 элементов. В каждом элементе может быть от 0 до 10 коллизий. Вычислим вероятность коллизий, умножим на затраты по памяти и найдём математическое ожидание объёма памяти для размещения одного элемента.
Итого: для хранения “квартир” нужно N ячеек памяти, для хранения “комнат” - примерно 1.9 * N. Суммарный расход памяти: 2.9 * N = О(N) - линейный.
Заключение
Если вы уже закончили работу над крупным проектом, все настройки которого хранятся в хэш-таблице, то вы можете выписать список всех-всех-всех параметров (ключей) и создать идеальную хэш-таблицу для их хранения, чтобы увеличить скорость доступа к этим элементам.
А теперь небольшой бонус. 15 января я проведу Demo Day курса "Алгоритмы и структуры данных" на платформе OTUS, приглашаю всех желающих узнать подробно о курсе и задать вопросы лично.
Также хочу посоветовать еще несколько статей из своего блога, которые уже успели получить хороший отклик у читателей:
