Hajautustaulu

Hajautustaulu, tai hash table, on tietorakenne, joka säilyttää avain-arvo -pareja. Sen perusidea on käyttää hajautusfunktiota muuntamaan avaimet taulukon indekseiksi, jotta arvoihin voidaan hakea, lisätä ja poistaa nopeasti. Hajautustaulun koko ja hajautuksen laatu vaikuttavat suorituskykyyn; keskimäärin operatiot ovat O(1).

Toiminta perustuu siihen, että sama avain tuottaa saman indeksin, mutta eri avaimet voivat törmätä samaan kohtaan. Törmäykset ratkaistaan kahdella yleisellä tavalla: eriyttämällä ketjuttamisella (separate chaining) ja avoimella osoitusmenetelmällä (open addressing). Eriytetyllä ketjuttamisella kukin taulukon paikka tallentaa listan avain-arvo -pareista, ja haku sekä poisto kulkevat tämän listan läpi. Avoimessa osoitusmenetelmässä arvo tallennetaan seuraaviin indekseihin tietyn tutkimusjakson mukaan, esimerkiksi lineaarisella, kvadraattisella tai kaksinkertaisella hajautuksella.

Suorituskyky riippuu täyttöasteesta (load factor) ja hajautusfunktion laadusta. Keskimäärin operatiot ovat O(1), mutta pahimmillaan ne voivat olla O(n), jos törmäyksiä on runsaasti tai avaimet ovat huonosti hajautettuja. Taulukon koon laajentaminen (rehashing) käytetään, kun täyttöaste ylittää asetetun kynnin, jotta suorituskyky pysyy hyvänä.

Käyttökohteita ovat muun muassa sanakirjat, välimuistit, symbolitaulut ohjelmointikielissä ja monissa tietokantaratkaisuissa, missä nopea avainperusteinen pääsy on tärkeää. Hajautustaulu on yleinen perusta tietorakenteissa, joissa avaimia käsitellään nopeasti.