Hashtablepohjaiset

Hashtablepohjaiset tietorakenteet ovat tietorakenteita, joissa hash-taulu on keskeinen tallennus- ja hakuoperaatioiden perusta. Niiden ideana on hajauttaa avaimet hash-funktion avulla taulukon indeksoitavaksi ja säilyttää niihin liittyvät arvot tämän hajautetun paikan sisällä. Tämän ansiosta hakeminen, lisääminen ja poistaminen voidaan tehdä yleensä erittäin nopeasti keskimäärin.

Käytännössä hashtablepohjaiset rakenteet voivat toteuttaa kollisioonhallinnan kahdella päätavalla: erillinen ketjuttaminen (separate chaining) ja avoin osoitus (open addressing). Ketjuttamisessa samaan hakukohtaan voidaan tallentaa useita avaimia listana tai muuna rakenteena. Avoimessa osoituksessa tyhjiä paikkoja täytetään hakeutuvan kohdan ympärille lineaarisesti, kvadraattisesti tai kaksoishajautuksella. Taulun kokoa kasvatetaan ja uudelleen hajautetaan (rehashing), kun täyttöaste ylittää asetetun kynnyksen, jotta suorituskyky säilyy.

Suorituskyky riippuu hash-funktion laadusta ja kollisioonhallinnasta. Keskimäärin operaatioiden aikavaikutus on O(1), mutta pahimmillaan se voi olla O(n), jos hajautus on epäonnistunut tai taulu on liian täynnä. Oikea koon kasvatus sekä hyvän laadun hash-funktion valinta ovat keskeisiä suunnittelun kannalta.

Hashtablepohjaiset rakenteet ovat yleisiä sanakirjoissa (indoors maps), joukkojen toteutuksissa sekä välimuistien kehittämisessä. Ohjelmointikielissä ne löytyvät muun muassa Java HashMap ja HashSet, Pythonin dict, C++ unordered_map ja unordered_set sekä monissa C-kirjastoissa erilaisina ratkaisuina. Niiden valinta riippuu käyttötapauksesta ja vaaditusta suorituskyvystä sekä järjestykseen liittyvistä tarpeista.