Hajautustaulukot

Hajautustaulukko on tietorakenne, joka mahdollistaa avainten ja niihin liittyvien arvojen nopean sijoittamisen ja hakemisen. Perusideana on käyttää hajautusfunktiota avaimen muuntamiseksi taulukon indeksiin, jolloin arvo tallennetaan tähän kohtaan. Törmäykset — tilanne, jossa kaksi avainta saa saman indeksin — ratkaistaan eri tavoilla.

Törmäysratkaisut voidaan jakaa pääpiirteittäin kahteen ryhmään: erillisellä jäsentelyllä (separate chaining) säilytetään samaan indeksiin useita avaimia linkitettyinä listoina, ja avoimella osoittamisella (open addressing) etsitään seuraava vapaa paikka peräkkäin tai tietyllä laskentatavalla (lineaarinen haku, neliömäinen haku tai kaksoishajautus).

Hajautustaulukon koon hallinta ja uudelleenjakoaminen (rehashing) tapahtuvat tyypillisesti, kun kuormitusprosentti ylittää tietyn kynnin. Hyvä hajautusfunktio jakaa avaimet tasaisesti; huono funktio aiheuttaa liian monia törmäyksiä. Suorituskyky on keskimäärin O(1) operaatioille hakeminen, lisäys ja poisto, mutta pahimmillaan se voi olla O(n) riippuen törmäysten määrästä ja uudelleenjakoamisesta.

Käyttökohteita ovat sanakirjat, välimuistit ja set-tyypit, joissa nopea pääsy on tärkeää. Useat ohjelmointikielet tarjoavat hash-taulukkoihin perustuvia sanakirja- ja set-tyyppejä, kuten Pythonin dict, Java HashMap ja C++:n unordered_map.