Хеширование с кукушкой

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

История

Хеширование с кукушкой было впервые описано Расмусом Пагом и Флеммингом Фришем Родлером в докладе на конференции 2001 года. ^[1] Статья была удостоена награды Европейского симпозиума по алгоритмам «Испытание временем» в 2020 году. ^[2]^: 122

Операции

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

Искать

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

 функция  поиска (x  возвращает     )   $T_{1}[h_{1}(x)]\ =\ x\vee T_{2}[h_{2}(x)]=x$  конечная функция

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

Удаление

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

Вставка

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

1  функция  (x)  Insert 2  если  поиск(x),  то 3  возврата 4  конец, если   цикла 5  циклов Максимальное  время 6,  если   $T_{1}[h_{1}(x)]$  =   $\bot$  затем 7  $T_{1}[h_{1}(x)]$  := х8  возврат 9  конец, если 10 х  $\leftrightarrow T_{1}[h_{1}(x)]$ 11  если   $T_{2}[h_{2}(x)]$  =   $\bot$  затем 12  $T_{2}[h_{2}(x)]$  := х13  возвращение 14  конец, если 15 х  $\leftrightarrow T_{2}[h_{2}(x)]$ 16  конечная петля 17 перефразирования()18 вставка(х)19  конечная функция

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

Теория

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

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

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

Упражняться

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

Пример

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

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

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

Таблица 1: используется h(k)
		Шаги
Номер шага		1	2	3	4	5	6	7	8	9	10
Ключ вставлен		53	50	20	75	100	67	105	3	36	45
ч(к)		9	6	9	9	1	1	6	3	3	1
Записи хеш-таблицы	0
	1					100	67	67	67	67	45
	2
	3								3	36	36
	4
	5
	6		50	50	50	50	50	105	105	105	105
	7
	8
	9	53	53	20	75	75	75	53	53	53	53
	10

Таблица 2: используется h′(k)
		Шаги
Номер шага		1	2	3	4	5	6	7	8	9	10
Ключ вставлен		53	50	20	75	100	67	105	3	36	45
ч'(к)		4	4	1	6	9	6	9	0	3	4
Записи хеш-таблицы	0									3	3
	1				20	20	20	20	20	20	20
	2
	3
	4			53	53	53	53	50	50	50	50
	5
	6							75	75	75	75
	7
	8
	9						100	100	100	100	100
	10

Цикл

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

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

Таблица 1	Таблица 2
45 заменяет 67 в ячейке 1	67 заменяет 75 в ячейке 6
75 заменяет 53 в ячейке 9	53 заменяет 50 в ячейке 4
50 заменяет 105 в ячейке 6.	105 заменяет 100 в ячейке 9.
100 заменяет 45 в ячейке 1	45 заменяет 53 в ячейке 4
53 заменяет 75 в ячейке 9	75 заменяет 67 в ячейке 6
67 заменяет 100 в ячейке 1	100 заменяет 105 в ячейке 9.
105 заменяет 50 в ячейке 6.	50 заменяет 45 в ячейке 4
45 заменяет 67 в ячейке 1	67 заменяет 75 в ячейке 6

Вариации

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

Крутая и практичная альтернатива традиционным хеш-таблицам. Архивировано 7 апреля 2019 г. в Wayback Machine , У. Эрлингссон, М. Манасс, Ф. Макшерри, 2006 г.
Хеширование кукушки для студентов, 2006 г. , Р. Пах, 2006 г.
Хеширование с кукушкой, теория и практика (Часть 1, Часть 2 и Часть 3 ), Майкл Митценмахер, 2007.
Наор, Мони; Сегев, Гил; Видер, Уди (2008). «Независимое от истории хеширование с кукушкой» . Международный коллоквиум по автоматам, языкам и программированию (ICALP) . Рейкьявик, Исландия . Проверено 21 июля 2008 г.
Алгоритмические улучшения для быстрого одновременного хеширования с кукушкой , К. Ли, Д. Андерсен, М. Камински, М. Фридман. ЕвроСис 2014.

Примеры

[Cuckoo-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) . Четвертый коллоквиум по математике и информатике. Дискретная математика и теоретическая информатика. Том. АГ. стр. 403–406.

[4] Коэн, Джеффри С. и Дэниел М. Кейн. «Границы независимости, необходимые для хеширования с кукушкой». Транзакции ACM в алгоритмах (2009).

[5] Путрашку, Михай и Миккель Торуп. «Сила простого хеширования таблиц». Журнал ACM (JACM) 59.3 (2012): 1-50.

[6] Аумюллер, Мартин, Мартин Дитцфельбингер и Филипп Вельфель. «Явных и эффективных хэш-семейств достаточно для кукушкиного хеширования с помощью тайника». Алгоритмика 70.3 (2014): 428-456.

[mitzenmacher2009survey-7] Перейти обратно: Перейти обратно: ^а ^б Митценмахер, Майкл (9 сентября 2009 г.). «Некоторые открытые вопросы, связанные с хешированием с кукушкой» (PDF) . Труды ЕКА 2009 . Проверено 10 ноября 2010 г.

[8] Дитцфельбингер, Мартин; Вейдлинг, Кристоф (2007). «Сбалансированное распределение и словари с плотно упакованными ячейками постоянного размера» . Теория. Вычислить. Наука . 380 (1–2): 47–68. дои : 10.1016/j.tcs.2007.02.054 . МР 2330641 .

[9] Кирш, Адам; Митценмахер, Майкл Д.; Видер, Уди (2010). «Более надежное хеширование: хеширование кукушки с тайником». СИАМ Дж. Компьютер . 39 (4): 1543–1561. дои : 10.1137/080728743 . МР 2580539 .

[10] Аумюллер, Мартин; Дитцфельбингер, Мартин; Вельфель, Филипп (2014). «Явных и эффективных хэш-семейств достаточно для кукушкиного хеширования с помощью тайника». Алгоритмика . 70 (3): 428–456. arXiv : 1204.4431 . дои : 10.1007/s00453-013-9840-x . МР 3247374 . S2CID 1888828 .

[11] «Микроархитектура» .

[12] Фан, Бин; Андерсен, Дэйв Г.; Каминский, Майкл; Митценмахер, Майкл Д. (2014), «Фильтр кукушки: практически лучше, чем Блум», Proc. 10-й Международный турнир ACM. Конф. Новые сетевые эксперименты и технологии (CoNEXT '14) , стр. 75–88, doi : 10.1145/2674005.2674994.

[13] Жуковский, Марцин; Хеман, Сандор; Бонч, Питер (июнь 2006 г.). «Хеширование с учетом архитектуры» (PDF) . Материалы международного семинара по управлению данными на новом оборудовании (DaMoN) . Проверено 16 октября 2008 г.

[14] Росс, Кеннет (08 ноября 2006 г.). Эффективные хеш-зонды на современных процессорах (PDF) (отчет об исследовании). ИБМ. RC24100 . Проверено 16 октября 2008 г.

[15] Аскитис, Николас (2009). «Быстрые и компактные хеш-таблицы для целочисленных ключей». Материалы 32-й Австралазийской конференции по информатике (ACSC 2009) (PDF) . Том. 91. стр. 113–122. ISBN 978-1-920682-72-9 . Архивировано из оригинала (PDF) 16 февраля 2011 г. Проверено 13 июня 2010 г.

[16] «Монолит: система рекомендаций, лежащая в основе TikTok» . gantry.io . Проверено 30 мая 2023 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]