Зозулине хешування це схема в програмуванні для вирішення колізій значень хеш функцій в геш таблиці з постійним часом ви

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

Приклад зозулиного хешування. Стрілки показують альтернативне положення ключа. Нове значення, яке вставляється в клітинку 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 % .

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

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

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

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

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

Див. також

Примітки

Pagh, Rodler, 2001, с. 121–133.
Kutzelnigg, 2006, с. 403–406.
Mitzenmacher, 2009.
Dietzfelbinger, Weidling, 2007, с. 47–68.
Kirsch, Mitzenmacher, Wieder, 2010, с. 1543–1561.
Aumüller, Dietzfelbinger, Woelfel, 2014, с. 428–456.
«Micro-Architecture» [ 29 грудня 2019 у Wayback Machine.].
Fan, Kaminsky, Andersen, 2013, с. 36–40.
Zukowski, Heman, Boncz, 2006.
Ross, 2006.
Askitis, 2009, с. 113–122.

Література

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.]

[FOOTNOTEPagh,_Rodler2001121–133-1] Pagh, Rodler, 2001, с. 121–133.

[FOOTNOTEKutzelnigg2006403–406-2] Kutzelnigg, 2006, с. 403–406.

[FOOTNOTEMitzenmacher2009-3] Mitzenmacher, 2009.

[FOOTNOTEDietzfelbinger,_Weidling200747–68-4] Dietzfelbinger, Weidling, 2007, с. 47–68.

[FOOTNOTEKirsch,_Mitzenmacher,_Wieder20101543–1561-5] Kirsch, Mitzenmacher, Wieder, 2010, с. 1543–1561.

[FOOTNOTEAumüller,_Dietzfelbinger,_Woelfel2014428–456-6] Aumüller, Dietzfelbinger, Woelfel, 2014, с. 428–456.

[7] «Micro-Architecture» [ 29 грудня 2019 у Wayback Machine.].

[FOOTNOTEFan,_Kaminsky,_Andersen201336–40-8] Fan, Kaminsky, Andersen, 2013, с. 36–40.

[FOOTNOTEZukowski,_Heman,_Boncz2006-9] Zukowski, Heman, Boncz, 2006.

[FOOTNOTERoss2006-10] Ross, 2006.

[FOOTNOTEAskitis2009113–122-11] Askitis, 2009, с. 113–122.

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

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

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