Кукушкино хеширование

Схема хеширования структуры данных

Пример хеширования Cuckoo. Стрелки показывают альтернативное расположение каждого ключа. Новый элемент будет вставлен в расположение A путем перемещения A в его альтернативное расположение, в настоящее время занятое B, и перемещения B в его альтернативное расположение, которое в настоящее время свободно. Вставка нового элемента в расположение H не будет успешной: поскольку H является частью цикла (вместе с W), новый элемент будет снова выброшен.

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

История

Впервые хеширование кукушки было описано Расмусом Пагом и Флеммингом Фриче Родлером в докладе на конференции 2001 года. ^[1] В 2020 году доклад был удостоен награды European Symposium on Algorithms Test-of-Time. ^{[2] : 122}

Операции

Кукушечное хеширование — это форма открытой адресации , в которой каждая непустая ячейка хеш-таблицы содержит ключ или пару ключ-значение . Хеш-функция используется для определения местоположения каждого ключа, и его присутствие в таблице (или значение, связанное с ним) можно обнаружить, изучив эту ячейку таблицы. Однако открытая адресация страдает от коллизий , которые случаются, когда более одного ключа сопоставляются с одной и той же ячейкой. Основная идея кукушечного хеширования заключается в разрешении коллизий с помощью двух хеш-функций вместо одной. Это обеспечивает два возможных местоположения в хеш-таблице для каждого ключа. В одном из часто используемых вариантов алгоритма хеш-таблица разбивается на две меньшие таблицы одинакового размера, и каждая хеш-функция предоставляет индекс в одну из этих двух таблиц. Также возможно, чтобы обе хеш-функции предоставляли индексы в одну таблицу. ^{[1] : 121-122}

Искать

Хеширование Cuckoo использует две хеш-таблицы, и . Предполагая, что — длина каждой таблицы, хеш-функции для двух таблиц определяются как, и где — ключ, а — набор, ключи которого хранятся в или . Операция поиска выглядит следующим образом: ^{[1] : 124} ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle r}$ ${\displaystyle h_{1},\ h_{2}\ :\ \cup \rightarrow \{0,...,r-1\}}$ ${\displaystyle \forall x\in S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle T_{1}}$ ${\displaystyle h_{2}(x)}$ ${\displaystyle T_{2}}$

Логическое ИЛИ ( ) означает, что значение ключа находится либо в , либо , что является худшим случаем. ^{[1] : 123} ${\displaystyle \vee }$ ${\displaystyle x}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle O(1)}$

Удаление

Удаление выполняется вовремя, поскольку зондирование не задействовано. Это игнорирует стоимость операции сжатия, если таблица слишком разреженная. ^{[1] : 124-125} ${\displaystyle O(1)}$

Вставка

