Hajautusalgoritmi
Wikipedia
Hajautusfunktio on algoritmi, jota käytetään tietorakenteen hajautustaulun, eli tiivisteen, toteuttamisessa . 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, esim. käyttämällä ketjutusta. Ohessa yksinkertainen esimerkki pseudokoodina:
function compute_hash(string):
slot_size = 1000
num = 0
for char in string:
num = num + ascii_orginal(char)
quotient = mod(num, slot_size) # 0 <= quotient < slot_size
return quotient
Hajautustauluna käytetään nyt 1000-alkioista taulukkoa, ja kun jokin arvo halutaan tallentaa taulukkoon käyttäen merkkijonoa haluttua merkkijonoa avaimena, arvo tallennetaan taulukon siihen indeksiin, minkä compute_hash(merkkijono) palauttaa.
[muokkaa] Törmäykset
Eri merkkijonoista syntyvät samat hajautusarvot johtavat törmäyksiin. Ketjuttaessa 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.
Muita ratkaisuja törmäysten hoitamiseksi antavat kaksoishajautus sekä lineaarimenettely. Lineaarimenettelyssä kokeillaan yksitellen törmäyksen aiheuttaneelle alkiolle seuraavia vapaita lokeroja. Tätä jatketaan niin kauan 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
[muokkaa] Toteutukset
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, mutta tietorakennetta voidaan dynaamisesti kasvattaa ilman suurempia kustannuksia.
