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

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Пример Кукавичјег хеширања. Стрелице показују алтернативне локације сваког кључа. Нови елемент ће биту убачен на локацију А померањем А на његову алтернативну локацију, тренутну заузету елементом В, и померањем В на његову алтернативну локацију, која је тренутно слободна. Убацивање новог елемента на локацију елемента Н не би успело јер је Н део циклуса (ѕаједно са 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. 

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

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

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