Käki-hashing

Cuckoo-hajautus on algoritmi, joka ratkaisee hash - arvojen törmäykset taulukossa , jossa noutoaika on vakio pahimmassa tapauksessa [ .

Ehdotettu vuonna 2001 [1] . Nimi viittaa joidenkin käkilajien käyttäytymiseen , kun poikanen työntää munia tai muita poikasia ulos pesästä; Samoin algoritmi tarjoaa mahdollisuuden työntää vanha avain ulos, kun uusi avain asetetaan.

Toiminnot

Käkihajautus on eräänlainen avoin osoitus , jossa hash-taulukon jokainen ei-tyhjä solu sisältää avaimen tai avain-arvo- parin . Hajautusfunktiota käytetään määrittämään kunkin avaimen sijainti, ja sen läsnäolo taulukossa (tai siihen liittyvä arvo) voidaan löytää tutkimalla kyseistä solua taulukossa. Avoin osoitus kärsii kuitenkin törmäyksistä , joita tapahtuu, kun useampi kuin yksi avain päätyy samaan soluun. Käkihajautuksen perusideana on ratkaista törmäykset käyttämällä kahta hash-funktiota yhden sijasta. Tämä tarjoaa kaksi mahdollista paikkaa hash-taulukossa kullekin avaimelle. Yhdessä algoritmin tavallisista muunnelmista hash-taulukko jaetaan kahteen pienempään taulukkoon, ja jokainen hash-funktio antaa indeksin jompaankumpaan näistä kahdesta taulukosta. On myös mahdollista varmistaa, että molemmat hash-funktiot indeksoidaan samassa taulukossa.

Hakeminen vaatii vain kahden paikan tarkastelemista hash-taulukossa, pahimmassa tapauksessa jatkuvaa aikaa ( katso "o" iso ja "o" pieni ). Tämä on toisin kuin monet muut hash-taulukkoalgoritmit, jotka eivät tarjoa vakioita noutoaikoja pahimmassa tapauksessa. Poistaminen voidaan tehdä myös tyhjentämällä avaimen sisältävä solu pahimmassa tapauksessa vakioajassa, mikä on helpompaa kuin muissa menetelmissä, kuten lineaarisessa luotauksessa .

Kun uusi avain lisätään ja toinen soluista on tyhjä, avain voidaan sijoittaa kyseiseen soluun. Siinä tapauksessa, että molemmat solut ovat varattuina, on tarpeen siirtää muut avaimet muihin paikkoihin (tai päinvastoin niiden aikaisempiin paikkoihin), jotta uudelle avaimelle saadaan tilaa. Käytetään ahnetta algoritmia - avain sijoitetaan johonkin mahdollisista asennoista, "työntämällä" kaikki tässä asennossa olleet avaimet. Poistettu avain asetetaan sitten vaihtoehtoiseen asentoonsa, jolloin kaikki siellä mahdollisesti olleet avain poistetaan. Prosessi jatkuu, kunnes tyhjä paikka löytyy. On kuitenkin mahdollista, että lisäysprosessi epäonnistuu, joutuu äärettömään silmukkaan tai kun ketju on liian pitkä (pidempi kuin ennalta määrätty kynnys, joka riippuu logaritmisesti taulukon pituudesta). Tässä tapauksessa tiivistetaulukko rakennetaan uudelleen paikoilleen uusilla hash-funktioilla :

Uutta taulukkoa ei tarvitse perustaa uudelleenkäsittelyä varten – voimme yksinkertaisesti käydä taulukon läpi ja poistaa ja lisätä uudelleen avaimet, jotka eivät ole oikeassa asennossa. [yksi]Pagh & Rodler, "Cuckoo Hashing"

Laskennallinen monimutkaisuus

Odotettu lisäysaika on vakio [1] , vaikka otetaan huomioon mahdollinen taulukon uudelleenrakentamistarve, kunhan avainten määrä on alle puolet hash-taulukon kapasiteetista, eli kuormituskerroin on alle 50 %.

Tämän varmistamiseksi käytetään satunnaisgraafiteoriaa - voit muodostaa ohjaamattoman graafin , jota kutsutaan "käkigraafiksi", jossa kärjet ovat hash-taulukon soluja ja kunkin hajautettavan pisteen reunat yhdistävät kaksi mahdollista paikkaa ( hash-taulukko). Sitten ahne algoritmi arvojoukon lisäämiseksi käkihajautustaulukkoon onnistuu, jos ja vain, jos tämän arvojoukon käkigraafi on pseudometsä , kaavio, jossa on enintään yksi sykli jokaisessa yhdistetyssä komponentissa . Mikä tahansa kärkipisteiden luoma aligraafi, jossa on enemmän särmiä kuin pisteiden lukumäärä, vastaa avaimia, joille tiivistetaulukossa ei ole tarpeeksi paikkoja. Jos hash-funktio valitaan satunnaisesti, käkigraafi on satunnainen graafi Erdős - Rényi-mallissa . Suurella todennäköisyydellä satunnaisessa graafissa, jossa reunojen lukumäärän suhde kärkien lukumäärään on rajattu yli 1/2, graafi on pseudometsä ja käkihajautusalgoritmi paikantaa onnistuneesti kaikki avaimet. Lisäksi sama teoria osoittaa, että käkigraafin yhdistettyjen komponenttien odotettu koko on pieni, mikä varmistaa vakion odotetun lisäysajan [2] .

Esimerkki

Kun otetaan huomioon seuraavat kaksi hash-funktiota:

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)
kaksikymmentä	9	yksi
viisikymmentä	6	neljä
53	9	neljä
75	9	6
100	yksi	9
67	yksi	6
105	6	9
3	3	0
36	3	3
39	6	3

