Зозулине хешування

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

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

Історія

Зозулине хешування було вперше описане Расмусом Пажом і Флеммінгом Фрішем Родлером у 2001.

Операції

Зозулине хешування є видом відкритої адресації, де кожна непуста комірка геш-таблиці містить ключ або пару ключ-значення. Хеш-функція використовується для визначення місця кожного ключа, його наявності в таблиці (або значення, асоційованого з ним) і може бути знайдене за допомогою перевірки цієї комірки в таблиці. Однак, відкрита адресація потерпає від колізій, які трапляються, коли більше одного ключа потрапляють в одну клітинку. Основна ідея зозулиного хешування полягає у розв'язанні колізій за допомогою використання двох хеш-функцій замість однієї. Це забезпечує два можливі положення у хеш-таблиці для кожного ключа. У одному з звичайних варіантів алгоритму хеш-таблиця розбивається на дві менші таблиці меншого розміру і кожна хеш-функція дає індекс у одну з цих двох таблиць. Можна забезпечити також для обох хеш-функцій індексування всередині однієї таблиці.

Вибірка вимагає перегляду всього двох місць в хеш-таблиці, що вимагає постійного часу в гіршому випадку (див. «O» велике і «o» мале). Це контрастує з багатьма іншими алгоритмами хеш-таблиць, які не забезпечують постійний час вибірки в гіршому випадку. Видалення також може бути здійснено очищенням комірки, що містить ключ, за постійний час в гіршому випадку, що здійснюється простіше, ніж в інших схемах, таких як лінійне зондування.

Коли вставляється новий ключ і одна з двох комірок порожня, ключ може бути поміщений в цю комірку. У разі ж, коли обидві комірки зайняті, необхідно перемістити інші ключі в інші місця (або, навпаки, на їх колишні місця), щоб звільнити місце для нового ключа. Використовується жадібний алгоритм — ключ поміщається в одну з можливих позицій, «виштовхуючи» будь-який ключ, який був в цій позиції. Виштовхнутий ключ потім поміщається в його альтернативну позицію, знову виштовхуючи будь-який ключ, який може там опинитися. Процес триває, поки не знайдеться порожня позиція. Проте, можливий випадок, коли процес вставки закінчується невдачею, потрапляючи в нескінченний цикл або коли утворюється надто довгий ланцюжок (довше, ніж заздалегідь заданий поріг, залежить логарифмічно від довжини таблиці). В цьому випадку хеш-таблиця перебудовується на місці з новими хеш-функціями:

	Немає необхідності розміщення нової таблиці для повторного хешування - ми можемо просто переглядати таблицю для видалення і повторної вставки всіх ключів, які знаходяться не в тій позиції, в якій повинні були б стояти.[1]
— Pagh & Rodler, «Cuckoo Hashing»

Теорія

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

Щоб забезпечити це, використовується теорія випадкових графів — можна утворити неорієнтований граф, званий «зозулиним графом», в якому вершинами є комірки хеш-таблиці, а ребра для кожного хешованого з'єднують два можливих положення (комірки хеш-таблиці). Тоді жадібний алгоритм вставки множини значень в зозулину хеш-таблицю успішно завершується тоді і тільки тоді, коли зозулин граф для цієї множини значень є псевдолісом — графом максимум з одним циклом в кожній компоненті зв'язності. Будь-який породжений вершинами підграф з числом ребер, більшим числа вершин, відповідає безлічі ключів, для яких число слотів в хеш-таблиці недостатнє. Якщо хеш-функція вибирається випадково, зозулиний граф буде випадковим графом в моделі Ердьоша — Ренї [en]. З високим ступенем ймовірності для випадкового графу, в якому відношення числа ребер до числа вершин обмежена зверху 1/2, граф є псевдолісом і алгоритм зозулиного хешування успішно розподіляє всі ключі. Більше того, та ж теорія доводить, що очікуваний розмір компонент зв'язності зозулиного графу малий, що забезпечує постійний очікуваний час вставки ^[2].

Приклад

Нехай дано такі дві хеш-функції:

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

k	h (k)	h '(k)
20	9	1
50	6	4
53	9	4
75	9	6
100	1	9
67	1	6
105	6	9
3	3	0
36	3	3
39	6	3

Стовпці в наступних двох таблицях показують стан хеш-таблиці після вставки елементів.

