[Алгоритмы, Поисковая оптимизация] Идеальное хэширование

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
11-Янв-2021 17:31

Цитировать

Какова сложность поиска элемента по ключу?Это зависит от того, какую структуру данных использовать.В односвязном списке - линейная сложность.В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?В общем случае - нет. Но если список всех ключей установлен заранее и не изменяется, а хэш-коды у всех ключей различны, то можно построить идеальную хэш-таблицу без коллизий, где поиск любого элемента происходит за несколько тривиальных операций, причём, количество этих операций не зависит от размера хэш-таблицы.Идеально! Поговорим о том, как это сделать.Представьте англо-русский словарь. Английские слова являются ключами, а перевод - значениями. Время поиска любого слова в таком словаре может происходит за константное время, как если бы мы обращались к элементу массива по индексу!

Взял, такой, хэш-код слова “dog”, вычислил хэш-функцию, поколдовал ещё немножко, и, вуаля, в руках уже “собака” на поводке указателе!

Как такое возможно?Предположим, в словаре 10.000 слов-ключей. Для их хранения мы открываем хэш-таблицу на 10.000 элементов. Возможно ли создать “волшебную” хэш-функцию-биекцию, которая каждый ключ отображала бы на индекс массива, где он должен лежать? Наверное, это возможно, если создать “небольшую” нейронную сеть и обучить её. Если же ограничиваться простейшей хэш-функцией вида “(Ak + B) % N”, с возможностью подбора лишь двух коэффициентов A и В, то создать “волшебную” биекцию вряд ли удастся - коллизий не избежать. В этой формуле k - уникальный хэшкод (ulong) уникального ключа.Идея идеального хэширования заключается в двухэтапном хэшировании.На первом этапе находим “квартиру”, а на втором этапе - “комнату”, где располагается искомое значение.Это напоминает метод разрешения коллизий методом цепочек. Но если в методе цепочек в каждой “квартире” расположен односвязный список “комнат”, то в идеальном хэшировании мы в каждой квартире создадим отдельную хэш-таблицу с матрицей “комнат”. Это будут “квадрокомнатные квартиры”, но обо всём по порядку.Первый этапМинимизация количества “комнат” в “квартирах”.Поскольку список всех ключей известен заранее, то можно подобрать такие коэффициенты, чтобы максимальное количество “комнат” (коллизий) в одной “квартире” было минимальным. Достаточно несколько десятков попыток, чтобы минимизировать максимальное количество коллизий. Например, за 100 итераций подбора коэффициентов для словаря из 10.000 ключей максимальное количество коллизий для одного элемента не превышает 10.Итак, на первом этапе мы подбираем глобальные коэффициенты А и В для хэш-функции вида “(A*k + B) % N”. Эта функция вычисляет номер “квартиры”, в которой находится значение для заданного ключа. При этом минимизируется максимальное количество “комнат” (коллизий) в каждой “квартире”.Второй этапДля размещения K элементов в одной “квартире” мы резервируем K² “комнат”. Такая “квадрокомнатная квартира” позволит без особого труда подобрать коэффициенты A и B для размещения K элементов без единой коллизии, потому что значения всех ключей известно заранее (напомним, что хэш-коды всех ключей различны). Коэффициенты подбираются для каждой “квартиры” отдельно и хранятся в каждом элементе первой хэш-таблицы, вместе с количеством “комнат”.Вот и всё!Для поиска любого элемента в идеальной хэш-таблице необходимо выполнить следующие действия:

Найти номер “квартиры” i по хэш-коду ключа k: “(A * k + B) % N”.
Взять коэффициенты для вычисления номера комнаты: Ai, Bi, K².
Найти номер “комнаты” по формуле: “(Ai * k + Bi) % K²”
Вернуть значение из найденной “комнаты”.

В любом случае (как в лучшем, так и худшем) на “поиск” элемента потребуется константное количество действий, которое не зависит от общего количества элементов.Расход памятиМожет показаться, что наличие “квадрокомнатных” квартир потребует слишком много памяти для хранения нашей идеальной хэш-таблицы. Продемонстрируем, что затраты по памяти не превышают линейную сложность (троекратный расход).Возьмём, для примера, хэш-таблицу из N = 10 элементов. В каждом элементе может быть от 0 до 10 коллизий. Вычислим вероятность коллизий, умножим на затраты по памяти и найдём математическое ожидание объёма памяти для размещения одного элемента.

Итого: для хранения “квартир” нужно N ячеек памяти, для хранения “комнат” - примерно 1.9 * N. Суммарный расход памяти: 2.9 * N = О(N) - линейный.ЗаключениеЕсли вы уже закончили работу над крупным проектом, все настройки которого хранятся в хэш-таблице, то вы можете выписать список всех-всех-всех параметров (ключей) и создать идеальную хэш-таблицу для их хранения, чтобы увеличить скорость доступа к этим элементам.А теперь небольшой бонус. 15 января я проведу Demo Day курса "Алгоритмы и структуры данных" на платформе OTUS, приглашаю всех желающих узнать подробно о курсе и задать вопросы лично. Также хочу посоветовать еще несколько статей из своего блога, которые уже успели получить хороший отклик у читателей:

===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_algoritmy (Алгоритмы), #_poiskovaja_optimizatsija (Поисковая оптимизация), #_idealnoe_heshirovanie (идеальное хеширование), #_heshtablitsy (хеш-таблицы), #_blog_kompanii_otus._onlajnobrazovanie (
Блог компании OTUS. Онлайн-образование
), #_algoritmy (
Алгоритмы
), #_poiskovaja_optimizatsija (
Поисковая оптимизация
)

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 16:09
Часовой пояс: UTC + 5