При вставке нового элемента с ключом первым шагом является проверка того, занят ли слот таблицы . Если нет, элемент вставляется в этот слот. Однако, если слот занят, существующий элемент удаляется и вставляется в . Затем вставляется в таблицу , следуя той же процедуре. Процесс продолжается до тех пор, пока не будет найдена пустая позиция для вставки ключа. ^{[1] : 124-125} Чтобы избежать бесконечного цикла , указывается пороговое значение . Если количество итераций превышает этот фиксированный порог, и и перехешируются с новыми хеш-функциями, и процедура вставки повторяется. Ниже приведен псевдокод для вставки: ^{[1] : 125} ${\displaystyle x}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle T_{1}}$ ${\displaystyle x'}$ ${\displaystyle x}$ ${\displaystyle T_{1}[h_{1}(x)]}$ ${\displaystyle x'}$ ${\displaystyle T_{2}}$ ${\displaystyle {\text{Max-Loop}}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

В строках 10 и 15 «подход кукушки» с выбиванием других клавиш, которые занимают, повторяется до тех пор, пока каждая клавиша не получит свое собственное «гнездо», т. е. элемент не будет вставлен в пустой слот в любой из двух таблиц. Нотация выражает обмен и . ^{[1] : 124-125} ${\displaystyle T_{1,2}[h_{1,2}(x)]}$ ${\displaystyle x}$ ${\displaystyle x\leftrightarrow y}$ ${\displaystyle x}$ ${\displaystyle y}$

Теория

Вставки выполняются успешно за ожидаемое постоянное время ^[1], даже с учетом возможности необходимости перестроения таблицы, при условии, что количество ключей не превышает половины емкости хеш-таблицы, т. е. коэффициент загрузки составляет менее 50%.

Один из методов доказательства этого использует теорию случайных графов : можно сформировать неориентированный граф , называемый «графом кукушки», который имеет вершину для каждого местоположения хэш-таблицы и ребро для каждого хэшированного значения, причем конечные точки ребра являются двумя возможными местоположениями значения. Тогда жадный алгоритм вставки для добавления набора значений в хэш-таблицу кукушки будет успешным тогда и только тогда, когда граф кукушки для этого набора значений является псевдолесом , графом с не более чем одним циклом в каждом из его связанных компонентов . Любой подграф, индуцированный вершиной, с большим количеством ребер, чем вершин, соответствует набору ключей, для которых в хэш-таблице недостаточное количество слотов. Когда хэш-функция выбирается случайным образом, граф кукушки является случайным графом в модели Эрдёша–Реньи . С высокой вероятностью, для коэффициента загрузки менее 1/2 (соответствующего случайному графу, в котором отношение числа ребер к числу вершин ограничено ниже 1/2), граф является псевдолесом, и алгоритм хеширования кукушки успешно размещает все ключи. Та же теория также доказывает, что ожидаемый размер связного компонента графа кукушки мал, гарантируя, что каждая вставка занимает постоянное ожидаемое время. Однако, также с высокой вероятностью, коэффициент загрузки более 1/2 приведет к гигантскому компоненту с двумя или более циклами, что приведет к сбою структуры данных и необходимости изменения размера. ^[3]

Поскольку теоретическая случайная хеш-функция требует слишком много места для практического использования, важным теоретическим вопросом является то, какие практические хеш-функции достаточны для хеширования Cuckoo. Один из подходов заключается в использовании k-независимого хеширования . В 2009 году было показано ^[4], что достаточно k-независимости, и требуется как минимум 6-независимость. Другой подход заключается в использовании табуляции хеширования , которая не является 6-независимой, но, как было показано в 2012 году ^[5] , имеет другие свойства, достаточные для хеширования Cuckoo. Третий подход от 2014 года ^[6] заключается в небольшой модификации хеш-таблицы cuckoo с так называемым stash, что позволяет использовать не более 2-независимых хеш-функций. ${\displaystyle O(\log n)}$

Упражняться

На практике хеширование кукушки примерно на 20–30% медленнее линейного зондирования , которое является самым быстрым из распространенных подходов. ^[1] Причина в том, что хеширование кукушки часто приводит к двум промахам кэша за поиск, чтобы проверить два местоположения, где может храниться ключ, в то время как линейное зондирование обычно приводит только к одному промаху кэша за поиск. Однако из-за его наихудших гарантий по времени поиска хеширование кукушки все еще может быть ценным, когда требуются скорости отклика в реальном времени .

Пример

Даны следующие хеш-функции (две младшие цифры k в основании 11):

${\displaystyle h\left(k\right)=k{\bmod {1}}1}$
${\displaystyle h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor {\bmod {1}}1}$

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

Цикл

Если вы попытаетесь вставить элемент 45, то вы попадете в цикл и потерпите неудачу. В последней строке таблицы мы снова находим ту же начальную ситуацию, что и в начале.

${\displaystyle h\left(45\right)=45{\bmod {1}}1=1}$
${\displaystyle h'\left(45\right)=\left\lfloor {\frac {45}{11}}\right\rfloor {\bmod {1}}1=4}$

Вариации

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

Можно ожидать, что обобщения хеширования кукушки, использующие более двух альтернативных хеш-функций, будут эффективно использовать большую часть емкости хеш-таблицы, жертвуя при этом некоторой скоростью поиска и вставки. Использование всего трех хеш-функций увеличивает нагрузку до 91%. ^[7]

Другое обобщение хеширования кукушки, называемое блочным хешированием кукушки, использует более одного ключа на ведро и сбалансированную схему распределения. Использование всего 2 ключей на ведро позволяет получить коэффициент загрузки выше 80%. ^[8]

Другой изученной разновидностью хеширования кукушки является хеширование кукушки с помощью тайника . Тайник в этой структуре данных представляет собой массив постоянного числа ключей, используемых для хранения ключей, которые не могут быть успешно вставлены в основную хеш-таблицу структуры. Эта модификация снижает частоту отказов хеширования кукушки до функции обратного полинома с показателем, который может быть сделан произвольно большим за счет увеличения размера тайника. Однако большие тайники также означают более медленный поиск ключей, которые отсутствуют или находятся в тайнике. Тайник можно использовать в сочетании с более чем двумя хеш-функциями или с заблокированным хешированием кукушки для достижения как высоких коэффициентов загрузки, так и малых частот отказов. ^[9] Анализ хеширования кукушки с помощью тайника распространяется на практические хеш-функции, а не только на модель случайной хеш-функции, обычно используемую в теоретическом анализе хеширования. ^[10]

Некоторые рекомендуют упрощенное обобщение хеширования кукушки, называемое перекошенно-ассоциативным кэшем, в некоторых кэшах ЦП . ^[11]

Другая вариация хэш-таблицы кукушки, называемая фильтром кукушки , заменяет сохраненные ключи хэш-таблицы кукушки гораздо более короткими отпечатками, вычисленными путем применения другой хэш-функции к ключам. Чтобы эти отпечатки можно было перемещать внутри фильтра кукушки, не зная ключей, из которых они пришли, два местоположения каждого отпечатка могут быть вычислены друг из друга с помощью побитовой исключающей операции или с отпечатком или с хешем отпечатка. Эта структура данных образует приблизительную структуру данных членства набора с почти такими же свойствами, как фильтр Блума : он может хранить элементы набора ключей и проверять, является ли ключ запроса членом, с некоторой вероятностью ложных срабатываний (запросы, которые неправильно сообщаются как часть набора), но без ложных срабатываний . Однако он улучшает фильтр Блума во многих отношениях: его использование памяти меньше на постоянный множитель, он имеет лучшую локальность ссылок и (в отличие от фильтров Блума) он позволяет быстро удалять элементы набора без дополнительных штрафов за хранение. ^[12]

Сравнение с родственными структурами

Исследование Зуковски и др. ^[13] показало, что хеширование кукушки намного быстрее, чем цепочечное хеширование для небольших кэш -резидентных хеш-таблиц на современных процессорах. Кеннет Росс ^[14] показал, что сегментированные версии хеширования кукушки (варианты, которые используют сегменты, содержащие более одного ключа) быстрее обычных методов также для больших хеш-таблиц, когда использование пространства высоко. Производительность сегментированной хеш-таблицы кукушки была дополнительно исследована Аскитисом ^[15] с ее производительностью, сравненной с альтернативными схемами хеширования.

В обзоре Митценмахера ^[7] представлены открытые проблемы, связанные с хешированием кукушки, по состоянию на 2009 год.

Известные пользователи

Cuckoo hashing используется в системе рекомендаций TikTok для решения проблемы «внедрения коллизий таблиц», которая может привести к снижению качества модели. Система рекомендаций TikTok «Monolith» использует преимущество разрешения коллизий cuckoo hashing, чтобы предотвратить сопоставление различных концепций с одними и теми же векторами. ^[16]

Смотрите также

• Идеальное хеширование
• Двойное хеширование
• Квадратичный зонд
• Классики хэширование

Ссылки

1. Пах, Расмус ; Родлер, Флемминг Фриш (2001). «Кукушка Хашинг». Алгоритмы — ЕКА 2001 . Конспекты лекций по информатике. Том. 2161. CiteSeerX  10.1.1.25.4189 . дои : 10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
2. «ESA - Европейский симпозиум по алгоритмам: Премия ESA за испытание временем 2020» . esa-symposium.org . Наградной комитет: Ури Цвик , Самир Хуллер , Эдит Коэн . Архивировано из оригинала 22 мая 2021 г. Проверено 22 мая 2021 г.{{cite web}}: CS1 maint: другие ( ссылка )
3. Кутцельнигг, Рейнхард (2006). Двудольные случайные графы и кукушкино хеширование (PDF) . Четвертый коллоквиум по математике и информатике. Дискретная математика и теоретическая информатика. Т. AG. С. 403–406.
4. Коэн, Джеффри С. и Дэниел М. Кейн. «Границы независимости, необходимые для хеширования кукушки». Труды ACM по алгоритмам (2009).
5. Патрашку, Михай и Миккель Торуп. «Мощь простого табуляционного хеширования». Журнал ACM (JACM) 59.3 (2012): 1-50.
6. Аумюллер, Мартин, Мартин Дицфельбингер и Филипп Вёльфель. «Явные и эффективные семейства хэшей достаточны для хэширования кукушки с помощью тайника». Algorithmica 70.3 (2014): 428-456.
7. Mitzenmacher, Michael (2009-09-09). "Некоторые открытые вопросы, связанные с хешированием кукушки" (PDF) . Труды ESA 2009. Получено 2010-11-10 .
8. Дицфельбингер, Мартин; Вайдлинг, Кристоф (2007). «Сбалансированное распределение и словари с плотно упакованными ячейками постоянного размера». Theoret. Comput. Sci . 380 (1–2): 47–68. doi : 10.1016/j.tcs.2007.02.054 . MR  2330641.
9. Кирш, Адам; Митценмахер, Майкл Д.; Видер, Уди (2010). «Более надежное хеширование: хеширование кукушки с заначкой». SIAM J. Comput . 39 (4): 1543–1561. doi :10.1137/080728743. MR  2580539.
10. Аумюллер, Мартин; Дитцфельбингер, Мартин; Вёльфель, Филипп (2014). «Явные и эффективные семейства хэшей достаточны для хэширования кукушки с помощью тайника». Algorithmica . 70 (3): 428–456. arXiv : 1204.4431 . doi :10.1007/s00453-013-9840-x. MR  3247374. S2CID  1888828.
11. «Микроархитектура».
12. Фань, Бин; Андерсен, Дэйв Г.; Камински, Майкл; Митценмахер, Майкл Д. (2014), «Фильтр кукушки: практически лучше, чем Bloom», Труды 10-й Международной конференции ACM «Развивающиеся сетевые эксперименты и технологии» (CoNEXT '14) , стр. 75–88, doi : 10.1145/2674005.2674994
13. Жуковски, Марчин; Хеман, Шандор; Бонц, Питер (июнь 2006 г.). "Архитектурно-осознанное хеширование" (PDF) . Труды Международного семинара по управлению данными на новом оборудовании (DaMoN) . Получено 16 октября 2008 г.
14. Росс, Кеннет (2006-11-08). Эффективные хэш-пробы на современных процессорах (PDF) (Исследовательский отчет). IBM. RC24100 . Получено 2008-10-16 .
15. Аскитис, Николас (2009). «Быстрые и компактные хэш-таблицы для целочисленных ключей». Труды 32-й Австралазийской конференции по компьютерным наукам (ACSC 2009) (PDF) . Том 91. С. 113–122. ISBN 978-1-920682-72-9. Архивировано из оригинала (PDF) 2011-02-16 . Получено 2010-06-13 .
16. "Monolith: система рекомендаций, стоящая за TikTok". gantry.io . Получено 2023-05-30 .

Внешние ссылки

• Крутая и практичная альтернатива традиционным хеш-таблицам. Архивировано 07.04.2019 на Wayback Machine , U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing для студентов, 2006, Р. Паг, 2006.
• Cuckoo Hashing, теория и практика (часть 1, часть 2 и часть 3), Михаэль Митценмахер, 2007.
• Наор, Мони; Сегев, Гил; Видер, Уди (2008). «Независимое от истории хеширование кукушек». Международный коллоквиум по автоматам, языкам и программированию (ICALP) . Рейкьявик, Исландия . Получено 21 июля 2008 г.
• Улучшения алгоритмов для быстрого параллельного хеширования Cuckoo, X. Ли, Д. Андерсен, М. Каминский, М. Фридман. EuroSys 2014.

Примеры

• Параллельная высокопроизводительная хеш-таблица Cuckoo, написанная на C++
• Хэш-карта Cuckoo, написанная на C++
• Генератор статических хеш-таблиц Cuckoo для C/C++
• Хэш-таблица Cuckoo, написанная на Haskell
• Хеширование Cuckoo для Go