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

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

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

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

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

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

- Pagh & Rodler, "Cuckoo Hashing"

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

Пример уреди

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

$h\left(k\right)=k\mod 11$
$h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor \mod 11$

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, улазите у цилус. У последњем реду табеле налазимо исту иницијалну ситуацију, као што је била на почетку.

$h\left(6\right)=6\mod 11=6$
$h'\left(6\right)=\left\lfloor {\frac {6}{11}}\right\rfloor \mod 11=0$

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

Примери уреди

[Cuckoo-1] а ^б 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.

[mitzenmacher2009survey-2] Mitzenmacher, Michael (9. 9. 2009). „Some Open Questions Related to Cuckoo Hashing | Proceedings of ESA 2009” (PDF). Приступљено 10. 11. 2010.

[3] 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.

[4] Ross, Kenneth (8. 11. 2006). „Efficient Hash Probes on Modern Processors” (PDF). IBM Research Report RC24100. RC24100. Приступљено 16. 10. 2008.

[5] 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.

[1]

[2]

[3]

[4]

[5]

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

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

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