Hakurakenne

Hakurakenne eli assosiaatiotaulu (engl. associative array) eli hakemisto[1] on abstrakti tietotyyppi, joka kuvaa avaimia arvoiksi. Kun hakurakenteelle antaa avaimen (esimerkiksi henkilön nimi), se kertoo arvon (puhelinnumero). Sen rajapinta on tyypillisesti:

  • Set(k, v): merkitse avaimen k arvoksi v
  • Lookup(k): hae avaimeen k liitetty arvo
  • Remove(k): poista avain k ja siihen liittyvä arvo
Puhelinluetteloa mallintavassa assosiaatiotaulussa avaimilla (nimet) pääsee käsiksi arvoihin (puhelinnumerot).

Taulukkoa voidaan pitää hakurakenteena, joka sallii avaimiksi vain luonnollisia lukuja.

Hakurakenteen matemaattinen malli on funktio, jonka määrittely- ja maalijoukko ovat numeroituvia. Määrittely- ja maalijoukot vastaavat hakurakenteen avain- ja arvojoukkoja. Assosiaatiotauluja käytetäänkin säilyttämään vaikeasti laskettavan funktion arvoja tietokoneen muistissa.

Toteutus

[muokkaa | muokkaa wikitekstiä]
Linkitetyn listan alkioina on kolmikoita (linkki, avain, arvo), joten se toimii hakurakenteena.

Yksinkertaisinta on käyttää toteutukseen linkitettyä listaa säilömään (avain, arvo)-pareja, jolloin kyselyn asymptoottinen suoritusaika on O(n). Tasapainotetulla hakupuulla päästään aikaan O(log n) ja hajautustaululla keskimääräiseen suoritusaikaan O(1). Ennaltalaskettuja tulosarvoja sisältävää hakutaulua voidaan käyttää ohjelman optimointiin kun laskenta vaatisi enemmän aikaa kuin muistihaku.[2]

Oikeastaan avaimien ja arvojen käsitteleminen erillisenä ei ole välttämätöntä, sillä mihin tahansa haku-, lisäys- ja poisto-operaatiot toteuttavaan tietorakenteeseen voidaan tallentaa (avain, arvo)-pareja.[3] Tällöin parien vertailun on toimittava yksinomaan avaimen perusteella.

Usein sallitaan useiden arvojen tallentaminen samaan avaimeen. Etenkin C++-ohjelmointikielen yhteydessä tätä kutsutaan assosiaatiomonitauluksi (multimap). Joissakin yhteyksissä hakurakenteen rajapintaa on laajennettu tukemaan muitakin operaatioita, kuten seuraajaa (hae löydetystä avaimesta järjestyksessä seuraava) tai aluehakua (range query, hae kaikki avaimet annetulta väliltä).

Tuki ohjelmointikielissä

[muokkaa | muokkaa wikitekstiä]

Ohjelmoinnissa hakurakenteen toteuttavaa tietotyyppiä kutsutaan assosiaatiotauluksi. Koska assosiaatiotaulut ovat hyvin yleiskäyttöisiä, useat ohjelmointikielet tukevat niitä suoraan. Lua-kieli jopa perustuu täysin niiden varaan. Yleisimpiä nimiä assosiaatiotaululle ovat dictionary (sanakirja), map (kuvaus) tai tyypillisen toteutustavan mukaan hash table, hajautustaulu.

C++

[muokkaa | muokkaa wikitekstiä]

C++:n standardimallikirjastossa on säiliöluokkia kuten std::map[4], joka on tyypillisesti toteutettu tasapainotettuna binäärihakupuuna.[5] Standardi velvoittaa, että indeksointi voidaan tehdä ajassa O(log n).[6] 

 #include <string>
 #include <map>

 std::map<std::string, int> taulu;
 taulu["Jussi Virtanen"] = 991234567;
 int nro = taulu["Jussi Virtanen"];

C++11-standardia edeltävässä Technical Report 1 -muistiossa standardikirjastoon on lisätty std::unordered_map, joka toteuttaa assosiaatiotaulun hajautustauluna.

Lua

[muokkaa | muokkaa wikitekstiä]

Luan ainoa sisäänrakennettu tietorakenne on assosiaatiotaulu, jonka avulla tietueet, taulukot ja oliot rakennetaan. Koska assosiaatiotaulut ovat kaikkialla, niistä käytetään vain sanaa table, taulu. 

 taulu = {}
 taulu = {x = 10}
 print(taulu["x"])  -- tulostaa 10
 print(taulu.x)     -- tulostaa 10
 taulukko = { "a", "b", "c", "d" }  -- alkiot saavat automaattisesti avaimet 1, 2, 3 ja 4
 print(taulukko[2]) -- tulostaa "b"

Python

[muokkaa | muokkaa wikitekstiä]

Pythonissa on sisäänrakennettu assosiaatiotaulu, josta käytetään sanaa dictionary, sanakirja. 

 >>> sanakirja = {'map': 'kuvaus', 'lookup': 'haku'}
 >>> print(sanakirja['map'])
 kuvaus

Katso myös

[muokkaa | muokkaa wikitekstiä]

Muita abstrakteja tietotyyppejä

[muokkaa | muokkaa wikitekstiä]

Lähteet

[muokkaa | muokkaa wikitekstiä]
  • Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: Introduction to Algorithms – 2nd ed. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7

Viitteet

[muokkaa | muokkaa wikitekstiä]
  1. ↑ Laaksonen, Antti: Kisakoodarin käsikirja (Sivut 48–49) cs.helsinki.fi. 2018. Viitattu 15.12.2020.
  2. ↑ Chris Wilcox & Michelle Mills Strout & James M. Bieman: Mesa: Automatic Generation of Lookup Table Optimizations (PDF) cs.colostate.edu. Arkistoitu 11.8.2017. Viitattu 29.8.2019. (englanniksi)
  3. ↑ Thomas Cormen, Charles Leiserson, Ronald Rivest ja Clifford Stein: Introduction to Algorithms – 2nd ed. s. 197–198. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7
  4. ↑ http://www.cppreference.com/cppmap/
  5. ↑ http://groups.google.fi/group/comp.lang.c++.moderated/browse_thread/thread/13feb73ec4135cf8/ (Arkistoitu – Internet Archive)
  6. ↑ Bjarne Stroustrup: ”17.1.2: Säiliöiden yhteenveto”, C++-ohjelmointi. (2. painos. Alkup. The C++ Programming Language – 3rd. ed) Teknolit/Addison-Wesley, 1997. ISBN 0-201-88954-4

Aiheesta muualla

[muokkaa | muokkaa wikitekstiä]