Viikon 7 aiheena on luentomateriaalin sivut 295–334.
Hajautusfunktion tehtävänä on muuttaa sille annettu arvo tietyllä välillä olevaksi kokonaisluvuksi eli hajautusarvoksi. Hajautusfunktion tulee toimia joka kerralla samalla tavalla, jotta hajautusarvo on pysyvä kuvaus alkuperäisestä arvosta. Lisäksi hajautusfunktion tulisi tuottaa mahdollisimman tasaisesti eri hajautusarvoja lukuvälillä.
Esimerkiksi jos hajautettava arvo on merkkijono, yksi yksinkertainen hajautusfunktio on käyttää hajautusarvona merkkijonon merkkien määrää. Tällöin esimerkiksi merkkijonon "Uolevi" hajautusarvo on 6. Lisää mahdollisia hajautusfunktioita tulee esille laskaritehtävissä.
Hajautustaulu on hajautusfunktioon perustuva tietorakenne. Ideana on laittaa jokainen alkio sen hajautusarvoa vastaavaan kohtaan taulukossa. Jos hajautusfunktio tuottaa tasaisesti hajautusarvoja, alkiot menevät tasaisesti eri puolille taulukkoa ja hajautustaulu toimii tehokkaasti.
Javan tietorakenteet HashSet ja HashMap
perustuvat hajautukseen.
Ne toimivat periaatteessa
samalla tavalla kuin TreeSet
ja TreeMap.
Kuitenkin niissä on kaksi tärkeää eroa:
Hash-rakenteet ovat nopeampia kuin
Tree-rakenteet.
Hash-rakenteissa tieto ei ole
järjestyksessä,
minkä vuoksi esim. metodeita higher
ja lower ei voi käyttää.
Jos tarvetta järjestykselle ei ole
(yleensä ei ole), niin kannattaa siis käyttää
Hash-rakenteita!
Hash-rakenteita voi käyttää suoraan
Javan omien luokka (esim. String) kanssa.
Kuitenkin jos luokka on itse tehty,
siihen täytyy liittää metodi hashCode,
jonka täytyy palauttaa olion hajautusarvo.