Зозулин фільтр (англ. cuckoo filter) — це імовірнісна структура даних, яка використовується для перевірки того, чи елемент належить до множини, подібно до фільтр Блума . Хибно позитивні збіги можливі, але не хибно негативні – іншими словами, запит повертає «можливо в наборі» або «безумовно не в наборі». Зозулин фільтр, дозволяє видаляти наявні елементи, що не можливо з використанням фільтра Блума. Крім того, для додатків, які зберігають багато елементів і орієнтовані на помірно низьку долю хибно-позитивних результатів, фільтри зозулі можуть досягти меншого використання пам'яті, ніж оптимізовані по пам'яті фільтри Блума.
Зозулині фільтри були вперше описані в 2014 році
Опис алгоритму У фільтрі зозулі використовується -канальна множинно-асоціативна хеш-таблиця на основі хешування зозулі для зберігання цифрових відбитків усіх елементів (кожна корзина хеш-таблиці може зберігати до записів).
Зокрема, два індекси потенційних корзин і в таблиці для певного елемента обчислюються за допомогою двох хеш-функцій (має назву хешування с частковим ключем, ) ):
Застосування двох вищезазначених хеш-функцій для побудови зозулиної хеш-таблиці дає змогу переміщувати елементи лише на основі цифрових відбитків, в умовах коли отримати оригінальний елемент неможливо. Як наслідок, під час вставки нового елемента, який вимагає переміщення існуючого елемента , інше можливе розташування для елемента , витісненого з корзини розраховується за формулою
Базуючись на хешуванні зозулі з частковим ключем, хеш-таблиця може досягти як високого рівня використання (завдяки хешуванню зозулі), так і компактності, оскільки зберігаються лише цифрові відбитки. Операції пошуку та видалення для фільтра зозулі прості. Існує максимум два місця і , які варто перевірити. Якщо елемент знайдено, відповідна операція пошуку або видалення може бути виконана за час . Більше теоретичного аналізу фільтрів зозулі можна знайти в літературі.
Порівняння з фільтрами Блума Зозулин фільтр подібний до фільтра Блума тим, що вони обидва дуже швидкі та компактні, і обидва вони можуть повертати хибно позитивні результати:
Оптимальних по пам'яті фільтри Блума використовують біт місця для кожного вставленого ключа, де це коефіцієнт хибно позитивних результатів. Зозулиному фільтру необхідно де це коефіцієнт завантаження хеш-таблиці, який може бути на основі налаштувань зозулиного фільтра. Варто зазначити, що теоретична нижня межа об'єму пам'яті складає бітів для кожного елемента. При позитивному пошуку оптимальний для пам'яті фільтр Блума вимагає константно операцій звернення до бітового масиву, тоді як зозулин фільтр потребує щонайбільше двох таких операції. Після досягнення порогового значення навантаження швидкість вставки до фільтра зозулі може деградувати. В такому випадку рекомендується розширення таблиці. Навпроти, фільтри Блума можуть продовжувати вставляти нові елементи без розширення таблиці, але це можливо ціною отримання вищого рівня хибно позитивних результатів.
Обмеження
Зозулин фільтр може видаляти лише елементи, про які відомо, що вони були вставлені раніше. Вставка може бути невдалою, в такому випадку хешування потрібно проводити наново. Варто зазначити, що амортизована складність вставки залишається .
Посилання