Gegutės maiša

Gegutės maiša - informatikos metodas, padedantis išspręsti maišos funkcijų reikšmių susidūrimo, arba kolizijos problemą maišos lentelėje. Pirmieji gegutės maišą aprašė Rasmus Pagh ir Flemming Friche Rodler 2001 m.

Gegutės maišos pavyzdys. Rodyklės rodo alternatyvią vietą kiekvienam raktui. Naujas elementas A būtų įterptas perkeliant A į jo alternatyvią vietą, užimtą B, ir perkeliant B į jo alternatyvią vietą, kuri šiuo metu laisva. Naujo elemento įterpimas H vietoje nepavyktų: kadangi H yra ciklo dalis, naujas elementas vėl būtų išmestas ir maišos lentelę reiktų perdaryti.

Idėja

Pagrindinė idėja - naudoti dvi maišos funkcijas, o ne vieną. Kiekvienam raktui jos duoda dvi galimas vietas maišos lentelėje.

Rakto įterpimui naudojamas godusis algoritmas: naujas raktas yra įterpiamas vienoje iš dviejų galimų vietų. Jei vieta nėra tuščia, jis išmeta toje vietoje buvusį raktą: išstumtas raktas keliauja į savo antrąją vietą, išmeta ten buvusį raktą ir t. t., kol kuris nors išmestasis raktas atranda laisvą vietą. Priešingu atveju procesas užsitęsia be galo. Pastaruoju atveju maišos lentelė yra perdaroma naudojant naujas maišos funkcijas.

Rakto paieška reikalauja peržiūrėti tik dvi vietas lentelėje, t. y. trunka konstantinį laiką. Dauguma kitų maišos lentelės algoritmų gali neturėti konstantinio blogiausio atvejo rėžio rakto paieškai.

Taip pat galima parodyti, kad įterpimai vidutiniškai trunka konstantinį laiką, netgi atsižvelgiant į retkarčiais vykstančius lentelės perdarymus, vienintelis reikalavimas - kad lentelėje būtų užpildyta mažiau negu pusė vietų.

Apibendrinimai

Gegutės maišos apibendrinimai naudoja daugiau nei dvi maišos funkcijas ir gali sėkmingai dirbti išnaudodami didesnę dalį maišos lentelės talpos, nors šiuo atveju šiek tiek sumažėja paieškos ir įterpimo greitis. Trijų maišos funkcijų naudojimas leidžia apkrauti lentelę 91 %. Kitas gegutės maišos apibendrinimas - naudoti daugiau negu vieną raktą "kibirėliui" (angl. bucket). Naudojant 2 raktus "kibirėliui" leidžia panaudoti 80 % lentelės. Gegutės maiša gali būti naudojama realizuojant duomenų struktūrą ekvivalenčią Blumo filtrui.

Kita

Metodas pavadintas pagal kai kurių rūšių gegučių elgesį: jų gegučiukai išsiritę išmeta kitus kiaušinius ar jauniklius iš lizdo. Zukowski ir kiti parodė, kad gegutės maiša yra žymiai greitesnė nei grandininė maiša mažoms, liekančio podėlio (angl. cache - resident) maišos lentelėms naudojant šiuolaikinius procesorius. K. Ross parodė, kad "sukibirintos" (angl. bucketized) gegutės maišos versijos (t. y., tos, kurios naudoja daugiau nei vieną raktą "kibirėliui") yra greitesnės nei tradiciniai metodai didelėms maišos lentelėms, kai lentelės apkrovimas didelis. Deja, bet kol kas gegutės maiša lieka mažai žinoma už mokslinės visuomenės ribų.

Taip pat žiūreti

• Maišos funkcija

Literatūra

• Gegutės maiša, teorija ir praktika (2 dalis, 3 dalis)