Kahden seuraavan taulukon sarakkeet näyttävät tiivistetaulukon tilan elementtien lisäämisen jälkeen.

1. h(k) taulukko
	kaksikymmentä	viisikymmentä	53	75	100	67	105	3	36	39
0
yksi					100	67	67	67	67	100
2
3								3	36	36
neljä
5
6		viisikymmentä	viisikymmentä	viisikymmentä	viisikymmentä	viisikymmentä	105	105	105	viisikymmentä
7
kahdeksan
9	kaksikymmentä	kaksikymmentä	53	75	75	75	53	53	53	75
kymmenen

2. h'(k) taulukko
	kaksikymmentä	viisikymmentä	53	75	100	67	105	3	36	39
0									3	3
yksi			kaksikymmentä	kaksikymmentä	kaksikymmentä	kaksikymmentä	kaksikymmentä	kaksikymmentä	kaksikymmentä	kaksikymmentä
2
3										39
neljä				53	53	53	viisikymmentä	viisikymmentä	viisikymmentä	53
5
6							75	75	75	67
7
kahdeksan
9						100	100	100	100	105
kymmenen

Pyörät

Jos haluat lisätä elementin 6, saat äärettömän silmukan. Taulukon viimeiseltä riviltä löytyy sama alkutilanne kuin alussa.

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

avain	pöytä 1		taulukko 2
	vanha arvo	uusi arvo	vanha arvo	uusi arvo
6	viisikymmentä	6	53	viisikymmentä
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	viisikymmentä	53
viisikymmentä	39	viisikymmentä	36	39
36	3	36	6	3
6	viisikymmentä	6	53	viisikymmentä

Muunnelmia

Käkihajautuksen muunnelmia on tutkittu lähinnä tilankäytön parantamiseksi kuormituskerrointa nostamalla . Näissä versioissa voidaan saavuttaa yli 50 %:n kuormituskynnys. Joitakin näistä menetelmistä voidaan käyttää vähentämään merkittävästi tarvittavien tietorakenteen uusien määrää.

Useampaa kuin kahta hash-funktiota käyttävän käkitiivistyksen yleistämisen voidaan odottaa hyödyntävän hash-taulukkoa paremmin, mikä uhraa jonkin verran haku- ja lisäysnopeutta. Kolmen hash-funktion käyttö nostaa latauskertoimen 91 %:iin [3] . Toinen käkihajautuksen yleistys, nimeltään block cuckoo hashing , sisältää useamman kuin yhden avaimen solua kohden. Kahden näppäimen käyttö solua kohti mahdollistaa kuormituksen nostamisen yli 80 % [4] .

Toinen tutkittu vaihtoehto on käkihajautus marginaalilla . "Stock" on vakiopituinen avainten joukko, jota käytetään tallentamaan avaimia, joita ei voida lisätä onnistuneesti päähajautustaulukkoon. Tämä muutos vähentää epäonnistumisten määrää käänteispolynomifunktioon asteella, joka voi olla mielivaltaisen suuri lisäämällä marginaalin kokoa. Suuri marginaali tarkoittaa kuitenkin hitaampaa hakua avaimelle, joka ei ole päätaulukossa tai jos se on marginaalissa. Varastoa voidaan käyttää yhdessä useamman kuin kahden hash-funktion tai estää käkihajautustoiminnon, jotta saavutetaan sekä korkea käyttöaste että alhainen lisäysvirhe [5] . Cuckoo-hajautusanalyysi on laajentunut enemmän kuin käytännön tiivistefunktioihin, ei vain teoreettisessa hash-analyysissä käytettyihin satunnaisiin hajautusmalleihin [6] .

