Koodit: QB: Hajautustaulu

Ohjelmointikielen tavallinen taulukko on mainio tietorakenne, mutta siinä on yksi rajoitus: taulukon alkioihin osoitetaan kokonaisluvuilla. Toisinaan olisi kuitenkin kätevämpää, jos indekseinä voisi käyttää esimerkiksi merkkijonoja. Tietorakenne hajautustaulu on vastaus tähän toivomukseen.

Tavoitteena on siis pystyä kirjoittamaan seuraavanlaista koodia:

' saksan kielen sanakirja
LISAA "on", "ist"
LISAA "tiistai", "Dienstag"
LISAA "tänään", "heute"
PRINT HAE("tänään") + " " + HAE("on") + " " + HAE("tiistai")
' tulostus: heute ist Dienstag

Hajautusfunktio ja hajautusarvo

Hajautustaulun perusidea on yksinkertainen: keksitään jokin matemaattinen kaava eli hajautusfunktio, jolla alkuperäinen tieto (tässä merkkijono) saadaan muutettua kokonaisluvuksi. Hajautusfunktion täytyy olla sellainen, että sama tieto muuttuu aina samaksi kokonaisluvuksi ja kokonaisluvut ovat tietyllä lukualueella. Lisäksi olisi toivottavaa, että hajautusfunktio antaisi mahdollisiman tasaisesti eri kokonaislukuja.

Ensimmäisten vaatimusten täyttäminen on helppoa: kunhan hajautusfunktioon ei kuulu satunnaislukuja tai vastaavaa, se muuttaa saman tiedon samaksi kokonaisluvuksi, ja kokonaisluvun saa halutulle lukualueelle jakojäännöksen avulla. Sen sijaan kokonaislukujen tasainen jakautuminen on vaikeampi ehto, mutta tämä vaikuttaa ainoastaan hajautustaulun tehokkuuteen. Hajautustaulu toimii, vaikka hajautusfunktio palauttaisi aina saman kokonaisluvun.

Merkkijonojen tapauksessa yksinkertainen hajautusfunktio voisi laskea merkkijonojen merkkien määrän. Tällöin esimerkiksi merkkijonon "abc" hajautusarvo (hajautusfunktion tuottama kokonaisluku) olisi 3 ja merkkijonon "testi" hajautusarvo olisi 5. Tämän hajautusfunktion heikkous on, että hyvin monelle merkkijonolle tulee sama hajautusarvo.

Hieman parempi hajautusfunktio muuntaa merkkijonon merkit kokonaisluvuiksi ja laskee nämä kokonaisluvut yhteen. Nyt esimerkiksi merkkijono "abc" koostuu merkeistä "a", "b" ja "c", joita vastaavat luonnollisesti kokonaisluvut 1, 2 ja 3. Hajautusarvo olisi siis 1 + 2 + 3 = 6. Vastaavasti merkkijonon "testi" hajautusarvo olisi 73. Nyt hajautusarvo riippuu paitsi merkkijonon pituudesta myös itse merkeistä. Edelleen puutteena on, että samat merkit eri järjestyksessä tuottavat saman hajautusarvon (esim. "talo" ja "lato") ja muutenkaan hajautusfunktion tasaisuudesta on hankalaa sanoa mitään varmaa.

Hajautustaulun toteutus

Hyvän hajautusfunktion miettimiseen voi käyttää paljon aikaa, mutta käytännössä vaikkapa yllä kuvattu merkkien koodien yhteenlasku voi riittää mainiosti. Nyt siis jokainen merkkijono pystytään muuttamaan kokonaisluvuksi, joten voidaan ruveta käyttämään ohjelmointikielen taulukkoja. Esimerkiksi jos merkkijonoa "abc" vastaa "ööö" ja merkkijonoa "testi" vastaa "putka", taulukon kohtaan 6 tulee "ööö" ja kohtaan 73 tulee "putka".

Tässä on ainoastaan yksi ongelma: monella taulukkoon tulevalla merkkijonolla voi olla sama hajautusarvo. Näin on varsinkin silloin, jos hajautusfunktio on huono ja samoja hajautusarvoja tulee paljon. Mutta vaikka hajautusarvot jakaantuisivat miten tasaisesti, kaksi hajautusarvoa voi mennä päällekkäin. Viimeistään näin käy silloin, kun hajautusarvojen määrä on suurempi kuin hajautustaulun koko.

