Зозулине хешування
Зозулине хешування — це схема в програмуванні для вирішення колізій значень хеш-функцій в геш-таблиці з постійним часом вибірки в гіршому випадку. Назва походить від поведінки деяких видів зозуль, коли пташеня зозулі виштовхує яйця або інших пташенят з гнізда відразу після того, як вилупиться. Аналогічне відбувається в зозулиному хеші, коли вставка нового ключа в таблицю може виштовхнути старий ключ в інше місце в таблиці.
Історія
Зозулине хешування було вперше описане Расмусом Пажом і Флеммінгом Фрішем Родлером у 2001.
Операції
Зозулине хешування є видом відкритої адресації, де кожна непуста комірка геш-таблиці містить ключ або пару ключ-значення. Хеш-функція використовується для визначення місця кожного ключа, його наявності в таблиці (або значення, асоційованого з ним) і може бути знайдене за допомогою перевірки цієї комірки в таблиці. Однак, відкрита адресація потерпає від колізій, які трапляються, коли більше одного ключа потрапляють в одну клітинку. Основна ідея зозулиного хешування полягає у розв'язанні колізій за допомогою використання двох хеш-функцій замість однієї. Це забезпечує два можливі положення у хеш-таблиці для кожного ключа. У одному з звичайних варіантів алгоритму хеш-таблиця розбивається на дві менші таблиці меншого розміру і кожна хеш-функція дає індекс у одну з цих двох таблиць. Можна забезпечити також для обох хеш-функцій індексування всередині однієї таблиці.
Вибірка вимагає перегляду всього двох місць в хеш-таблиці, що вимагає постійного часу в гіршому випадку (див. «O» велике і «o» мале). Це контрастує з багатьма іншими алгоритмами хеш-таблиць, які не забезпечують постійний час вибірки в гіршому випадку. Видалення також може бути здійснено очищенням комірки, що містить ключ, за постійний час в гіршому випадку, що здійснюється простіше, ніж в інших схемах, таких як лінійне зондування.
Коли вставляється новий ключ і одна з двох комірок порожня, ключ може бути поміщений в цю комірку. У разі ж, коли обидві комірки зайняті, необхідно перемістити інші ключі в інші місця (або, навпаки, на їх колишні місця), щоб звільнити місце для нового ключа. Використовується жадібний алгоритм — ключ поміщається в одну з можливих позицій, «виштовхуючи» будь-який ключ, який був в цій позиції. Виштовхнутий ключ потім поміщається в його альтернативну позицію, знову виштовхуючи будь-який ключ, який може там опинитися. Процес триває, поки не знайдеться порожня позиція. Проте, можливий випадок, коли процес вставки закінчується невдачею, потрапляючи в нескінченний цикл або коли утворюється надто довгий ланцюжок (довше, ніж заздалегідь заданий поріг, залежить логарифмічно від довжини таблиці). В цьому випадку хеш-таблиця перебудовується на місці з новими хеш-функціями:Шаблон:Цитата
Теорія
Очікуваний час вставки постійний Шаблон:Sfn, навіть якщо брати до уваги можливу необхідність перебудови таблиці, поки число ключів менше половини ємності хеш-таблиці, тобто коефіцієнт навантаження менше 50 %.
Щоб забезпечити це, використовується теорія випадкових графів — можна утворити неорієнтований граф, званий «зозулиним графом», в якому вершинами є комірки хеш-таблиці, а ребра для кожного хешованого з'єднують два можливих положення (комірки хеш-таблиці). Тоді жадібний алгоритм вставки множини значень в зозулину хеш-таблицю успішно завершується тоді і тільки тоді, коли зозулин граф для цієї множини значень є псевдолісом — графом максимум з одним циклом в кожній компоненті зв'язності. Будь-який породжений вершинами підграф з числом ребер, більшим числа вершин, відповідає безлічі ключів, для яких число слотів в хеш-таблиці недостатнє. Якщо хеш-функція вибирається випадково, зозулиний граф буде випадковим графом в моделі Ердьоша — Ренї [en]. З високим ступенем ймовірності для випадкового графу, в якому відношення числа ребер до числа вершин обмежена зверху 1/2, граф є псевдолісом і алгоритм зозулиного хешування успішно розподіляє всі ключі. Більше того, та ж теорія доводить, що очікуваний розмір компонент зв'язності зозулиного графу малий, що забезпечує постійний очікуваний час вставки Шаблон:Sfn.
Приклад
Нехай дано такі дві хеш-функції:
| 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 |
Варіації
Вивчалися деякі варіації зозулиного хешування, в основному з метою поліпшити використання простору шляхом збільшення коефіцієнта завантаження. У цих варіантах може досягатися поріг навантаження більше 50 %. Деякі з цих методів можуть бути використані для істотного зменшення числа необхідних перебудов структури даних.
Від узагальнення зозулиного хешування, що використовує понад дві хеш-функцій, можна очікувати кращого використання хеш-таблиці, жертвуючи деякою швидкістю вибірки і вставки. Використання трьох хеш-функцій підвищує коефіцієнт завантаження до 91 % Шаблон:Sfn. Інше узагальнення зозулиного хешування, зване блоковим зозулиним хешуванням, містить більше одного ключа на комірку. Використання двох ключів на комірку дозволяє підвищити завантаження вище 80 % Шаблон:Sfn.
Ще один варіант — зозулине хешування з запасом. «Запас» — це масив ключів постійної довжини, який використовується для зберігання ключів, які не можуть бути успішно вставлені в головну хеш-таблицю. Ця модифікація зменшує число невдач до назад-поліноміальної функції зі ступенем, яка може бути довільно великою, шляхом збільшення розміру запасу. Однак великий запас означає більш повільний пошук ключа, якого немає в основній таблиці, або якщо він знаходиться в запасі. Запас можна використовувати в комбінації з більш ніж двома хеш-функціями або з блоковим зозулиним хешуванням для отримання як високого ступеня завантаження, так і малого числа невдач вставки Шаблон:Sfn. Аналіз зозулиного хешування з запасом поширився і на практичні хеш-функції, не тільки випадкові моделі хеш-функцій, які використовуються в теоретичному аналізі хешування Шаблон:Sfn.
Деякі дослідники пропонують використовувати в деяких кешах процесора спрощене узагальнення зозулиного хешування, званого несиметричним асоціативним кешем[1].
Порівняння з аналогічними структурами
Є інші алгоритми, які використовують кілька хеш-функцій, зокрема фільтр Блума, ефективна по пам'яті структура даних для нечітких множин. Альтернативна структура даних для задач з тими ж нечіткими множинами, заснована на зозулиному хешуванні, звана зозулиним фільтром, використовує меншу кількість пам'яті і, на відміну від класичних фільтрів Блума, дозволяє не тільки вставку і перевірку існування але і видалення елемента. Однак теоретичний аналіз цих методів проведено значно слабше, ніж аналіз фільтрів Блума Шаблон:Sfn.
Дослідження, проведені Жуковським, Хеманом і Бонзом Шаблон:Sfn, показали, що зозулине хешування істотно швидше методу ланцюжків для малих хеш-таблиць, що знаходяться в кеші сучасних процесорів. Кеннет Росс Шаблон:Sfn показав блочну версію зозулиного хешування (блок містить більше одного ключа), який працює швидше звичайних методів для великих хеш-таблиць в разі високого коефіцієнта завантаження. Швидкість роботи блокової версії зозулиної хеш-таблиці пізніше досліджував Аскітіс Шаблон:Sfn у порівнянні з іншими схемами хешування.
Див. також
Примітки
Література
Посилання
- A cool and practical alternative to traditional hash Шаблон:Webarchive tables, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
- Cuckoo Hashing for Undergraduates, 2006 Шаблон:Webarchive, R. Pagh, 2006.
- Cuckoo Hashing, Theory and Practice Шаблон:Webarchive (Part 1, Part 2 Шаблон:Webarchive and Part 3 Шаблон:Webarchive), Michael Mitzenmacher, 2007.
- Algorithmic Improvements for Fast Concurrent Cuckoo Hashing Шаблон:Webarchive, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.