Hajautusalgoritmi
Hajautusfunktio (engl. hash function) on algoritmi, jota käytetään hajautustaulu-tietorakenteen toteuttamisessa. Se ottaa syötteeksi merkkijonon (tai helposti merkkijonoksi muutettavan muun tyypin) ja laskee sille ns. tiivisteen. Tätä tiivistettä puolestaan käytetään indeksinä taulukkoon, jota kutsutaan hajautustauluksi. Tyypillisesti hajautustauluja käytetään, kun halutaan indeksoida tietorakennetta käyttäen avaimina merkkijonoja numeeristen arvojen sijaan.
Yksinkertainen ja nopea hajautusalgoritmi perustuu johonkin suurehkoon vakioon ja jakojäännökseen, joka lasketaan vakion ja merkkijonosta muodostetun lukuarvon perusteella. Esimerkiksi hajautustauluun voidaan varata tilaa 1000:lle alkiolle jolloin sisäinen toteutus indeksoi aina taulukon alkioita 0..999. Törmäyksistä johtuvat päällekkäisyydet voidaan ratkaista usealla tavalla, esimerkiksi käyttämällä ketjutusta. Ohessa esimerkki pelkistetystä (ja moneen tarkoitukseen huonosta) hajautusfunktiosta pseudokoodina:
function laske_tiiviste(merkkijono): taulukon_koko = 1000 summa = 0 for merkki in merkkijono: summa = summa + ascii(merkki) jakojaannos = mod(summa, taulukon_koko) # 0 <= jakojaannos < taulukon_koko return jakojaannos
Hajautustauluna käytetään nyt 1000-alkioista taulukkoa, ja kun jokin arvo halutaan tallentaa taulukkoon käyttäen haluttua merkkijonoa avaimena, arvo tallennetaan taulukon siihen indeksiin, jonka laske_tiiviste(merkkijono) palauttaa.
Törmäykset
[muokkaa | muokkaa wikitekstiä]Eri merkkijonoista syntyvät samat hajautusarvot johtavat törmäyksiin. Hajautustarkoituksiin hyvä tiiviste on sellainen, joka minimoi törmäykset, eli jonka tuottamat tiivisteet syötemerkkijonoille jakautuvat hajautustauluun mahdollisimman tasaisesti.
Hajautustauluja käytettäessä on kuitenkin käytännössä aina varauduttava törmäyksiin. Ketjutettaessa tämä ratkaistaan siten, että samaan hajautusindeksiin osuneet avaimet muodostavat ketjun, jota käydään lävitse lineaarisesti. Lineaarisuus ei kuitenkaan tee hajautustaulusta tehotonta, koska hyvä hajautusfunktio tuottaa tasaisesti jakautuneita avaimia. Tällöin täynnä olevaan hajautustauluun tehtävien hakujen asymptoottinen kompleksisuus on edelleen sama kuin lineaarisessa haussa, O(n), mutta käytännössä hakunopeus on karkeasti ottaen kääntäen verrannollinen hajautustaulun kokoon.
Muita ratkaisuja törmäysten hoitamiseksi antavat kaksoishajautus sekä lineaarimenettely. Näitä käytettäessä hajautustauluun ei voida tallentaa mielivaltaista määrää arvoja, joten taulun täyttyminen pitää ottaa huomioon.
Lineaarimenettelyssä kokeillaan yksitellen törmäyksen aiheuttaneelle alkiolle seuraavia vapaita lokeroja. Tätä jatketaan kunnes vapaa lokero löytyy.
h(k,i) = (h'(k) + i) mod m .. missä h' on jokin hajautusfunktio ja m lokeroiden lukumäärä.
Hyötynä helppo toteutus, eikä ketjutuksessa esiintyviä listoja ole. Haittana on ryvästyminen - yhä useammin alkiot törmäävät pitenevään arvojen jonoon, josta seuraa tehottomuutta.
Kaksoishajautus tuottaa tasaisimman hajautuksen esitellyistä ratkaisuista. Siinä ideana on kaksi erillistä hajautusfunktiota, joiden summan mukaan alkion lokero määräytyy. Usein funktioiden jakojäännöskin lasketaan eri jakajan mukaan jolloin tulos satunnaistuu enemmän.
h(k,i) = (h'(k) + i * h''(k)) mod m .. missä h' ja h'' ovat hajautusfunktioita, m taulun koko, i on törmäyslaskuri.
Esimerkki kaksoishajautuksesta:
Olkoon: m = 13 h'(k) = k mod m h''(k) = 1 + (k mod (m-2)) Alkiot: 61, 16, 96, 21, 88, 15, 73 indeksit: 0 1 2 3 4 5 6 7 8 9 10 11 12 Sijainti: | | |15|16| |96| | |21|61|88| | | Muut arvot pääsevät ongelmitta omiin lokeroihinsa, mutta (h'(73) + 0 * h''(73)) mod 13 =(73 mod 13) mod 13 = 8, joka on jo varattu (21). Otetaan siis käyttöön toinen hajautusfunktio seuraavasti: (h'(73) + 1*(1 + (73 mod 11))) mod 13 = 3 Tällöin alkio yritetään sijoittaa lokeroon 3, mutta tämäkin lokero on jo varattu (16). Kasvatetaan siis i:tä yhdellä: (h'(73) + 2*(1 + (73 mod 11))) mod 13 = (8+16) mod 13 = 11 Tällöin alkio päätyy lokeroon 11, joka on vapaa. Lopullinen taulu indeksit: 0 1 2 3 4 5 6 7 8 9 10 11 12 Sijainti: | | |15|16| |96| | |21|61|88|73| | Lopullisen taulun ''täyttöaste'' on 53,8% = 7 / 13 = alkioiden määrä / taulun koko
Toteutukset
[muokkaa | muokkaa wikitekstiä]Nykyään hajautustauluja tarvitsee tai kannattaa toteuttaa harvoin itse. C++:n STL sisältää tietorakenteen map ja monet korkean tason ohjelmointikielet tarjoavat valmiit toteutukset (usein nimellä map, hash tai dictionary). Monesti hajautusfunktio on sisäisesti korvattu tasapainotetulla puurakenteella, jolloin haku pysyy edelleen nopeana (asymptoottinen kompleksisuus O(log n)), mutta tietorakennetta voidaan dynaamisesti kasvattaa käymättä kaikkia siihen talletettuja arvoja läpi.