Кукушкове хешування: Гарантований постійний час пошуку

Як Працює Хешування Кукушки

Хешування кукушки базується на двох незалежних хеш-функціях, які зазвичай називають h1 та h2, і (у класичній варіації з двома таблицями) двома масивами однакового розміру. Кожен ключ k має рівно два законні місця розташування: позицію h1(k) в першій таблиці та позицію h2(k) у другій таблиці. Для пошуку ключа просто обчислюються обидва хеш-значення та перевіряються обидва слоти; якщо ключ не знайдено ні в одному з них, то він точно не міститься в таблиці. Це робить пошук передбачуваним: немає ланцюгів для проходження, жодної послідовності зондування, лише два прямих доступи до масивів. Вставлення ключа k є найбільш цікавою частиною схеми. Щоб вставити ключ k, спочатку перевірте його слот у першій таблиці. Якщо цей слот порожній, вставте k туди і все. Якщо слот зайнятий іншим ключем j, k виганяє j, займаючи його місце, і тепер j потрібно повторно вставити на своєму альтернативному слоті, у другій таблиці. Якщо й там слот також зайнятий, ключ, що знаходиться там, виганяється в свою чергу, і процес повторюється, перескакуючи між двома таблицями. Кожен вигнаний ключ завжди має чітко визначене альтернативне місце розташування, оскільки положення кожного ключа фіксуються в момент хешування, незалежно від того, скільки разів він виганяється та повторно вставляється. Видалення також просте: знайдіть ключ в одному з його двох слотів і видаліть його безпосередньо, не потребуючи переструктурування ланцюгів або зміщення послідовностей зондування. Елегантність дизайну полягає в тому, що двохеш-функціональна, двослотова інваріант зберігається після кожної операції, тому гарантія того, що пошук завжди потребує лише перевірки двох місць, ніколи не порушується, незалежно від того, як внутрішньо таблиця була переміщена попередніми вставками.

Потовидільна схема: Койкова Нижня

Процес виселення є серцем коїхованової хешування, і поводиться так само, як і у його птаха-названика. Койка відкладає яйце в гніздо іншої птиці, і коли воно вилуплюється, койкова дитинка виштовхує оригінальні яйця, щоб претендувати на всю батьківську турботу для себе. У хеш-таблиці вставлення нового ключа може виштовхнути існуючий ключ зі свого слоту, змушуючи цей витіснений ключ переміщатися у свій інший гніздо, яке само по собі може бути зайнятим, виштовхуючи ще один ключ, і так далі. У практиці більшість вставлень стабілізуються після одного або двох виселень, особливо коли таблиця не занадто переповнена. Уявіть собі вставлення кількох ключів у невелику таблицю: перші кілька з них плавно входять у порожні слоти без жодної драми, але врешті-решт новий ключ приземляється на зайнятий слот, штовхає існуючий ключ звідти, цей існуючий знаходить свій альтернативний слот зайнятим, штовхає ще один ключ, і ланцюг триває до тих пір, поки якийсь ключ нарешті не приземлиться у порожній слот, і ланцюгова реакція завершується. Більшість часу цей ланцюг короткий і швидко вирішується, даючи вставці очікуваний час виконання, близький до константної, навіть якщо окрема вставка іноді може торкнутися багатьох ключів. Небезпека полягає в тому, що ланцюг виселень може рідко зустрічатися у циклі: ключ A виштовхує ключ B, який виштовхує ключ C, який врешті-решт виштовхує ключ A знову, відтворюючи точну ситуацію, яка почала ланцюг. Це називається циклом, і це означає, що поточна пара хеш-функцій просто не може вмістити поточний набір ключів у два фіксовані слоти один за одним. Реалізації захищаються від цього, обмежуючи кількість дозволених виселень для однієї вставки, наприклад, до деякої кількості, що помножена на логарифм розміру таблиці.

Розбиття Циклів: Перерозподіл Таблиці

