Kukavičje heširanje

Primer Kukavičjeg heširanja. Strelice pokazuju alternativne lokacije svakog ključa. Novi element će bitu ubačen na lokaciju A pomeranjem A na njegovu alternativnu lokaciju, trenutnu zauzetu elementom V, i pomeranjem V na njegovu alternativnu lokaciju, koja je trenutno slobodna. Ubacivanje novog elementa na lokaciju elementa N ne bi uspelo jer je N deo ciklusa (ѕajedno sa W), novi element bi bio opet izbačen

Kukavičje heširanje je šema u programiranju za rešavanje heš sudara vrednosti heš funkcija u tabeli, sa najgorim slučajem konstantnog pronalaženja vremena. Naziv potiče od ponašanja nekih vrsta kukavice, gde ženka kukavice gura druga jaja ili mlade iz gnezda kada se izlegnu; analogno, ubacivanje novog ključa u kukavičjoj heš tabeli može pomeriti stariji ključ na neko drugo mesto u tabeli.

Istorija

Kukavičji hešing su prvi opisali Rasmuš Pag (engl. Rasmus Pagh) i Flemming Frih Rodler (engl. Flemming Friche Rodler) u 2001.

Teorija

Osnovna ideja je da koristite dve heš funkcije, umesto samo jedne. Ovo obezbeđuje dve moguće lokacije u heš tabeli za svaki ključ. U jednom od najčešće korišćenih varijanti algoritma, heš tabela je podeljena na dve manje tabele jednake veličine i svaka heš funkcija daje indeks u jednoj od ove dve tabele. Kada se ubaci novi ključ, koristi se pohlepni algoritam. Novi ključ se ubacuje u jednu od svoje dve moguće lokacije, " izbacivanje " , to je, pomeranje, bilo kojeg ključa koji se već možda nalazi na toj lokaciji. Ovaj pomeren ključ se onda ubacuje u svoju alternativnu lokaciju, ponovo izbacuje bilo koji ključ koji se tamo nalazi, dokle god se ne nađe upražnjeno mesto, ili će postupak ući u beskonačnu petlju. U drugom slučaju, heš tabela je obnovljena na mestu pomoću nove heš funkcije. Nema potrebe da se alocira nova tabela za ponovno heširanje. Jednostavno možemo proći kroz tabele brišući i izvršiti uobičajenu proceduru ubacivanja na svim ključevima koji nisu nađeni na svojim namenjenim mestima u tabeli .

- Pagh & Rodler, "Cuckoo Hashing"

Pretraga zahteva pregled od samo dve lokacije u heš tabeli, koji u najgorem slučaju (pogledati Veliko O notaciju) vremenski traje konstantno. Ovo je u suprotnosti sa mnogim drugim algoritmima heš tabela, koji ne mogu da imaju stalni najgori slučaj vezan za vreme da uradi pretragu. Takođe se pokazalo da su umetanja uspela u očekivanom konstantnom vremenu, čak razmatrajući mogućnost obnavljanja tabela, dokle god se broj ključeva drži ispod polovine kapaciteta heš tabele, tj, faktor opterećenja je ispod 50%. Jedan metod dokazivanja ovoga koristi teoriju slučajnih grafova: jedan može formirati neusmerene grafove pod nazivom „Kukavičji graf“ koji ima najvišu tačku za svaku lokaciju heš tabele i ivicu za svaku heš vrednost, sa krajnjim tačkama ivice koje su dve moguće lokacije vrednosti. Onda, pohlepni algoritam ubacivanja za dodavanje skupa vrednosti u kukavičkoj heš tabeli uspeva, ako i samo ako kukavičji graf za ovaj skup vrednosti je grafikon sa najviše jednim ciklusom u svakim od njegovih povezanih komponenti; kao svaki podgraf indukovane najviše tačke sa više ivica nego čvorova odgovara skupu ključeva za koje postoje nedovoljan broj slotova u heš tabeli. Ovo svojstvo je tačno sa velikom verovatnoćom za slučajan graf u kome je broj ivica manji od polovine broja čvorova.

Primer

Zadate heš funkcije:

$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

Kolone u sledeće dve tabele prikazuju stanje heš tabela nakon pto su ubačeni elementi..

1. tabela za 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. tabela za 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

Ciklus

Ukoliko želite da ubacite element 6, ulazite u cilus. U poslednjem redu tabele nalazimo istu inicijalnu situaciju, kao što je bila na početku.

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

podrazumevani ključ	tabela 1		tabela 2
	stara vrednost	nova vrednost	stara vrednost	nova vrednost
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

Generalizacija i primene

Generalizacije o kukavičkom heširanju koje koriste više od dve alternativne heš funkcije može se očekivati da iskoristi efektivno veći deo prostora heš tabele dok žrtvuje neku brzinu pretrage i umetanja. Korišćenjem samo tri heš funkcije povećava opterećenje na 91%. Druga generalizacija kukavičkog hešinga se sastoji u korišćenju više od jednog ključa po kofi. Koristeći samo dva ključa po kofi dozvoljava faktor opterećenja iznad 80%. Drugi algoritmi koji koriste višestruke heš funkcije uključuju Blumov Filter. Kukavičji hešing može da se koristi za implementaciju strukture podataka ekvivalentno Blumovom Filteru. Pojednostavljena generalizacija kukavičkog heširanja zvani „iskrivljeni - asocijativnog“ keš se koristi u nekoj procesorskoj memoriji. Studija Zukovskog i saradnika, pokazale je da je kukavičji hešing je mnogo brži nego lančani hešing za male heš tabele na modernism procesorima smeštenim u kešu. Kenet Ros(engl. Kenet Ross) je pokazao da bucketized verzije kukavičkog heširanja (varijante koje koriste kofe koje sadrže više od jednog ključa) brži od konvencionalnih metoda koji važi isto i za velike heš tabele, kada je iskorišćenost prostora velika. Performanse bucketized kukavičji heš tabele je dalje istraživao Askitis, sa svojim performansama u poređenju protiv alternativnih Hesing šema. Istraživanje po Micenmaheru predstavlja otvorene probleme vezane za Kukavičko heširanje od 2009 godine.

Vidi još

• Savršena heš funkcija
• Linearno popunjabanje
• Duplo heširanje
• Kolizije
• Heš funkcija
• Kvadratno proveravanje

Literatura

• Pagh, Rasmus; Rodler, Flemming Friche (2001). „Cuckoo Hashing”. Algorithms — ESA 2001. Lecture Notes in Computer Science. 2161. str. 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. str. 113—122. ISBN 978-1-920682-72-9. Arhivirano iz originala (PDF) 16. 2. 2011. g. Pristupljeno 15. 4. 2014. 

Spoljašnje veze

• A cool and practical alternative to traditional hash tables Arhivirano na sajtu Wayback Machine (7. april 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. Pristupljeno 21. 7. 2008. 

Primeri

• 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