Tähän ongelmaan on monta ratkaisua, joista yksi on tallentaa hajautustauluun suoran merkkijonon asemesta linkki merkkijonojen listaan. Yksinkertaisimmillaan listan voi toteuttaa toisen taulukon avulla. Nyt yksi hajautusarvo voi viitata yhteen tai useampaan merkkijonoon. Esimerkiksi jos halutaan tallentaa merkkijonojen "abc" ja "testi" lisäksi merkkijonot "talo" ja "lato", joiden molempien hajautusarvo on 48, hajautustaulu näyttää seuraavalta:

06 -> ("abc", "ööö")
48 -> ("talo", "aaa") -> ("lato", "bbb")
73 -> ("testi", "putka")

Nyt kun halutaan selvittää, mikä merkkijono vastaa merkkijonoa "lato", lasketaan ensin merkkijonon "lato" hajautusarvo, joka on 48. Tässä listassa on kaksi merkkijonoa, joista ensimmäinen on väärä merkkijono, mutta sillä on sattumalta sama hajautusarvo, ja toinen on haluttu merkkijono. Siis hajautustaulusta etsitään laskemalla hajautusarvo ja käymällä sitä vastaava lista läpi. Tietysti voi olla myös niin, että merkkijonoa ei ole hajautustaulussa.

Huomautuksia

Hajautustaulun toteutus ei ole kovin monimutkaista, varsinkaan jos ei pohdi syvällisesti hajautusfunktion toteutusta, mutta silti voi tulla mieleen, mitä hyötyä hajautustaulusta on verrattuna tavalliseen taulukkoon. Voisihan merkkijonot tallentaa sellaisenaan taulukkoon seuraavasti:

01 -> ("abc", "ööö")
02 -> ("testi", "putka")
03 -> ("talo", "aaa")
04 -> ("lato", "bbb")

Nyt mikä tahansa merkkijono löytyy käymällä taulukko läpi alusta loppuun. Tämä toteutus on hyvä, jos taulukossa on kymmeniä tai satoja merkkijonoja ja ohjelma etsii sieltä muutaman merkkijonon. Mutta jos taulukossa on tuhat merkkijonoa ja niitä etsitään miljoona kertaa, ohjelmasta tulee todella hidas. Ikävin tapaus on, jos merkkijonoa ei ole taulukossa, jolloin koko taulukko käydään turhaan läpi. Muutenkin etsittävät merkkijonot voivat usein sijoittua taulukon loppuosaan.

Kehittyneempi menetelmä on tallentaa merkkijonot taulukkoon aakkosjärjestyksessä:

01 -> ("abc", "ööö")
02 -> ("lato", "bbb")
03 -> ("talo", "aaa")
04 -> ("testi", "putka")

Nyt merkkijonoja voi etsiä hyvin nopeasti binäärihaulla, joka perustuu hakualueen toistuviin puolituksiin sen mukaan, onko tutkittavassa kohdassa oleva merkkijono etsittävää ennen vai sen jälkeen aakkosjärjestyksessä. Tässä kuitenkin vaikeutena on taulukon päivitys niin, että aakkosjärjestys säilyy. Esimerkiksi jos taulukon alkuun halutaan lisätä merkkijono, kaikkia merkkijonoja täytyy siirtää alemmas, mikä on todella työläs toimenpide, jos taulukko on suuri.

Hajautustaulussa sekä tiedon haku että lisäys sujuvat todella nopeasti, jos hajautusarvojen lukualue (eli hajautustaulun koko) on riittävän suuri ja hajautusfunktio on kelvollinen. Esimerkiksi jos hajautustaulussa on tilaa 10000 hajautusarvolle ja merkkijonoja on 5000, luultavasti suurin osa hajautusarvoja vastaavista listoista on lyhyitä (yksi tai kaksi merkkijonoa) ja tietyn merkkijonon löytämiseksi täytyy tutkia vain muutama taulukon kohta. Tavallista taulukkoa käyttämällä pitäisi tutkia keskimäärin 2500 kohtaa ja tämäkin olettaen, että merkkijono yleensä löytyy taulukosta.

Mitä sitten tapahtuu, jos hajautusfunktio tuottaa liian usein saman hajautusarvon? Esimerkiksi jos käytetään surkeaa hajautusfunktiota, joka palauttaa aina kokonaisluvun 13, kaikki merkkijonot joutuvat samaan listaan ja muu hajautustaulu on typötyhjä. Tällöin tilanne vastaa täysin tavallisen taulukon käyttöä. Mitä tasaisemmin hajautusarvot jakaantuvat, sitä vähemmän hajautustaulu kärsii tavallisen taulukon ongelmista.