Коли ланцюг виселення від одного вставлення перевищує дозволений поріг, або виявляється фактичний цикл, cuckoo хешування не просто зазнає невдачі; воно перебудовує таблицю. Стандартним рішенням є вибір нової пари хеш-функцій, h1 та h2, і перерозподіл усіх ключових елементів, що зберігаються в таблиці, а також ключа, який спричинив невдачу, у нові слоти, визначені новими функціями. Оскільки нові хеш-функції по-різному розсіюють ключі, конкретна конфігурація, яка викликала цикл, майже напевно не повториться негайно, і вставлення відбувається нормально після цього. Цей процес перерозподілу іноді поєднується з розширенням таблиці, якщо завантаження стало високим, що зменшує частоту довгих ланцюгів виселення та ймовірність виникнення майбутніх циклів. Перебудова всієї таблиці звучить дорого, і окрема перебудова потребує часу пропорційного кількості збережених ключів, але ключовий теоретичний результат, що лежить в основі cuckoo хешування, полягає в тому, що при вдалому виборі достатньо випадкових хеш-функцій та завантаженні, яке комфортно нижче критичної межі, ймовірність необхідності перебудови на будь-якому вставленні є такою малою, що середній витратний час на вставлення залишається постійним протягом тривалого ряду операцій. У деяких практичних реалізаціях також використовується невелику допоміжна структура під назвою ‘stash’, яка утримує кілька ключів, які не могли бути розміщені після ланцюга виселення, уникаючи повної перебудови для випадкових невдач. Незалежно від того, чи здійснюється це шляхом перебудови, розширення таблиці або використання ‘stash’, основна стратегія однакова: розглядати застряглий ланцюг виселення як рідкісну структурну несправність поточних хеш-функцій, а не як недолік алгоритму, і виправити це, змінюючи функції, а не послаблюючи гарантію двох слотів, яка забезпечує швидкість пошуків.

Завантаження: Чому Cuckoo Hashing потребує простору для дихання

Завантаження (коефіцієнт заповнення) хеш-таблиці – це частка слотів, які зараз зайняті, і вона значно впливає на поведінку cuckoo hashing. Коли таблиця майже порожня, вставки майже завжди потрапляють безпосередньо або викликають лише дуже короткий ланцюг виселення, оскільки є хороша ймовірність того, що альтернативний слот ключа вільний. Зі збільшенням коефіцієнта заповнення шанси на те, що обидва кандидати слоти ключа вже зайняті, значно зростають, і ланцюги виселення стають довші та частіше потрапляють у цикл. Теоретичний аналіз класичної схеми з двох таблиць і двох хеш-функцій показує, що схема добре працює, якщо коефіцієнт заповнення залишається нижчим приблизно ніж половина, тобто таблиця не повинна містити більше ніж приблизно 50% від загальної кількості слотів, об'єднаних з обох таблиць. Якщо вийти далеко за цей поріг, ймовірність утворення циклу швидко зростає, що призводить до частіших та дорогих рехешів, які в практиці руйнують гарантований постійний час пошуку, хоча пошуки теоретично залишаються швидкими, коли таблиця стабілізується. Цей ліміт у 50% значно більш консервативний, ніж схеми, такі як лінійна пробивка, які часто можуть витримувати навантаження до 70 або 80%, перш ніж продуктивність погіршиться, або окреме ланцюгове хешування, яке майже не погіршується, оскільки ланцюги просто стають довші. Цей компроміс свідомий: cuckoo hashing витрачає додатковий простір, приблизно вдвічі більше, ніж максимально заповнена структура, щоб забезпечити жорсткий ліміт на вартість пошуку, а не використовує його.

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

Порівняння Cuckoo Hashing з chaining та лінійним пошуком

Два класичні альтернативи cuckoo hashing – це separate chaining та open addressing схеми, такі як linear probing. Порівняння цих підходів дозволяє зрозуміти, що саме ви отримуєте від cuckoo hashing. У separate chaining кожен слот містить зв’язний список (або подібну структуру) для всіх ключів, які туди хешуються; пошук означає обхід цього списку, тому в найгіршому випадку, якщо багато ключів зіштовхуються в один слот, пошук може зайняти час пропорційний кількості ключів у таблиці. Середня продуктивність хороша з добре розподіленим хеш-функцією, але немає гарантії проти поганого випадку або ворожого введення, що призведе до довгого списку. Linear probing зберігає ключі безпосередньо в масиві та, при зіткненні, сканує вперед по слотах до тих пір, поки не знайде порожній слот; пошук також повинен слідувати цьому самому послідовності пробивання, і коли таблиця заповнюється, послідовності пробивання можуть ставати довгими, що погіршує продуктивність, особливо через явище первинного кластерування, де збільшуються та зливаються групи зайнятих слотів. Cuckoo hashing обходить обидві ці проблеми, фіксуючи заздалегідь точно дві можливі позиції, які може займати ключ. Пошук ніколи не займає більше двох пробивань, незалежно від того, наскільки повністю заповнена таблиця (до її безпечного коефіцієнту завантаження) або як випадково виявляються значення хешів. Це справжня гарантія найгіршого випадку, а не лише середнього значення, що має величезне значення в реальному часі, апаратних реалізаціях та мережевих додатках, таких як таблиці маршрутизації, де одне повільне виконання пошуку може порушити вимоги щодо затримки. Ціна, яку платиться – це нижчий корисний коефіцієнт завантаження, складніша логіка вставки, що включає потенційні ланцюжки виселення та перехешування, і потреба у високоякісних незалежних хеш-функціях для підтримки низького циклічного шансу.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Cuckoo Hashing: Guaranteed Constant-Time Lookups і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.