Hajautustaulu

Wikipedia

Hajautustaulu on tietotekniikassa tietorakenne, jolla yhdistetään avain arvoon. Tällä saavutetaan tehokas menetelmä jolla voidaan hakea sekä usein myös tallentaa sekä poistaa tietoa taulusta. Hajautustaulujen toimintaan liittyy hyvin läheisesti tiivisteet, jonka avulla avain muunnetaan taustalla olevan taulun indeksiksi. Ks. hajautusalgoritmi

[muokkaa] Törmäykset

Hajautustauluissa voi tapahtua törmäyksiä, joiden sattuessa voidaan käyttää erilaisia strategioita.

1. Voidaan suorittaa uudelleenindeksointi, jossa tiivisteen arvoa käytetään indeksin laskemiseen alkuperäisena arvon sijasta.

2. Voidaan siirtyä eteenpäin niin kauan että tulee vastaan vapaa indeksi.

3. Tallennetaan samaan indeksiin useampi arvo.

Menetelmissä 1 ja 2 on vaarana että uudelleenindeksointi kestää liian kauan tai ei tuota tulosta.

[muokkaa] Taulun koko

Jos käytetään tekniikkaa 1 tai 2 törmäyksien hoitoon, tulee myös huolehtia siitä että taulun täyttöaste pysyy riittävän harvana, ja että se ei tule täyteen. Tämä tekniikka tosin vaatii että käytettävissä on menetelmä taulukon uudelleenallokointiin.

Tämä artikkeli on käännetty vieraskielisen Wikipedian artikkelista, ja siitä puuttuvat lähdemerkinnät.
Voit auttaa Wikipediaa etsimällä sopivat lähteet.