1. table for h(k)
	20	50	53	75	100	67	105	3	36	39
0
1					100	67	67	67	67	100
2
3								3	36	36
4
5
6		50	50	50	50	50	105	105	105	50
7
8
9	20	20	53	75	75	75	53	53	53	75
10

2. table for h'(k)
	20	50	53	75	100	67	105	3	36	39
0									3	3
1			20	20	20	20	20	20	20	20
2
3										39
4				53	53	53	50	50	50	53
5
6							75	75	75	67
7
8
9						100	100	100	100	105
10

Цикли

Якщо ви хочете вставити елемент 6, ви отримаєте нескінченний цикл. В останньому рядку таблиці ми знаходимо ту ж початкову ситуацію, що і на початку.

${\displaystyle h\left(6\right)=6\mod 11=6}$ ${\displaystyle h'\left(6\right)=\left\lfloor {\frac {6}{11}}\right\rfloor \mod 11=0}$

ключ	table 1		table 2
	старі значення	нові значення	старі значення	нові значення
6	50	6	53	50
53	75	53	67	75
67	100	67	105	100
105	6	105	3	6
3	36	3	39	36
39	105	39	100	105
100	67	100	75	67
75	53	75	50	53
50	39	50	36	39
36	3	36	6	3
6	50	6	53	50

Варіації

Вивчалися деякі варіації зозулиного хешування, в основному з метою поліпшити використання простору шляхом збільшення коефіцієнта завантаження. У цих варіантах може досягатися поріг навантаження більше 50 %. Деякі з цих методів можуть бути використані для істотного зменшення числа необхідних перебудов структури даних.

Від узагальнення зозулиного хешування, що використовує понад дві хеш-функцій, можна очікувати кращого використання хеш-таблиці, жертвуючи деякою швидкістю вибірки і вставки. Використання трьох хеш-функцій підвищує коефіцієнт завантаження до 91 % ^[3]. Інше узагальнення зозулиного хешування, зване блоковим зозулиним хешуванням, містить більше одного ключа на комірку. Використання двох ключів на комірку дозволяє підвищити завантаження вище 80 % ^[4].

Ще один варіант — зозулине хешування з запасом. «Запас» — це масив ключів постійної довжини, який використовується для зберігання ключів, які не можуть бути успішно вставлені в головну хеш-таблицю. Ця модифікація зменшує число невдач до назад-поліноміальної функції зі ступенем, яка може бути довільно великою, шляхом збільшення розміру запасу. Однак великий запас означає більш повільний пошук ключа, якого немає в основній таблиці, або якщо він знаходиться в запасі. Запас можна використовувати в комбінації з більш ніж двома хеш-функціями або з блоковим зозулиним хешуванням для отримання як високого ступеня завантаження, так і малого числа невдач вставки ^[5]. Аналіз зозулиного хешування з запасом поширився і на практичні хеш-функції, не тільки випадкові моделі хеш-функцій, які використовуються в теоретичному аналізі хешування ^[6].

Деякі дослідники пропонують використовувати в деяких кешах процесора спрощене узагальнення зозулиного хешування, званого несиметричним асоціативним кешем^[7].

Порівняння з аналогічними структурами

Є інші алгоритми, які використовують кілька хеш-функцій, зокрема фільтр Блума, ефективна по пам'яті структура даних для нечітких множин. Альтернативна структура даних для задач з тими ж нечіткими множинами, заснована на зозулиному хешуванні, звана зозулиним фільтром, використовує меншу кількість пам'яті і, на відміну від класичних фільтрів Блума, дозволяє не тільки вставку і перевірку існування але і видалення елемента. Однак теоретичний аналіз цих методів проведено значно слабше, ніж аналіз фільтрів Блума ^[8].

Дослідження, проведені Жуковським, Хеманом і Бонзом ^[9], показали, що зозулине хешування істотно швидше методу ланцюжків для малих хеш-таблиць, що знаходяться в кеші сучасних процесорів. Кеннет Росс ^[10] показав блочну версію зозулиного хешування (блок містить більше одного ключа), який працює швидше звичайних методів для великих хеш-таблиць в разі високого коефіцієнта завантаження. Швидкість роботи блокової версії зозулиної хеш-таблиці пізніше досліджував Аскітіс ^[11] у порівнянні з іншими схемами хешування.

Див. також

• Колізія геш-функції
• Хеш-функція