Hajautusarvojen kytkeminen listoihin ei ole ainoa tapa välttää hajautusarvojen törmäyksiä. Yksi keino on heittää vanha tieto menemään, jos uutta puskee päälle, mutta tämä ei tule yleensä kysymykseen. Toinen menetelmä on käydä hajautustaulua niin kauan läpi oikeasta hajautusarvosta aloittaen, kunnes vastaan tulee varaamaton indeksi. Tästä kehittyneempi versio on etsiä tyhjää paikkaa hyppien, jotta tietty hajautustaulun osa ei ruuhkautuisi. Tällöin kaikki tiedot mahtuvat hajautustaulun sisään, mutta toteutuksesta tulee helposti monimutkaisempi ja ehdottomasti suurin tietojen määrä on hajautustaulun alkioiden määrä.

Esimerkistä

Esimerkissä toteutetaan sanakirja hajautustaulun avulla. Hajautusfunktio on sama kuin ylempänä: kirjainten koodit lasketaan yhteen niin, että a = 1, b = 2, c = 3 jne. Hajautusarvot halutaan välille 0 – 99, minkä vuoksi lopputulos saadaan ottamalla jakojäännös 100:lla. Varsinaiset merkkijonot sisältävä lista toteutetaan taulukon avulla, jonka jokaisessa alkiossa on kaksi merkkijonoa (indeksi ja sisältö). Lisäksi erillisessä taulukossa lukee listojen rakenne taulukon sisällä. Luku 0 tarkoittaa joka tilanteessa listan loppua.

' hajautustaulu
DIM SHARED htaulu%(100)
' merkkijonolista
DIM SHARED ttaulu$(1000, 2)
' listojen linkit
DIM SHARED ltaulu%(1000)
' tietojen kokonaismäärä
DIM SHARED tmaara%

LISAA "hyvin", "gut"
LISAA "ja", "und"
LISAA "melko", "ziemlich"
LISAA "myös", "auch"
LISAA "nopea", "schnell"
LISAA "ohjelma", "das Programm"
LISAA "on", "ist"
LISAA "tiistai", "Dienstag"
LISAA "toimii", "funktioniert"
LISAA "tänään", "heute"

CLS
PRINT "Käännösteksti:"

PRINT HAE$("tänään"); " "; HAE$("on"); " "; HAE$("tiistai")
PRINT HAE$("ohjelma"); " "; HAE$("toimii"); " "; HAE$("hyvin")
PRINT HAE$("ja"); " "; HAE$("on"); " "; HAE$("melko"); " "; HAE$("nopea")

PRINT
PRINT "Hajautustaulu:"

FOR i% = 0 TO 99
   IF htaulu%(i%) <> 0 THEN
      PRINT i%; TAB(5);
      tkohta% = htaulu%(i%)
      WHILE tkohta% <> 0
         PRINT " => ("; ttaulu$(tkohta%, 0); ", "; ttaulu$(tkohta%, 1); ")";
         tkohta% = ltaulu%(tkohta%)
      WEND
      PRINT
   END IF
NEXT

FUNCTION HAE$ (avain$)
   harvo% = LASKE(avain$)
   tkohta% = htaulu%(harvo%)
   WHILE tkohta% <> 0
      IF ttaulu$(tkohta%, 0) = avain$ THEN
         HAE$ = ttaulu$(tkohta%, 1)
         EXIT FUNCTION
      END IF
      tkohta% = ltaulu%(tkohta%)
   WEND
END FUNCTION

FUNCTION LASKE% (mj$)

   FOR i% = 1 TO LEN(mj$)
      m% = ASC(LCASE$(MID$(mj$, i%, 1))) - ASC("a") + 1
      s% = s% + m%
   NEXT
   LASKE% = s% MOD 100
END FUNCTION

SUB LISAA (avain$, tieto$)
   harvo% = LASKE(avain$)
   tmaara% = tmaara% + 1
   ttaulu$(tmaara%, 0) = avain$
   ttaulu$(tmaara%, 1) = tieto$
   tkohta% = htaulu%(harvo%)
   IF tkohta% = 0 THEN
      htaulu%(harvo%) = tmaara%
   ELSE
      WHILE ltaulu%(tkohta%) <> 0
         tkohta% = ltaulu%(tkohta%)
      WEND
      ltaulu%(tkohta%) = tmaara%
   END IF
END SUB