Gøghashing

Cuckoo-hashing er en algoritme til at løse hashværdikollisioner i en tabel med konstant hentningstid i værste fald .

Foreslået i 2001 [1] . Navnet henviser til adfærden hos nogle gøgearter , når ynglen skubber æg eller andre unger ud af reden; på samme måde giver algoritmen mulighed for at trykke den gamle nøgle ud, når du indsætter en ny.

Operationer

Cuckoo hashing er en slags åben adressering , hvor hver ikke-tom celle i hash-tabellen indeholder en nøgle eller et nøgle-værdi- par . En hash-funktion bruges til at bestemme placeringen for hver nøgle, og dens tilstedeværelse i tabellen (eller værdien forbundet med den) kan findes ved at undersøge den pågældende celle i tabellen. Åben adressering lider dog af kollisioner , som sker, når mere end én nøgle ender i samme celle. Den grundlæggende idé med gøgehashing er at løse kollisioner ved at bruge to hash-funktioner i stedet for én. Dette giver to mulige positioner i hash-tabellen for hver nøgle. I en af de sædvanlige varianter af algoritmen er hashtabellen opdelt i to mindre tabeller af mindre størrelse, og hver hashfunktion giver et indeks til en af disse to tabeller. Det er også muligt at sikre, at begge hash-funktioner er indekseret i samme tabel.

Hentning kræver kun at se to steder i hash-tabellen, hvilket kræver konstant tid i værste fald ( se "o" stor og "o" lille ). Dette er i modsætning til mange andre hash-tabelalgoritmer, der i værste fald ikke giver konstante hentetider. Fjernelse kan også ske ved at rydde cellen, der indeholder nøglen, i konstant tid i værste fald, hvilket er lettere end i andre ordninger såsom lineær sondering .

Når en ny nøgle er indsat og en af de to celler er tom, kan nøglen placeres i den celle. I det tilfælde, hvor begge celler er optaget, er det nødvendigt at flytte andre nøgler til andre steder (eller omvendt til deres tidligere steder) for at gøre plads til en ny nøgle. En grådig algoritme bruges - nøglen placeres i en af de mulige positioner, og "skubber ud" enhver nøgle, der var i denne position. Den udstødte nøgle placeres derefter i sin alternative position, hvorved enhver nøgle, der måtte have været der, skubbes igen ud. Processen fortsætter, indtil en tom position er fundet. Det er dog muligt, at indsættelsesprocessen mislykkes, kommer ind i en uendelig løkke , eller når kæden er for lang (længere end en forudbestemt tærskel, der logaritmisk afhænger af bordets længde). I dette tilfælde genopbygges hash-tabellen på plads med nye hash-funktioner :

Der er ingen grund til at oprette en ny tabel til rehashing - vi kan blot gå gennem tabellen for at slette og genindsætte eventuelle nøgler, der ikke er i den position, de burde være. [en]Pagh & Rodler, "Cuckoo Hashing"

Beregningsmæssig kompleksitet

Den forventede indsættelsestid er konstant [1] , selv under hensyntagen til det mulige behov for at genopbygge tabellen, så længe antallet af nøgler er mindre end halvdelen af kapaciteten af hashtabellen, dvs. belastningsfaktoren er mindre end 50 %.

For at sikre dette, bruges tilfældig grafteori - du kan danne en urettet graf , kaldet en "gøgegraf", hvor hjørnerne er cellerne i hashtabellen, og kanterne for hver hashbar forbinder to mulige positioner (celler i hash-tabel). Så lykkes den grådige algoritme til at indsætte et sæt værdier i en gøgehash-tabel, hvis og kun hvis gøgegrafen for dette værdisæt er en pseudo -skov , en graf med højst én cyklus i hver tilsluttet komponent . Enhver top-genereret subgraf med flere kanter end antallet af toppunkter svarer til et sæt nøgler, som der ikke er nok pladser til i hash-tabellen. Hvis hash-funktionen er valgt tilfældigt, vil gøgegrafen være en tilfældig graf i Erdős-Rényi-modellen . Med en høj grad af sandsynlighed, for en tilfældig graf, hvor forholdet mellem antallet af kanter og antallet af hjørner er afgrænset over 1/2, er grafen en pseudo-skov, og gøge-hashing-algoritmen har succes med at lokalisere alle nøgler. Desuden beviser den samme teori, at den forventede størrelse af de forbundne komponenter i en gøgegraf er lille, hvilket sikrer en konstant forventet indsættelsestid [2] .

