Hash-taulukko (hajautustaulu) – selitys, toimintaperiaate ja esimerkit

Hash-taulukko (hajautustaulu) – selkeä selitys, toimintaperiaate ja käytännön esimerkit. Opit avain/arvoparit, hash-funktion ja tehokkaan haun.

Hash-taulukko on tehokas tapa tallentaa ja hakea tietoa avain–arvo -pareina. Tietojenkäsittelytieteessä näitä säilyttämiseen tarkoitettuja välineitä kutsutaan tietorakenteiksi. Hash-taulukko käyttää hash-funktiota muuttamaan avaimen (esimerkiksi henkilön nimen) taulukon indeksiarvoksi. Jokaisella tallennettavalla kohteella on avain ja sitä vastaava arvo, kuten henkilön puhelinnumero, joka on artikkelin alkutekstissä kuvattu esimerkki (arvo).

Tiedot varastoidaan sisäiseen taulukkoon, joka käytännössä on sarja laatikoita tai lokeroita indekseillä 0, 1, 2, ... Hash-funktio laskee avaimesta kokonaisluvun (hash-koodin) ja yleensä käytetään esimerkiksi modulo-operaatiota, jotta saadaan taulukon sisään sijoittuva indeksi. Näin tiedon paikka voidaan laskea suoraan vain avaimen perusteella ilman koko tietomäärän läpikäyntiä.

Hash-funktio ja paikan määritys

Hash-funktio muuntaa avaimen (esim. merkkijonon tai numeron) numeroksi, jota käytetään taulukon indeksinä. Hyvä hash-funktio antaa keskimäärin tasaisen jakautuman eri indekseille, on nopea laskea ja soveltuu käytettäville avaintyypeille. Käytännössä hash-koodi voidaan vielä muuntaa taulukon pituuden mukaiseksi indeksiksi esimerkiksi operaatiolla hash_koodi % taulukon_koko.

Konfliktit (collisions) ja niiden ratkaisut

Koska eri avaimet voivat antaa saman indeksin (hash-koodi modulo taulukon koko), kolonisoituminen on väistämätön ongelma. Tavallisimmat ratkaisut ovat:

• Ketjutus (chaining): Jokaisessa taulukon solussa pidetään lista (esim. linkitetty lista tai dynaaminen taulukko) kaikista sinne osuneista avain–arvo -pareista. Haku käy ensin oikeaan lokeroon ja etsii sieltä avainta lineaarisesti.
• Avoin osoitus (open addressing): Jos laskettu paikka on varattu, etsitään seuraava vapaa paikka tietyllä probe-sekvenssillä. Tyypillisiä probe-menetelmiä ovat lineaarinen probing, kvadratische probing ja double hashing. Poistaminen vaatii usein erityisen merkin (tombstone) paikan vapauttamiseksi oikein.

Kuormituskerroin ja uudelleenkokoitus

Kuormituskerroin (load factor) lasketaan usein suhdelukuna n / capacity, jossa n on tallennettujen parien määrä ja capacity taulukon lokeroiden lukumäärä. Kun kuormituskerroin kasvaa liian suureksi (esim. yli 0.7), suorituskyky heikkenee konfliktien vuoksi, joten monet toteutukset laajentavat taulukon kokoa ja rehash»-toiminnon avulla laskennat uusiksi kaikille avaimille sopivat indeksit. Uudelleenkokoitus on kallis operaationa, mutta se tapahtuu harvoin ja kustannus tulee amortisoituneena per operaatio.

Suorituskyky (kompleksisuus)

Hyvin suunniteltu hash-taulukko tarjoaa keskimääräisesti O(1) aikavaativuuden hakemiselle, lisäykselle ja poistoille. Huonoissa tapauksissa (esim. kaikki avaimet kollidoivat tai hash-funktio on huono) suorituskyky voi heiketä O(n):ään, missä n on tallennettujen alkioiden määrä. Muistin käyttö ja varausten koko (capacity) vaikuttavat myös tehokkuuteen.

