Хеширование с кукушкой - это схема в компьютерном программировании для разрешения хеш-коллизий значений хеш-функций в таблице с постоянным временем поиска в худшем случае . Название происходит от поведения некоторых видов кукушки , когда птенец кукушки выталкивает другие яйца или птенцов из гнезда, когда вылупляется; аналогично, вставка нового ключа в хеш-таблицу с кукушкой может переместить старый ключ в другое место в таблице.
История [ править ]
Кукушечное хеширование было впервые описано Расмусом Пагом и Флеммингом Фришем Родлером в 2001 году [1].
Операция [ править ]
Хеширование с кукушкой - это форма открытой адресации, при которой каждая непустая ячейка хеш-таблицы содержит ключ или пару ключ-значение . Хэш - функция используется для определения местоположения для каждого ключа, и его присутствие в таблице (или значение , связанное с ней) можно найти, исследуя эту ячейку таблицы. Однако открытая адресация страдает от коллизий., что происходит, когда одной и той же ячейке сопоставлено несколько ключей. Основная идея хеширования с кукушкой состоит в том, чтобы разрешать конфликты с помощью двух хеш-функций вместо одной. Это обеспечивает два возможных места в хеш-таблице для каждого ключа. В одном из часто используемых вариантов алгоритма хеш-таблица разделена на две меньшие таблицы равного размера, и каждая хеш-функция предоставляет индекс в одну из этих двух таблиц. Обе хэш-функции также могут предоставлять индексы в одну таблицу.
Поиск требует проверки всего двух мест в хеш-таблице, что в худшем случае занимает постоянное время. Это контрастирует со многими другими алгоритмами хэш-таблиц, которые могут не иметь постоянной границы наихудшего случая на время выполнения поиска. Удаление также может быть выполнено путем гашения ячейки, содержащей ключ, в постоянное время наихудшего случая, что проще, чем в некоторых других схемах, таких как линейное зондирование .
Когда вставлен новый ключ и одна из двух его ячеек пуста, он может быть помещен в эту ячейку. Однако, когда обе ячейки уже заполнены, необходимо будет переместить другие ключи на их вторые места (или обратно в их первые места), чтобы освободить место для нового ключа. Используется жадный алгоритм : новый ключ вставляется в одно из двух возможных мест, «выталкивая», то есть вытесняя любой ключ, который уже мог находиться в этом месте. Затем этот смещенный ключ вставляется в его альтернативное место, снова выбивая любой ключ, который может там находиться. Процесс продолжается таким же образом до тех пор, пока не будет найдена пустая позиция, завершая алгоритм. Тем не менее, этот процесс вставки может завершиться неудачно из-за входа в бесконечный цикл.или найдя очень длинную цепочку (длиннее заранее установленного порога, который является логарифмическим по размеру таблицы). В этом случае хеш-таблица перестраивается на месте с использованием новых хеш-функций :
Нет необходимости выделять новые таблицы для повторного хеширования: мы можем просто пройтись по таблицам для удаления и выполнить обычную процедуру вставки для всех ключей, обнаруженных не в предполагаемой позиции в таблице.
- Паг и Родлер, «Кукушка хэширования» [1]
Теория [ править ]
Вставки выполняются в течение ожидаемого постоянного времени [1], даже с учетом возможности необходимости перестроить таблицу, пока количество ключей остается ниже половины емкости хеш-таблицы, т. Е. Коэффициент загрузки ниже 50%.
Один из методов доказательства этого использует теорию случайных графов : можно сформировать неориентированный граф, называемый «графом кукушки», который имеет вершину для каждого местоположения хеш-таблицы и ребро для каждого хэшированного значения, причем конечные точки ребра являются два возможных местоположения значения. Затем алгоритм жадной вставки для добавления набора значений в хеш-таблицу с кукушкой будет успешным тогда и только тогда, когда граф с кукушкой для этого набора значений является псевдолесом , графом с не более чем одним циклом в каждом из его связанных компонентов . Любой индуцированный вершинами подграф с большим количеством ребер, чем вершин, соответствует набору ключей, для которого недостаточно слотов в хеш-таблице. Когда хеш-функция выбирается случайным образом, график с кукушкой представляет собойслучайный граф в модели Эрдеша – Реньи . С большой вероятностью для случайного графа, в котором отношение количества ребер к количеству вершин ограничено ниже 1/2, граф является псевдолесом, и алгоритм хеширования с кукушкой успешно размещает все ключи. Более того, та же теория также доказывает, что ожидаемый размер связной компоненты графа кукушки невелик, что гарантирует, что каждая вставка занимает постоянное ожидаемое время. [2]
Практика [ править ]
На практике хеширование с кукушкой примерно на 20–30% медленнее, чем линейное зондирование , которое является самым быстрым из распространенных подходов. [1] Причина в том, что хеширование с кукушкой часто вызывает два промаха кеша за поиск, чтобы проверить два места, где может храниться ключ, в то время как линейное зондирование обычно вызывает только один промах кеша за поиск. Однако из-за гарантии наихудшего случая в отношении времени поиска хеширование с кукушкой по-прежнему может быть полезным, когда требуется скорость ответа в реальном времени . Одним из преимуществ хеширования с кукушкой является свойство отсутствия списка ссылок, которое хорошо подходит для обработки на GPU.
Пример [ править ]
Даны следующие хэш-функции:
В следующих двух таблицах показана вставка некоторых примеров элементов. Каждый столбец соответствует состоянию двух хэш-таблиц во времени. Возможные места вставки для каждого нового значения выделены.
| Ключ вставлен | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| k | 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
| h (k) | 9 | 6 | 9 | 9 | 1 | 1 | 6 | 3 | 3 | 6 | |
| 0 | |||||||||||
| 1 | 100 | 67 | 67 | 67 | 67 | 100 | |||||
| 2 | |||||||||||
| 3 | 3 | 36 | 36 | ||||||||
| 4 | |||||||||||
| 5 | |||||||||||
| 6 | 50 | 50 | 50 | 50 | 50 | 105 | 105 | 105 | 39 | ||
| 7 | |||||||||||
| 8 | |||||||||||
| 9 | 20 | 20 | 20 | 75 | 75 | 75 | 53 | 53 | 53 | 75 | |
| 10 | |||||||||||
| Ключ вставлен | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| k | 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
| h ′ (k) | 1 | 4 | 4 | 6 | 9 | 6 | 9 | 0 | 3 | 3 | |
| 0 | 3 | 3 | |||||||||
| 1 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | ||||
| 2 | |||||||||||
| 3 | |||||||||||
| 4 | 53 | 53 | 53 | 53 | 50 | 50 | 50 | 53 | |||
| 5 | |||||||||||
| 6 | 75 | 75 | 75 | 67 | |||||||
| 7 | |||||||||||
| 8 | |||||||||||
| 9 | 100 | 100 | 100 | 100 | 105 | ||||||
| 10 | |||||||||||
Цикл [ править ]
Если вы сейчас попытаетесь вставить элемент 6, вы войдете в цикл и потерпите неудачу. В последней строке таблицы мы снова находим ту же исходную ситуацию, что и в начале.
| Таблица 1 | Таблица 2 |
|---|---|
| 6 заменяет 50 в ячейке 6 | 50 заменяет 53 в ячейке 4 |
| 53 заменяет 75 в ячейке 9 | 75 заменяет 67 в ячейке 6 |
| 67 заменяет 100 в ячейке 1 | 100 заменяет 105 в ячейке 9 |
| 105 заменяет 6 в ячейке 6 | 6 заменяет 3 в ячейке 0 |
| 3 заменяет 36 в ячейке 3 | 36 заменяет 39 в ячейке 3 |
| 39 заменяет 105 в ячейке 6 | 105 заменяет 100 в ячейке 9 |
| 100 заменяет 67 в ячейке 1 | 67 заменяет 75 в ячейке 6 |
| 75 заменяет 53 в ячейке 9 | 53 заменяет 50 в ячейке 4 |
| 50 заменяет 39 в ячейке 6 | 39 заменяет 36 в ячейке 3 |
| 36 заменяет 3 в ячейке 3 | 3 заменяет 6 в ячейке 0 |
| 6 заменяет 50 в ячейке 6 | 50 заменяет 53 в ячейке 4 |
Варианты [ править ]
Было изучено несколько вариантов хеширования с кукушкой, в первую очередь с целью улучшения использования пространства за счет увеличения допустимого коэффициента нагрузки до числа, превышающего 50% -ный порог базового алгоритма. Некоторые из этих методов также можно использовать для уменьшения частоты отказов хеширования с кукушкой, в результате чего перестройки структуры данных будут происходить гораздо реже.
Можно ожидать, что обобщения хеширования с кукушкой, использующие более двух альтернативных хэш-функций, будут эффективно использовать большую часть емкости хэш-таблицы, при этом жертвуя некоторой скоростью поиска и вставки. Использование всего трех хеш-функций увеличивает нагрузку до 91%. [3] Другое обобщение хеширования с кукушкой, называемое хешированием с кукушкой, состоит в использовании более одного ключа для каждой корзины. Использование всего 2 ключей на ведро обеспечивает коэффициент загрузки более 80%. [4]
Другой вариант хеширования с кукушкой, который был изучен, - это хеширование с кукушкой с тайником . Тайник в этой структуре данных представляет собой массив постоянного количества ключей, используемых для хранения ключей, которые не могут быть успешно вставлены в основную хеш-таблицу структуры. Эта модификация снижает частоту отказов хеширования с кукушкой до функции обратного полинома с показателем, который можно сделать произвольно большим, увеличив размер тайника. Однако большие тайники также означают более медленный поиск ключей, которых нет или которые находятся в тайнике. Тайник можно использовать в сочетании с более чем двумя хеш-функциями или с заблокированным хешированием с кукушкой для достижения как высоких коэффициентов нагрузки, так и небольшой частоты отказов. [5]Анализ хеширования с кукушкой с помощью тайника распространяется на практические хеш-функции, а не только на модель случайной хеш-функции, обычно используемую в теоретическом анализе хеширования. [6]
Некоторые люди рекомендуют упрощенное обобщение хеширования с кукушкой, называемое асимметричным ассоциативным кешем в некоторых кэшах ЦП . [7]
Другой вариант хэш-таблицы с кукушкой, называемый фильтром с кукушкой , заменяет сохраненные ключи хеш-таблицы с кукушкой гораздо более короткими отпечатками пальцев, вычисляемыми путем применения к клавишам другой хеш-функции. Чтобы позволить этим отпечаткам пальцев перемещаться внутри фильтра кукушки, не зная ключей, из которых они произошли, два местоположения каждого отпечатка пальца могут быть вычислены друг от друга с помощью побитового исключающего или операции с отпечатком пальца или с хешем. отпечатка пальца. Эта структура данных формирует приблизительную структуру данных членства в наборе с теми же свойствами, что и фильтр Блума : она может хранить элементы набора ключей и проверять, является ли ключ запроса членом, с некоторой вероятностью ложных срабатываний.(запросы, которые неправильно указаны как часть набора), но без ложных отрицаний . Однако он улучшает фильтр Блума во многих отношениях: его использование памяти меньше на постоянный коэффициент, у него лучшая локальность ссылки и (в отличие от фильтров Блума) он позволяет быстро удалять элементы набора без дополнительных затрат на хранение. [8]
[ править ]
Исследование Zukowski et al. [9] показал, что хеширование с кукушкой намного быстрее, чем цепное хеширование для небольших, резидентных кеш- таблиц на современных процессорах. Кеннет Росс [10] показал, что варианты хеширования с кукушкой (варианты, в которых используются сегменты, содержащие более одного ключа) быстрее, чем обычные методы, также для больших хеш-таблиц, когда используется много места. Аскитис [11] дополнительно исследовал производительность хеш-таблицы с кукушкой с разделением на столбцы, сравнив ее производительность с альтернативными схемами хеширования.
Обзор Митценмахера [3] представляет открытые проблемы, связанные с хешированием с кукушкой по состоянию на 2009 год.
См. Также [ править ]
- Идеальное хеширование
- Двойное хеширование
- Квадратичное зондирование
- Хеширование в классическом стиле
Ссылки [ править ]
- ^ a b c d Паг, Расмус; Родлер, Флемминг Фриче (2001). «Кукушка хеширования». Алгоритмы - ESA 2001 . Конспект лекций по информатике. 2161 . С. 121–133. CiteSeerX 10.1.1.25.4189 . DOI : 10.1007 / 3-540-44676-1_10 . ISBN 978-3-540-42493-2.
- ^ Kutzelnigg Рейнхард (2006). Двудольные случайные графы и хеширование с кукушкой (PDF) . Четвертый коллоквиум по математике и информатике. Дискретная математика и теоретическая информатика. AG . С. 403–406.
- ^ a b Митценмахер, Майкл (2009-09-09). "Некоторые открытые вопросы, связанные с хешированием кукушки | Материалы ESA 2009" (PDF) . Проверено 10 ноября 2010 . Cite journal requires
|journal=(help) - ^ Дицфельбингер, Мартин; Weidling, Christoph (2007), «Сбалансированное размещение и словари с плотно упакованными ячейками постоянного размера», Теорет. Comput. Sci. , 380 (1-2): 47-68, DOI : 10.1016 / j.tcs.2007.02.054 , МР 2330641 .
- ^ Кирш, Адам; Митценмахер, Майкл Д .; Видер, Уди (2010), "Более надежное хеширование: хеширование с кукушкой с тайником", SIAM J. Comput. , 39 (4): 1543-1561, DOI : 10,1137 / 080728743 , МР 2580539 .
- ^ Аумюллер, Мартин; Дицфельбингер, Мартин; Вельфель, Филипп (2014), «Явные и эффективные семейства хешей достаточно для хеширования кукушки с тайником», Algorithmica , 70 (3): 428–456, arXiv : 1204.4431 , doi : 10.1007 / s00453-013-9840-x , MR 3247374 .
- ^ «Микроархитектура» .
- ^ Вентилятор, Бин; Андерсен, Дэйв Дж .; Каминский, Михаил; Митценмахер, Майкл Д. (2014), «Фильтр кукушки: Практически лучше, чем Блум», Proc. 10-й ACM Int. Конф. Новые сетевые эксперименты и технологии (CoNEXT '14) , С. 75-88,. DOI : 10,1145 / 2674005,2674994
- ^ Zukowski, Marcin; Хеман, Сандор; Бонц, Питер (июнь 2006 г.). «Хеширование с учетом архитектуры» (PDF) . Материалы международного семинара по управлению данными на новом оборудовании (DaMoN) . Проверено 16 октября 2008 . Cite journal requires
|journal=(help) - ^ Росс, Кеннет (2006-11-08). «Эффективные хеш-зонды на современных процессорах» (PDF) . Отчет об исследованиях IBM RC24100. RC24100 . Проверено 16 октября 2008 . Cite journal requires
|journal=(help) - ^ Аскитис, Николас (2009). Быстрые и компактные хеш-таблицы для целочисленных ключей (PDF) . Материалы 32-й Австралазийской конференции по информатике (ACSC 2009) . 91 . С. 113–122. ISBN 978-1-920682-72-9. Архивировано из оригинального (PDF) 16 февраля 2011 года . Проверено 13 июня 2010 .
Внешние ссылки [ править ]
- Классная и практичная альтернатива традиционным хеш-таблицам , У. Эрлингссон, М. Манассе, Ф. Макшерри, 2006.
- Кукушка для студентов, 2006 , Р. Паг, 2006.
- Хеширование кукушки, теория и практика (часть 1, часть 2 и часть 3 ), Майкл Митценмахер, 2007.
- Наор, Мони; Сегев, Гил; Видер, Уди (2008). «Хеширование кукушки, не зависящее от истории» . Международный коллоквиум по автоматам, языкам и программированию (ICALP) . Рейкьявик, Исландия . Проверено 21 июля 2008 .
- Алгоритмические улучшения для быстрого одновременного хеширования кукушки , X. Ли, Д. Андерсен, М. Каминский, М. Фридман. EuroSys 2014.
Примеры [ править ]
- Параллельная высокопроизводительная хеш-таблица Cuckoo, написанная на C ++
- Хеш-карта кукушки, написанная на C ++
- Генератор статической хеш-таблицы с кукушкой для C / C ++
- Хеш-таблица с кукушкой, написанная на Haskell
- Хеширование с кукушкой для Go