Jotkut tutkijat ehdottavat, että joissakin prosessorin välimuistissa käytetään yksinkertaistettua käkihajautuksen yleistystä, jota kutsutaan epäsymmetriseksi assosiatiiviseksi välimuistiksi . [7]

Vertailu samankaltaisiin rakenteisiin

On muitakin algoritmeja, jotka käyttävät useita hajautusfunktioita, erityisesti Bloom-suodatin , muistitehokas tietorakenne sumeille joukoille. Vaihtoehtoinen tietorakenne samojen sumeiden joukkojen ongelmille, joka perustuu käkihajautusjärjestelmään, nimeltään Käkisuodatin , käyttää vielä vähemmän muistia ja (toisin kuin klassiset Bloom-suodattimet) mahdollistaa elementtien poistamisen, ei vain lisäyksen ja olemassaolon tarkistamista. Näiden menetelmien teoreettinen analyysi on kuitenkin paljon heikompi kuin Bloom-suodattimien analyysi [8] .

Vuonna 2006 tehdyt tutkimukset [9] osoittivat, että käkihajautus on huomattavasti nopeampi kuin nykyaikaisten prosessorien välimuistissa olevien pienten hash-taulukoiden ketjutusmenetelmä . Samana vuonna [10] kehitettiin lohkoversio Cuckoo hashingista (lohko sisältää useamman kuin yhden avaimen), joka on nopeampi kuin perinteiset menetelmät suurille hash-taulukoille korkean kuormituskertoimen tapauksessa. Cuckoo hash -taulukon lohkoversion nopeutta tutkittiin vuonna 2009 [11] .

Katso myös

Täydellinen hash-toiminto
Lineaarinen soundi
Kaksoistiivistys
Hash-funktion törmäys
Hashing
Quadratic sounding
Hashing "Classics"

Muistiinpanot

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

Kirjallisuus

Rasmus Pagh, Flemming Friche Rodler. Cuckoo Hashing // Algoritmit - ESA 2001. - 2001. - T. 2161. - S. 121-133. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-42493-2 . - doi : 10.1007/3-540-44676-1_10 .
Reinhard Kutzelnigg. Neljäs matematiikan ja tietojenkäsittelytieteen kollokviumi. - 2006. - T. AG. — s. 403–406. — (Diskreetti matematiikka ja tietojenkäsittelyteoria).
M. Mitzenmacher. 17. vuosittaisen eurooppalaisen algoritmien symposiumin (ESA) julkaisut. – 2009.
Martin Dietzfelbinger ja Christoph Weidling. Tasapainoinen kohdistaminen ja sanakirjat tiiviisti pakatuilla vakiokokoisilla laatikoilla // Teoria. 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. Vahvempi tiivistys: käkihajautus kätköllä // SIAM J. Comput.. - 2010. - V. 39 , no. 4 . - S. 1543-1561 . - doi : 10.1137/080728743 .
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel. Selkeä ja tehokas hash riittää käkihajautusperheille, joilla on kätkö // 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 // ;kirjaudu sisään:. - USENIX, 2013. - T. 38 , no. 4 . - S. 36-40 .
Marcin Zukowski, Sandor Heman, Peter Boncz. Arkkitehtuuri Conscious Hashing. — Proceedings of International Workshop on Data Management on New Hardware (DaMoN), 2006.
Kenneth Ross. Tehokkaat hajautusanturit nykyaikaisissa prosessoreissa. - IBM:n tutkimusraportti RC24100, 2006.
Nicholas Askitis. Nopeat ja kompaktit hajautustaulukot kokonaislukuavaimille. - 32nd Australasian Computer Science Conference (ACSC 2009) aineistoa. - 2009. - T. 91. - S. 113–122. - ISBN 978-1-920682-72-9 .

Linkit

Viileä ja käytännöllinen vaihtoehto perinteisille hash-taulukoille , U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
Cuckoo Hashing opiskelijoille, 2006 , R. Pagh, 2006.
Cuckoo Hashing, teoria ja käytäntö (osa 1, osa 2 ja osa 3 ), Michael Mitzenmacher, 2007.
Moni Naor, Gil Segev, Udi Wieder. Automaattien, kielten ja ohjelmoinnin kansainvälinen kollokviumi (ICALP). - Reykjavik, Islanti, 2008.
Algorithmic Improvements for Fast Concurrent Cuckoo Hashing , X. Li, D. Andersen, M. Kaminsky, M. Freedman. Eurosys 2014.