Hajautustaulut

Hajautustaulu on tietorakenne, joka tallentaa avain-arvopareja siten, että avaimen perusteella voidaan nopeasti hakea siihen liittyvä arvo. Jokaiselle avaimelle lasketaan hajautusarvo (hash), joka muunnetaan taulukon indeksoinnin avulla. Hyvä hajautus jakaa avaimet tasaisesti ja vähentää törmäysten määrää.

Toimintaperiaate perustuu kahteen osaan: taulukkoon ja hajautukseen. Hajautusarvo lasketaan avaimesta ja otetaan modulo taulukon koon, jolloin arvo osoittaa indeksiin. Törmäyksiä syntyy, kun useampi avain viittaa samaan indeksiin. Näiden ongelmien ratkaisemiseksi on kaksi päämenetelmää: erottelu (separate chaining) ja avoin osoitus (open addressing). Erottelussa jokaiselle indeksille voi olla erillinen ketjutettu lista tai muu rakenne, johon törmäävät avaimet tallennetaan. Avoimessa osoituksessa kaikki avaimet ovat taulukossa itsessään, ja törmäykset ratkaistaan etsimällä seuraava vapaa paikka esimerkiksi lineaarisella tai potenssipropeerauksella.

Suorituskyvyltään hajautustaulut tarjoavat yleensä keskimäärin O(1) aikaista suorittamista per operaatio (lisäys, haku, poisto). Pahimmassa tapauksessa aikavaikutus voi olla O(n), jos törmäykset kasaantuvat pahasti. Suunnittelussa käytetään usein myös dynaamista koonmuutosta: kun täyttöaste ylittää tavoitetason (esim. noin 0,7), taulukko kasvatetaan ja sisällöt rehashataan uudelleen hajautukseen sopivaan kokoon.

Sovelluksiaan hajautustaulut löytyvät sanakirjoista, symbolitauluista, välimuisteista sekä monenlaisista tietovarastointiratkaisuista. Törmäysten hallinta sekä hajautusfunktion laatu ovat keskeisiä tekijöitä suorituskyvyssä ja muistivaatimuksissa.