Кукавичје хеширање

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

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

Историја[уреди]

Кукавичји хешинг су први описали Расмуш Паг (енгл. Rasmus Pagh) и Флемминг Фрих Родлер (енгл. Flemming Friche Rodler) у 2001.[1]

Теорија[уреди]

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

- Pagh & Rodler, "Cuckoo Hashing"

Претрага захтева преглед од само две локације у хеш табели, који у најгорем случају (погледати Велико О нотацију) временски траје константно. Ово је у супротности са многим другим алгоритмима хеш табела, који не могу да имају стални најгори случај везан за време да уради претрагу. Такође се показало да су уметања успела у очекиваном константном времену, чак разматрајући могућност обнављања табела, докле год се број кључева држи испод половине капацитета хеш табеле, тј, фактор оптерећења је испод 50%. Један метод доказивања овога користи теорију случајних графова: један може формирати неусмерене графове под називом „Кукавичји граф“ који има највишу тачку за сваку локацију хеш табеле и ивицу за сваку хеш вредност, са крајњим тачкама ивице које су две могуће локације вредности. Онда, похлепни алгоритам убацивања за додавање скупа вредности у кукавичкој хеш табели успева, ако и само ако кукавичји граф за овај скуп вредности је графикон са највише једним циклусом у сваким од његових повезаних компоненти; као сваки подграф индуковане највише тачке са више ивица него чворова одговара скупу кључева за које постоје недовољан број слотова у хеш табели. Ово својство је тачно са великом вероватноћом за случајан граф у коме је број ивица мањи од половине броја чворова.[1] [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. табела за 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%.[3] Друга генерализација кукавичког хешинга се састоји у коришћењу више од једног кључа по кофи. Користећи само два кључа по кофи дозвољава фактор оптерећења изнад 80%. Други алгоритми који користе вишеструке хеш функције укључују Блумов Филтер. Кукавичји хешинг може да се користи за имплементацију структуре података еквивалентно Блумовом Филтеру. Поједностављена генерализација кукавичког хеширања звани „искривљени - асоцијативног“ кеш се користи у некој процесорској меморији. Студија Зуковског и сарадника[4], показале је да је кукавичји хешинг је много бржи него ланчани хешинг за мале хеш табеле на модернисм процесорима смештеним у кешу. Кенет Рос(енгл. Kenet Ross)[5] је показао да буцкетизед верзије кукавичког хеширања (варијанте које користе кофе које садрже више од једног кључа) бржи од конвенционалних метода који важи исто и за велике хеш табеле, када је искоришћеност простора велика. Перформансе буцкетизед кукавичји хеш табеле је даље истраживао Аскитис[6], са својим перформансама у поређењу против алтернативних Хесинг шема. Истраживање по Миценмахеру представља отворене проблеме везане за Кукавичко хеширање од 2009 године.

Види још[уреди]

Референце[уреди]

  1. 1,0 1,1 doi:10.1007/3-540-44676-1_10
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  2. Kutzelnigg, Reinhard (2006). „Fourth Colloquium on Mathematics and Computer Science”. Discrete Mathematics and Theoretical Computer Science. стр. 403—406<!-  |contribution= игнорисан (помоћ)
  3. Mitzenmacher, Michael (9. 9. 2009). „Some Open Questions Related to Cuckoo Hashing | Proceedings of ESA 2009” (PDF). Приступљено 10. 11. 2010. 
  4. Zukowski, Marcin (јун 2006). „Architecture-Conscious Hashing” (PDF). Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Приступљено 16. 10. 2008.  Непознати параметар |coauthors= игнорисан [|author= се препоручује] (помоћ)
  5. Ross, Kenneth (8. 11. 2006). „Efficient Hash Probes on Modern Processors” (PDF). IBM Research Report RC24100. RC24100. Приступљено 16. 10. 2008. 
  6. Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys (PDF). Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009). 91. стр. 113—122. ISBN 978-1-920682-72-9. 

Литература[уреди]

Спољашње везе[уреди]

Примери[уреди]