Користувач:KiranKaravaev/Зозулине хешування

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

варіації

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

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

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

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

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

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

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

Обзор Мутцемахера[3] представляє відкриті проблеми, связанные з кукушкиным хешированием.

Див. також

• Совершенная функция хеширования
• Колізія хеш-функції
• Хеширование

Примітки

пврпвр

Література

• Rasmus Pagh, Flemming Friche Rodler. [10.1007/3-540-44676-1_10 Cuckoo Hashing] // {{{Заголовок}}}. — 2001. — С. 121–133. — (Lecture Notes in Computer Science) — ISBN 978-3-540-42493-2.
• Reinhard Kutzelnigg. {{{Заголовок}}}. — 2006. — С. 403–406. — (Discrete Mathematics and Theoretical Computer Science)
• M. Mitzenmacher. {{{Заголовок}}}. — 2009.
• 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. [1] // ;login:. — USENIX, 2013. — Вип. 4. — С. 36–40. Процитовано 12 June 2014.
• Marcin Zukowski, Sandor Heman, Peter Boncz. [2]. — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006. Процитовано 2008-10-16.
• Kenneth Ross. [3]. — IBM Research Report RC24100, 2006. Процитовано 2008-10-16.
• Nikolas Askitis. {{{Заголовок}}}. — Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009). — 2009. — С. 113–122. — ISBN 978-1-920682-72-9.

Посилання

• A cool and practical alternative to traditional hash tables , U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
• Cuckoo Hashing, Theory and Practice (Part 1, Part 2 and Part 3 ), Michael Mitzenmacher, 2007.
• Moni Naor, Gil Segev, Udi Wieder. {{{Заголовок}}}. — Reykjavik, Iceland, 2008.
• Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.

Приклади

• Concurrent high-performance Cuckoo hashtable written in C ++
• Cuckoo hash map written in C ++
• Static cuckoo hashtable generator for C / C ++
• Cuckoo hash table written in Haskell
• Cuckoo hashing for Go

[[Категорія:Хешування]] [[Категорія:Алгоритми пошуку]]