Введение
Схема хеширования структуры данных
Cuckoo hashing — это схема в компьютерном программировании для разрешения коллизий хеш-функций в таблице, обеспечивающая постоянное время поиска в худшем случае. Название происходит от поведения некоторых видов кукушек, которые выталкивают другие яйца или птенцов из гнезда, когда вылупляются, что является разновидностью гнездового паразитизма. Аналогично, при вставке нового ключа в таблицу Cuckoo hashing, более старый ключ может быть перемещен в другое место в таблице.
История
Cuckoo hashing был впервые описан Расмусом Пагом и Флемингом Фричем Родлером в статье, представленной на конференции в 2001 году. В 2020 году эта статья была удостоена награды "Test of Time" Европейского симпозиума по алгоритмам.
Операции
Кукушечное хеширование – это разновидность открытой адресации, в которой каждая непустая ячейка хеш-таблицы содержит ключ или пару ключ-значение. Хеш-функция используется для определения местоположения каждого ключа, и наличие ключа в таблице (или связанного с ним значения) можно определить, просмотрев эту ячейку таблицы. Однако, открытая адресация подвержена коллизиям, которые возникают, когда более одного ключа отображается в одну и ту же ячейку. Основная идея кукушечного хеширования заключается в разрешении коллизий путем использования двух хеш-функций вместо одной. Это предоставляет два возможных местоположения в хеш-таблице для каждого ключа. В одном из распространенных вариантов алгоритма хеш-таблица разделяется на две меньшие таблицы одинакового размера, и каждая хеш-функция предоставляет индекс в одну из этих двух таблиц. Также возможно, чтобы обе хеш-функции предоставляли индексы в одну таблицу.
Удаление
Удаление происходит мгновенно, поскольку не требуется поиск. Это не учитывает стоимость операции сжатия, если таблица слишком разрежена.
Практика
На практике, кукушечное хеширование примерно на 20–30% медленнее, чем линейное зондирование, которое является самым быстрым из распространенных подходов. Другая обобщенная версия кукушечного хеширования, называемая блочным кукушечным хешированием, использует более одного ключа на ячейку и сбалансированную схему распределения. Использование всего 2 ключей на ячейку позволяет достичь коэффициента загрузки выше 80%. Еще одна изученная разновидность кукушечного хеширования – кукушечное хеширование со стешем (тайником). Стэш в этой структуре данных представляет собой массив, содержащий постоянное число ключей, используемых для хранения ключей, которые не удалось успешно вставить в основную хэш-таблицу. Эта модификация снижает вероятность неудачи кукушечного хеширования до обратно-полиномиальной функции, показатель степени которой можно произвольно увеличивать, увеличивая размер стеша. Однако большие стеши также приводят к более медленному поиску ключей, которые отсутствуют или находятся в стеше. Стэш можно использовать в сочетании с более чем двумя хеш-функциями или с блочным кукушечным хешированием для достижения как высоких коэффициентов загрузки, так и низких показателей отказов. Анализ кукушечного хеширования со стешем распространяется на практические хеш-функции, а не только на модель случайных хеш-функций, обычно используемую в теоретическом анализе хеширования. Некоторые специалисты рекомендуют упрощенную обобщенную версию кукушечного хеширования, называемую искаженным ассоциативным кэшем, для использования в некоторых кэшах ЦП. Другая разновидность кукушечной хэш-таблицы, называемая кукушечным фильтром, заменяет хранимые ключи кукушечной хэш-таблицы гораздо более короткими отпечатками, вычисляемыми путем применения другой хеш-функции к ключам. Чтобы эти отпечатки могли перемещаться внутри кукушечного фильтра, не зная ключей, из которых они получены, два местоположения каждого отпечатка могут быть вычислены друг из друга с помощью операции исключающего ИЛИ с отпечатком или с хешем отпечатка. Эта структура данных формирует приближенную структуру данных для проверки принадлежности к множеству, обладающую схожими свойствами с фильтром Блума: она может хранить элементы множества ключей и проверять, является ли ключ-запрос элементом множества, с некоторой вероятностью ложных срабатываний (запросы, которые ошибочно определяются как принадлежащие множеству), но без ложных отрицаний. Однако она превосходит фильтр Блума по нескольким параметрам: ее использование памяти меньше на постоянный коэффициент, она обладает лучшей локальностью ссылок и (в отличие от фильтров Блума) позволяет быстро удалять элементы множества без дополнительных затрат на хранение.