мини|Пример Кукавичјег хеширања. Стрелице показују алтернативне локације сваког кључа. Нови елемент ће биту убачен на локацију А померањем А на његову алтернативну локацију, тренутну заузету елементом В, и померањем В на његову алтернативну локацију, која је тренутно слободна. Убацивање новог елемента на локацију елемента Н не би успело јер је Н део циклуса (ѕаједно са W), нови елемент би био опет избачен

Кукавичје хеширање је шема у програмирању за решавање хеш судара вредности хеш функција у табели, са најгорим случајем константног проналажења времена. Назив потиче од понашања неких врста кукавице, где женка кукавице гура друга јаја или младе из гнезда када се излегну; аналогно, убацивање новог кључа у кукавичјој хеш табели може померити старији кључ на неко друго место у табели.

Историја Кукавичји хешинг су први описали Расмуш Паг () и Флемминг Фрих Родлер () у 2001.

Теорија Основна идеја је да користите две хеш функције, уместо само једне. Ово обезбеђује две могуће локације у хеш табели за сваки кључ. У једном од најчешће коришћених варијанти алгоритма, хеш табела је подељена на две мање табеле једнаке величине и свака хеш функција даје индекс у једној од ове две табеле. Када се убаци нови кључ, користи се похлепни алгоритам. Нови кључ се убацује у једну од своје две могуће локације, " избацивање " , то је, померање, било којег кључа који се већ можда налази на тој локацији. Овај померен кључ се онда убацује у своју алтернативну локацију, поново избацује било који кључ који се тамо налази, докле год се не нађе упражњено место, или ће поступак ући у бесконачну петљу. У другом случају, хеш табела је обновљена на месту помоћу нове хеш функције. Нема потребе да се алоцира нова табела за поновно хеширање. Једноставно можемо проћи кроз табеле бришући и извршити уобичајену процедуру убацивања на свим кључевима који нису нађени на својим намењеним местима у табели .

- Pagh & Rodler, "Cuckoo Hashing"

Претрага захтева преглед од само две локације у хеш табели, који у најгорем случају (погледати Велико О нотацију) временски траје константно. Ово је у супротности са многим другим алгоритмима хеш табела, који не могу да имају стални најгори случај везан за време да уради претрагу. Такође се показало да су уметања успела у очекиваном константном времену, чак разматрајући могућност обнављања табела, докле год се број кључева држи испод половине капацитета хеш табеле, тј, фактор оптерећења је испод 50%. Један метод доказивања овога користи теорију случајних графова: један може формирати неусмерене графове под називом „Кукавичји граф“ који има највишу тачку за сваку локацију хеш табеле и ивицу за сваку хеш вредност, са крајњим тачкама ивице које су две могуће локације вредности. Онда, похлепни алгоритам убацивања за додавање скупа вредности у кукавичкој хеш табели успева, ако и само ако кукавичји граф за овај скуп вредности је графикон са највише једним циклусом у сваким од његових повезаних компоненти; као сваки подграф индуковане највише тачке са више ивица него чворова одговара скупу кључева за које постоје недовољан број слотова у хеш табели. Ово својство је тачно са великом вероватноћом за случајан граф у коме је број ивица мањи од половине броја чворова.

Пример Задате хеш функције:

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. табела за h(k) 20 50 53 75 100 67 105 3 36 39 0 1 100 67 67 67 67 100 2 3 3 3 36 4 5 6 50 50 50 50 50 105 105 105 50 7 8 9 20 20 20 20 20 20 53 53 53 75 10

2. табела за h'(k) 20 50 53 75 100 67 105 3 36 39 0 3 1 20 20 20 20 2 3 36 39 4 53 53 53 53 50 50 50 53 5 6 75 75 75 75 75 75 67 7 8 9 100 100 100 100 105 10

Циклус Уколико желите да убаците елемент 6, улазите у цилус. У последњем реду табеле налазимо исту иницијалну ситуацију, као што је била на почетку.

подразумевани кључ табела 1 табела 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

Генерализација и примене Генерализације о кукавичком хеширању које користе више од две алтернативне хеш функције може се очекивати да искористи ефективно већи део простора хеш табеле док жртвује неку брзину претраге и уметања. Коришћењем само три хеш функције повећава оптерећење на 91%. Друга генерализација кукавичког хешинга се састоји у коришћењу више од једног кључа по кофи. Користећи само два кључа по кофи дозвољава фактор оптерећења изнад 80%. Други алгоритми који користе вишеструке хеш функције укључују Блумов Филтер. Кукавичји хешинг може да се користи за имплементацију структуре података еквивалентно Блумовом Филтеру. Поједностављена генерализација кукавичког хеширања звани „искривљени - асоцијативног“ кеш се користи у некој процесорској меморији. Студија Зуковског и сарадника, показале је да је кукавичји хешинг је много бржи него ланчани хешинг за мале хеш табеле на модернисм процесорима смештеним у кешу. Кенет Рос() је показао да буцкетизед верзије кукавичког хеширања (варијанте које користе кофе које садрже више од једног кључа) бржи од конвенционалних метода који важи исто и за велике хеш табеле, када је искоришћеност простора велика. Перформансе буцкетизед кукавичји хеш табеле је даље истраживао Аскитис, са својим перформансама у поређењу против алтернативних Хесинг шема. Истраживање по Миценмахеру представља отворене проблеме везане за Кукавичко хеширање од 2009 године.

Види још Савршена хеш функција Линеарно попуњабање Дупло хеширање Колизије Хеш функција Квадратно проверавање

Референце

Литература

Спољашње везе 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.

Примери 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

Категорија:Алгоритми претраживања Категорија:Хеширање