Кукавичје хеширање
Кукавичје хеширање је шема у програмирању за решавање хеш судара вредности хеш функција у табели, са најгорим случајем константног проналажења времена. Назив потиче од понашања неких врста кукавице, где женка кукавице гура друга јаја или младе из гнезда када се излегну; аналогно, убацивање новог кључа у кукавичјој хеш табели може померити старији кључ на неко друго место у табели.
Историја[уреди | уреди извор]
Кукавичји хешинг су први описали Расмуш Паг (енгл. Rasmus Pagh) и Флемминг Фрих Родлер (енгл. Flemming Friche Rodler) у 2001.[1]
Теорија[уреди | уреди извор]
Основна идеја је да користите две хеш функције, уместо само једне. Ово обезбеђује две могуће локације у хеш табели за сваки кључ. У једном од најчешће коришћених варијанти алгоритма, хеш табела је подељена на две мање табеле једнаке величине и свака хеш функција даје индекс у једној од ове две табеле. Када се убаци нови кључ, користи се похлепни алгоритам. Нови кључ се убацује у једну од своје две могуће локације, " избацивање " , то је, померање, било којег кључа који се већ можда налази на тој локацији. Овај померен кључ се онда убацује у своју алтернативну локацију, поново избацује било који кључ који се тамо налази, докле год се не нађе упражњено место, или ће поступак ући у бесконачну петљу. У другом случају, хеш табела је обновљена на месту помоћу нове хеш функције. Нема потребе да се алоцира нова табела за поновно хеширање. Једноставно можемо проћи кроз табеле бришући и извршити уобичајену процедуру убацивања на свим кључевима који нису нађени на својим намењеним местима у табели .
- Pagh & Rodler, "Cuckoo Hashing"
Претрага захтева преглед од само две локације у хеш табели, који у најгорем случају (погледати Велико О нотацију) временски траје константно. Ово је у супротности са многим другим алгоритмима хеш табела, који не могу да имају стални најгори случај везан за време да уради претрагу. Такође се показало да су уметања успела у очекиваном константном времену, чак разматрајући могућност обнављања табела, докле год се број кључева држи испод половине капацитета хеш табеле, тј, фактор оптерећења је испод 50%. Један метод доказивања овога користи теорију случајних графова: један може формирати неусмерене графове под називом „Кукавичји граф“ који има највишу тачку за сваку локацију хеш табеле и ивицу за сваку хеш вредност, са крајњим тачкама ивице које су две могуће локације вредности. Онда, похлепни алгоритам убацивања за додавање скупа вредности у кукавичкој хеш табели успева, ако и само ако кукавичји граф за овај скуп вредности је графикон са највише једним циклусом у сваким од његових повезаних компоненти; као сваки подграф индуковане највише тачке са више ивица него чворова одговара скупу кључева за које постоје недовољан број слотова у хеш табели. Ово својство је тачно са великом вероватноћом за случајан граф у коме је број ивица мањи од половине броја чворова.[1][тражи се извор]
Пример[уреди | уреди извор]
Задате хеш функције:
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%.[2] Друга генерализација кукавичког хешинга се састоји у коришћењу више од једног кључа по кофи. Користећи само два кључа по кофи дозвољава фактор оптерећења изнад 80%. Други алгоритми који користе вишеструке хеш функције укључују Блумов Филтер. Кукавичји хешинг може да се користи за имплементацију структуре података еквивалентно Блумовом Филтеру. Поједностављена генерализација кукавичког хеширања звани „искривљени - асоцијативног“ кеш се користи у некој процесорској меморији. Студија Зуковског и сарадника[3], показале је да је кукавичји хешинг је много бржи него ланчани хешинг за мале хеш табеле на модернисм процесорима смештеним у кешу. Кенет Рос(енгл. Kenet Ross)[4] је показао да буцкетизед верзије кукавичког хеширања (варијанте које користе кофе које садрже више од једног кључа) бржи од конвенционалних метода који важи исто и за велике хеш табеле, када је искоришћеност простора велика. Перформансе буцкетизед кукавичји хеш табеле је даље истраживао Аскитис[5], са својим перформансама у поређењу против алтернативних Хесинг шема. Истраживање по Миценмахеру представља отворене проблеме везане за Кукавичко хеширање од 2009 године.
Види још[уреди | уреди извор]
- Савршена хеш функција
- Линеарно попуњабање
- Дупло хеширање
- Колизије
- Хеш функција
- Квадратно проверавање
Референце[уреди | уреди извор]
- ^ а б Pagh, Rasmus; Rodler, Flemming Friche (2001). „Cuckoo Hashing”. Algorithms — ESA 2001. Lecture Notes in Computer Science. 2161. стр. 121—133. ISBN 978-3-540-42493-2. doi:10.1007/3-540-44676-1_10.
- ^ Mitzenmacher, Michael (9. 9. 2009). „Some Open Questions Related to Cuckoo Hashing | Proceedings of ESA 2009” (PDF). Приступљено 10. 11. 2010.
- ^ Zukowski, Marcin; Heman, Sandor; Boncz, Peter (јун 2006). „Architecture-Conscious Hashing” (PDF). Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Приступљено 16. 10. 2008.
- ^ Ross, Kenneth (8. 11. 2006). „Efficient Hash Probes on Modern Processors” (PDF). IBM Research Report RC24100. RC24100. Архивирано из оригинала (PDF) 28. 11. 2019. г. Приступљено 16. 10. 2008.
- ^ 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. Архивирано из оригинала (PDF) 16. 2. 2011. г. Приступљено 15. 4. 2014.
Литература[уреди | уреди извор]
- Pagh, Rasmus; Rodler, Flemming Friche (2001). „Cuckoo Hashing”. Algorithms — ESA 2001. Lecture Notes in Computer Science. 2161. стр. 121—133. ISBN 978-3-540-42493-2. doi:10.1007/3-540-44676-1_10.
- 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. Архивирано из оригинала (PDF) 16. 2. 2011. г. Приступљено 15. 4. 2014.
Спољашње везе[уреди | уреди извор]
- A cool and practical alternative to traditional hash tables Архивирано на сајту Wayback Machine (7. април 2019), 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.
- Naor, Moni; Segev, Gil; Wieder, Udi (2008). „History-Independent Cuckoo Hashing”. International Colloquium on Automata, Languages and Programming (ICALP). Reykjavik, Iceland. Приступљено 21. 7. 2008.