Avainkäytännöt ja hyvät hash-funktiot

Hyvän hash-funktion ominaisuuksia ovat:

• tasainen jakautuminen erilaisille avaimille,
• nopea laskenta,
• mieluiten deterministisyys (sama avain antaa aina saman hash-koodin),
• riittävä erottelukyky pienillä muutoksilla avaimessa.

Esimerkkejä käytännön algoritmeista ovat erilaiset merkkijonoille ja binääritiedoille optimoidut funktiot kuten MurmurHash tai djb2. Useimmat ohjelmointikielet tarjoavat valmiit hash-funktiot perusavaintyypeille; tärkeää on myös valita avaintyypiksi muuttumaton (immutable) tietotyyppi tai muistaa päivittää hash-arvo, jos avainta muokataan.

Poisto ja erityistilanteet

Ketjutuksessa poisto on yksinkertainen: etsitään ja poistetaan pari listasta. Avoimessa osoituksessa poisto vaatii usein tombstone-merkinnän, jotta probe-sekvenssin muut alkioiden löydettävyys säilyy (muuten myöhemmät haut saattavat katketa ennen kohdetta).

Käyttökohteet ja esimerkit

Hash-taulukoita käytetään laajasti esimerkiksi:

• assosiatiivisissa taulukoissa ja hakemistoissa (key-value stores),
• tietokannoissa indeksoinnissa ja välimuisteissa,
• joukkojen (set) toteutuksissa,
• ohjelmiston sisäisissä hakemistoissa, kokonaisten sanakirjojen toteutuksessa ja paljon muussa.

Esimerkki (konseptuaalinen): halutaan tallentaa nimiä puhelinnumeroineen. Avain = nimi (merkkijono), arvo = puhelinnumero. Syötettäessä hash-funktio laskee indeksin ja pari lisätään siihen lokeroon. Hakeessa sama prosessi: lasketaan indeksi ja etsitään oikea avain lokeroiden joukosta.

Käytännön toteutuksia

Monet ohjelmointikielet tarjoavat valmiita toteutuksia: Pythonin dict, Javan HashMap (ja synkronoitu Hashtable), C++:n unordered_map, Go:n map jne. Näissä toteutuksissa on usein optimoituja hash-funktioita, uudelleenkokoitusstrategioita ja valmiita konfliktinratkaisuja, joten useimmiten kannattaa käyttää kielen omaa rakennetta sen sijaan, että kirjoittaisi hash-taulukon nollasta.

Vinkkejä käytännössä

• Käytä hyvälaatuista hash-funktiota ja muuttumattomia avaimia.
• Pidä kuormituskerroin kohtuullisena ja anna toteutuksen huolehtia uudelleenkokoituksesta.
• Valitse ketjutus tai avoin osoitus sen mukaan, millaisia poistoja ja muistankäyttövaatimuksia sinulla on.
• Hyödynnä kielen tai kirjaston valmiita toteutuksia paitsi erityistapauksissa, kun tarvitset räätälöityä käyttäytymistä.

Yhteenvetona: hash-taulukko on erittäin tehokas ja käytännöllinen tietorakenne avain–arvo -parien tallentamiseen ja hakemiseen. Oikein suunniteltuna ja toteutettuna se tarjoaa keskimäärin vakioaikaiset operaatiot ja on siksi laajalti käytössä ohjelmistokehityksessä.

Kysymyksiä ja vastauksia

K: Mikä on hash-taulukko?

K: Mitkä ovat hash-taulukkoon tallennetun tiedon kaksi osaa?

K: Miten hash-taulukko toimii?

Kysymys: Mitä yleisiä käyttötarkoituksia hash-taulukoilla on?

K: Miksi Hash-taulukot ovat nopeampia kuin muut työkalut, kuten hakupuut tai muut hakurakenteet?

K: Millaiset tietokoneohjelmistot käyttävät Hash-taulukoita?

Hae kirjaimella