hajautustaulua

Hajautustaulua, tunnetaan myös nimellä *hash table* tai *hash map*, on tietorakenne, joka mahdollistaa nopean avain-arvo-parien tallentamisen ja etsimisen. Se perustuu hajautusfunktioon, joka muuntaa avaimet taulukon indekseiksi. Tällä tavalla voidaan saavuttaa keskimääräinen etsintäaika O(1) eli vakioaika, mikä tekee hajautustaulusta tehokkaan valinnan monissa sovelluksissa.

Hajautustaulun toiminta perustuu kahteen pääkomponenttiin: hajautusfunktioon ja kollisioiden käsittelymekanismiin. Hajautusfunktio muuntaa avain arvoon, joka viittaa taulukon soluun. Jos kaksi eri avainta tuottaa saman indeksin (kollisio), käytetään joko ketjuja tai avoimia osoittimia ratkaista kollisio. Ketjutus tarkoittaa, että kollisoineet avaimet tallennetaan listoihin taulukon soluihin, kun taas avoin osoitin siirtää kollisoineet avaimet seuraaviin tyhjiin soluihin.

Hajautustaulua käytetään laajalti ohjelmointikielien kielellä toteutetuissa rakenteissa, kuten Pythonin `dict`, JavaScriptin `Object` ja `Map`, sekä C++-kielen `unordered_map`. Niiden sovellusalueita ovat muun muassa tietokantojen indeksointi, kielenkäsittely, graafialgoritmit ja muistettavien tietojen hallinta. Hajautustaulun tehokkuus riippuu hajautusfunktion laadusta ja taulukon kokoasetuksista, joiden tulee olla riittävän suuret välttääkseen liian suuren kollisioiden määrän.

Hajautustaulun etuja ovat nopeus ja yksinkertaisuus, mutta haittapuolena voi olla muistinkäyttö, sillä taulukko täytyy usein suurentaa dynamisesti, mikä voi aiheuttaa lyhytaikaisia suorituskyvyn laskuja. Hajautustaulun valinta riippuukin sovelluksen vaatimuksista, kuten etsintä-, lisäys- ja poistotoimintojen taajuudesta sekä muistivarannoista.