Eksempel

Givet følgende to hash-funktioner:

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)
tyve	9	en
halvtreds	6	fire
53	9	fire
75	9	6
100	en	9
67	en	6
105	6	9
3	3	0
36	3	3
39	6	3

Kolonnerne i de næste to tabeller viser hash-tabellens tilstand, efter at elementer er blevet indsat.

1. tabel for h(k)
	tyve	halvtreds	53	75	100	67	105	3	36	39
0
en					100	67	67	67	67	100
2
3								3	36	36
fire
5
6		halvtreds	halvtreds	halvtreds	halvtreds	halvtreds	105	105	105	halvtreds
7
otte
9	tyve	tyve	53	75	75	75	53	53	53	75
ti

2. tabel for h'(k)
	tyve	halvtreds	53	75	100	67	105	3	36	39
0									3	3
en			tyve	tyve	tyve	tyve	tyve	tyve	tyve	tyve
2
3										39
fire				53	53	53	halvtreds	halvtreds	halvtreds	53
5
6							75	75	75	67
7
otte
9						100	100	100	100	105
ti

Cykler

Hvis du ønsker at indsætte element 6, får du en uendelig løkke. I den sidste række af tabellen finder vi den samme begyndelsessituation som i begyndelsen.

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

nøgle	tabel 1		tabel 2
	gammel værdi	ny værdi	gammel værdi	ny værdi
6	halvtreds	6	53	halvtreds
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	halvtreds	53
halvtreds	39	halvtreds	36	39
36	3	36	6	3
6	halvtreds	6	53	halvtreds

Variationer

Nogle variationer af gøgehashing er blevet undersøgt, hovedsageligt med det formål at forbedre pladsudnyttelsen ved at øge belastningsfaktoren . I disse varianter kan en belastningstærskel på mere end 50 % nås. Nogle af disse metoder kan bruges til at reducere antallet af nødvendige genopbygninger af datastruktur markant.

En generalisering af gøgehashing ved brug af mere end to hashfunktioner kan forventes at gøre bedre brug af hashtabellen og ofre en vis hente- og indsættelseshastighed. Brugen af tre hash-funktioner øger belastningsfaktoren til 91 % [3] . En anden generalisering af gøgehashing, kaldet blokgøghashing , indeholder mere end én nøgle pr. celle. Brugen af to nøgler pr. celle giver dig mulighed for at øge belastningen til over 80 % [4] .

En anden mulighed, der er blevet undersøgt, er gøghashing med en margen . "Stock" er et array af nøgler med konstant længde, der bruges til at gemme nøgler, der ikke kan indsættes i master-hash-tabellen. Denne modifikation reducerer antallet af fejl til en invers polynomiefunktion med en grad, der kan være vilkårligt stor ved at øge størrelsen af marginen. En stor margen betyder dog en langsommere søgning efter en nøgle, der ikke er i hovedtabellen, eller hvis den er i margenen. Stokken kan bruges i kombination med mere end to hash-funktioner eller blokgøg-hashing for at opnå både høj udnyttelse og lave indsættelsesfejl [5] . Gøg-hash-analyse har mere end udvidet til praktiske hash-funktioner, ikke kun de tilfældige hash-modeller, der bruges i teoretisk hash-analyse [6] .

Nogle forskere foreslår at bruge en forenklet generalisering af gøgehashing i nogle processorcaches kaldet asymmetrisk associativ cache . [7]

Sammenligning med lignende strukturer

