Hajautustauluna

Hajautustauluna tarkoittaa avain–arvoparien tallentamiseen tarkoitettua tietorakennetta, jossa avaimet mapataan taulukon indekseiksi hajautusfunktion avulla. Hajautustaulu mahdollistaa nopean haun, lisäämisen ja poistamisen keskimäärin O(1) aikaa.

Rakenne koostuu taulukosta (kanttauskappale) ja hajautusfunktiosta. Kun avain hajautetaan, sen tuottama indeksi määrittää, mihin paikkaan arvo tallennetaan. Kollisoinnit, eli useampi avain osuu samaan indeksiin, ratkaistaan kahdella päämenetelmällä: ketjuttamisella (separate chaining) ja avoimella osoituksella (open addressing).

Ketjuttamisessa kukin bucket sisältää listan tai muun kokoelman samalla indeksillä olevista avaimista. Avoimessa osoituksessa seuraavat paikat etsitään peräkkäin tai muun probeerausstrategian mukaan, kuten lineaarisella probingilla, neliöprobeerauksella tai kaksinkertaisella hajautuksella.

Suorituskyky riippuu hajautuksesta ja kuormituksesta. Keskimääräinen aika operaatioille on O(1), kun avaimet jakautuvat tasaisesti. Pahin tapaus voi olla O(n), jos kollisioita kertyy paljon tai hash-funktio on huono. Muistinvaraisuutta hallitaan varhaisesti varaamalla tilaa ja hallitsemaan kuormitusastetta α = n/m, missä n on ajettu arvojen määrä ja m on bucketien määrä.

Taulukko laajennetaan, kun kuormitus ylittää kynnyksen, ja avaimet rehashataan uuteen, suurempaan taulukkoon. Hajautustaulut soveltuvat sanakirjoille, välimuisteille ja symbolitauluille; ne eivät säilytä avainten järjestystä ilman lisästruktuureja. Esimerkkejä ohjelmointikielistä ovat Pythonin dict ja Java HashMap.