Hajautusalgoritmi

Hajautusfunktio () 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:
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 codice_1 palauttaa. 
Törmäykset.
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.
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.
Esimerkki kaksoishajautuksesta:
Toteutukset.
Nykyään hajautustauluja tarvitsee tai kannattaa toteuttaa harvoin itse. C++:n STL sisältää tietorakenteen codice_2 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.