Der er andre algoritmer, der bruger flere hash-funktioner, især Bloom-filteret , en hukommelseseffektiv datastruktur til fuzzy sæt. En alternativ datastruktur for problemer med de samme fuzzy sæt, baseret på gøgehashing, kaldet gøgefilteret , bruger endnu mindre hukommelse og tillader (i modsætning til klassiske Bloom-filtre) fjernelse af elementer, ikke kun indsættelse og eksistenskontrol. Den teoretiske analyse af disse metoder er dog meget svagere end analysen af Bloom-filtre [8] .

Undersøgelser i 2006 [9] viste, at gøgehashing er betydeligt hurtigere end kædemetoden for små hashtabeller placeret i moderne processorers cache . Samme år [10] blev der udviklet en blokversion af gøgehashing (en blok indeholder mere end én nøgle), som er hurtigere end konventionelle metoder til store hashtabeller i tilfælde af høj belastningsfaktor. Hastigheden af blokversionen af gøgehashbordet blev undersøgt i 2009 [11] .

Se også

Perfekt hash-funktion
Lineær lyd
Dobbelt hashing
Hash funktion kollision
Hashing
Kvadratisk lydende
Hashing "klassikere"

Noter

↑ 1 2 3 Pagh, Rodler, 2001 , s. 121-133.
↑ Kutzelnigg, 2006 , s. 403-406.
↑ Mitzenmacher, 2009 .
↑ Dietzfelbinger og Weidling 2007 , s. 47-68.
↑ Kirsch, Mitzenmacher, Wieder, 2010 , s. 1543-1561
↑ Aumüller, Dietzfelbinger, Woelfel, 2014 , s. 428-456.
↑ "Mikro-arkitektur" .
↑ Fan, Kaminsky, Andersen, 2013 , s. 36-40.
↑ Zukowski, Heman, Boncz, 2006 .
↑ Ross, 2006 .
↑ Askitis, 2009 , s. 113-122.

Litteratur

Rasmus Pagh, Flemming Friche Rodler. Cuckoo Hashing // Algoritmer - ESA 2001. - 2001. - T. 2161. - S. 121–133. — (Forelæsningsnotater i datalogi). — ISBN 978-3-540-42493-2 . - doi : 10.1007/3-540-44676-1_10 .
Reinhard Kutzelnigg. Fjerde kollokvium om matematik og datalogi. - 2006. - T. AG. — s. 403–406. — (Diskret matematik og teoretisk datalogi).
M. Mitzenmacher. Proceedings of the 17th Annual European Symposium on Algorithms (ESA). – 2009.
Martin Dietzfelbinger, Christoph Weidling. Balanceret tildeling og ordbøger med tætpakkede beholdere i konstant størrelse // Teoret. Comput. Sci .. - 2007. - T. 380 , no. 1-2 . — s. 47–68 . - doi : 10.1016/j.tcs.2007.02.054 .
Adam Kirsch, Michael D. Mitzenmacher, Udi Wieder. Mere robust hashing: gøghashing med et gemmer // SIAM J. Comput.. - 2010. - V. 39 , no. 4 . - S. 1543-1561 . - doi : 10.1137/080728743 .
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel. Eksplicit og effektiv hash er tilstrækkeligt til gøge-hashfamilier med et gemmested // Algorithmica. - 2014. - T. 70 , no. 3 . — S. 428–456 . - doi : 10.1007/s00453-013-9840-x .
Bin Fan, Michael Kaminsky, David Andersen. Cuckoo Filter: Better Than Bloom // ;login:. - USENIX, 2013. - T. 38 , no. 4 . — S. 36–40 .
Marcin Zukowski, Sandor Heman, Peter Boncz. Arkitekturbevidst hashing. — Proceedings of the International Workshop on Data Management on New Hardware (DaMoN), 2006.
Kenneth Ross. Effektive Hash-prober på moderne processorer. - IBM Research Report RC24100, 2006.
Nicholas Askitis. Hurtige og kompakte Hash-tabeller til heltalsnøgler. - Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009). - 2009. - T. 91. - S. 113–122. - ISBN 978-1-920682-72-9 .