Користувач:KiranKaravaev/Зозулине хешування
Зозулине хешування - це схема в програмуванні для вирішення колізій значень хеш-функцій в геш-таблиці з постійним часом вибірки в гіршому випадку. Назва походить від поведінки деяких видів зозуль, коли пташеня зозулі виштовхує яйця або інших пташенят з гнізда відразу після того, як вилупиться. Аналогічне відбувається в зозулином хеші, коли вставка нового ключа в таблицю може виштовхнути старий ключ в інше місце в таблиці.
Історія
ред.Зозулине хешування було вперше описане Расмусом Пажом і Флеммингом Фришем Родлером у 2001.
Операції
ред.Зозулине хешування є видом відкритої адресації, де кожна непуста коміркагеш-таблиці містить ключ або пару ключ–значення. Хеш-функція використовується для визначення місця для кожного ключа, і його наявності в таблиці (або значення, асоційоване з ним) може бути знайдене за допомогою перевірки цієї комірки в таблиці. Однак, відкрита адресація потерпає від колізій, які трапляються, коли більше одного ключа потрапляють в одну клітинку. Основная ідея зозулиного хешування є в вірішенні колізій за допомогою використання двох хеш-функцій вместо одної. Це забезпечує два #можливий положення у хеш-таблиці для кожногоключа. У однім з #звичайний варіантів алгоритму хеш-таблиця разбивается на дві меньшие таблиці меньшего розміру #і кожна хеш-функція дає індекс у одну з цих двох таблиць. Можна забезпечити також для обох хеш-функцій индексирование всередині одної таблиці.
Вибірка вимагає перегляду всього двох місць в хеш-таблиці, що вимагає постійного часу в гіршому випадку (див. «O» велике і «o» мале ). Це контрастує з багатьма іншими алгоритмами хеш-таблиць, які не забезпечують постійний час вибірки в гіршому випадку. Видалення також може бути здійснено очищенням комірки, що містить ключ за постійний час в гіршому випадку, що здійснюється простіше, ніж в інших схемах, таких як лінійне зондування.
Когда вставляется новый ключ и одна из двух ячеек пуста, ключ может быть помещён в эту ячейку. В случае же, когда обе ячейки заняты, необходимо переместить другие ключи в другие места (или, наоборот, на их прежние места), чтобы освободить место для нового ключа. Используется жадный алгоритм — ключ помещается в одну из возможных позиций, «выталкивая» любой ключ, который был в этой позиции. Вытолкнутый ключ затем помещается в его альтернативную позицию, снова выталкивая любой ключ, который мог там оказаться. Процесс продолжается, пока не найдётся пустая позиция. Возможен, однако, случай, когда процесс вставки заканчивается неудачей, попадая в бесконечный цикл или когда образуется слишком длинная цепочка (длиннее, чем заранее заданный порог, зависящий логарифмически от длины таблицы). В этом случае хеш-таблица перестраивается на месте[en] с новыми хеш-функциями:
Нет необходимости размещения новой таблицы для повторного хеширования — мы можем просто просматривать таблицу для удаления и повторной вставки всех ключей, которые находятся не в той позиции, в которой должны были бы стоять.[1] | ||
— Pagh & Rodler, «Cuckoo Hashing» |
Теорія
ред.Очікуваний час вставки постійний [1], навіть якщо брати до уваги можливу необхідність перебудови таблиці, поки число ключів менше половини ємності хеш-таблиці, тобто коефіцієнт навантаження менше 50%.
Щоб забезпечити це, використовується теорія випадкових графів - можна утворити неорієнтований граф, званий «зозулиним графом», в якому вершинами є комірки хеш-таблиці, а ребра для кожного хешируваного з'єднують два можливих положення (комірки хеш-таблиці). Тоді жадібний алгоритм вставки множини значень в зозулину хеш-таблицю успішно завершується тоді і тільки тоді, коли зозулин граф для цієї множини значень є псевдолісом, графом максимум з одним циклом в кожній компоненті зв'язності . Будь-який породжений вершинами підграф з числом ребер, великим числа вершин, відповідає безлічі ключів, для яких число слотів в хеш-таблиці недостатньо. Якщо хеш-функція вибирається випадково, кукушкин граф буде випадковим графом в модели Эрдёша – Реньи [en] . З високим ступенем ймовірності для випадкового графа, в якому відношення числа ребер до числа вершин обмежена зверху 1/2, граф є псевдолесом і алгоритм зозулиного хеширования має успішно все ключі. Більш того, та ж теорія доводить, що очікуваний розмір компонент зв'язності зозулиного графа малий, що забезпечує постійне очікуваний час вставки [2] .
Приклад
ред.Нехай дано такі дві хеш-функції:
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, ви отримаєте нескінченний цикл. В останньому рядку таблиці ми знаходимо ту ж початкову ситуацію, що і на початку.
ключ | 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% [3] . Інша узагальнення зозулиного хеширования, зване блоковим зозулиним хешированием, містить більше одного ключа на осередок. Використання двох ключів на осередок дозволяє підвищити завантаження вище 80% [4] .
Ще один вивчає варіант - зозулине хешування з запасом. «Запас» - це масив ключів постійної довжини, який використовується для зберігання ключів, які не можуть бути успішно вставлені в головну хеш-таблицю. Ця модифікація зменшує число невдач до назад-поліноміальної функції зі ступенем, яка може бути довільно великий, шляхом збільшення розміру запасу. Однак великий запас означає більш повільний пошук ключа, якого немає в основний Талице, або якщо він знаходиться в запасі. Запас можна використовувати в комбінації з більш ніж двома хеш-функціями або з блоковим зозулиним хешированием для отримання як високого ступеня завантаження, так і малого числа невдач вставки [5] . Аналіз зозулиного хеширования з запасом поширився і на практичні хеш-функції, не тільки випадкові моделі хеш-функцій, які використовуються в теоретичному аналізі хеширования [6] .
Деякі дослідники пропонують використовувати в деяких кешах процесора спрощене узагальнення зозулиного хеширования, званого несиметричним асоціативним кешем . [7]
Порівняння з аналогічними структурами
ред.Є інші алгоритми, які використовують кілька хеш-функцій, зокрема фільтр Блума, ефективна по пам'яті структура даних для нечітких множин. Альтернативна структура даних для задач з тими ж нечіткими множинами, заснована на Кукушкін хешуванні, звана зозулиним фільтром, використовує навіть меншу пам'ять і (на відміну від класичних фільтрів Блума) дозволяє видалення елемента, не тільки вставку і перевірку існування. Однак теоретичний аналіз цих методів проведено значно слабше, ніж аналіз фільтрів Блума [8] .
Дослідження, проведені Жуковським, Хеманом і бонз [9], показали, що зозулине хешування істотно швидше методу ланцюжків для малих хеш-таблиць, що знаходяться в кеші сучасних процесорів. Кеннет Росс [10] показав блочну версію зозулиного хеширования (блок містить більше одного ключа), який працює швидше звичайних методів для великих хеш-таблиць в разі високого коефіцієнта завантаження. Швидкість роботи блокової версії зозулиній хеш-таблиці пізніше досліджував Аскітіс [11] у порівнянні з іншими схемами кешування.
Обзор Мутцемахера[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
[[Категорія:Хешування]] [[Категорія:Алгоритми пошуку]]
- ↑ а б 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".
- ↑ Fan, Kaminsky, Andersen, 2013, с. 36–40.
- ↑ Zukowski, Heman, Boncz, 2006.
- ↑ Ross, 2006.
- ↑ Askitis, 2009, с. 113–122.