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

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

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

Історія

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

Операції

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

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

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

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

Теорія

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

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

Приклад

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

$h\left(k\right)=k\mod 11$ $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, ви отримаєте нескінченний цикл. В останньому рядку таблиці ми знаходимо ту ж початкову ситуацію, що і на початку.

$h\left(6\right)=6\mod 11=6$ $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 % . Інше узагальнення зозулиного хешування, зване блоковим зозулиним хешуванням, містить більше одного ключа на комірку. Використання двох ключів на комірку дозволяє підвищити завантаження вище 80 % .

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

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

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

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

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

Див. також

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

Література

• Martin Dietzfelbinger, Christoph Weidling.  // Theoret. Comput. Sci.. — 2007. — Вип. 1-2. — С. 47–68.
• Adam Kirsch, Michael D. Mitzenmacher, Udi Wieder.  // SIAM J. Comput.. — 2010. — Вип. 4. — С. 1543–1561.
• Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel.  // Algorithmica. — 2014. — Вип. 3. — С. 428–456.
• Bin Fan, Michael Kaminsky, David Andersen. Архівована копія // ;login:. — USENIX, 2013. — Вип. 4. — С. 36–40. Архівовано з джерела 1 серпня 2014. Процитовано 12 червня 2014.
• Marcin Zukowski, Sandor Heman, Peter Boncz. Архівована копія. — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006. Архівовано з джерела 15 травня 2019. Процитовано 2008-10-16.
• Kenneth Ross. Архівована копія. — IBM Research Report RC24100, 2006. Архівовано з джерела 28 листопада 2019. Процитовано 2008-10-16.

Посилання

• A cool and practical alternative to traditional hash [Архівовано 7 квітня 2019 у Wayback Machine.] tables, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing for Undergraduates, 2006 [Архівовано 15 червня 2011 у Wayback Machine.], R. Pagh, 2006.
• Cuckoo Hashing, Theory and Practice [Архівовано 28 листопада 2019 у Wayback Machine.] (Part 1, Part 2 [Архівовано 28 листопада 2019 у Wayback Machine.] and Part 3 [Архівовано 28 листопада 2019 у Wayback Machine.]), Michael Mitzenmacher, 2007.
• Algorithmic Improvements for Fast Concurrent Cuckoo Hashing [Архівовано 21 березня 2020 у Wayback Machine.], X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.

Приклади

• Concurrent high-performance Cuckoo hashtable written in C ++ [Архівовано 2 квітня 2019 у Wayback Machine.]
• Cuckoo hash map written in C ++ [Архівовано 28 листопада 2019 у Wayback Machine.]
• Static cuckoo hashtable generator for C / C ++ [Архівовано 18 грудня 2019 у Wayback Machine.]
• Cuckoo hash table written in Haskell
• Cuckoo hashing for Go [Архівовано 16 вересня 2020 у Wayback Machine.]