Hakurakenne

**Hakurakenne** eli **assosiaatiotaulu** () eli **hakemisto** 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

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

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.

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. 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ä
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++
C++:n standardimallikirjastossa on säiliöluokkia kuten `std::map`, joka on tyypillisesti toteutettu tasapainotettuna binäärihakupuuna. Standardi velvoittaa, että indeksointi voidaan tehdä ajassa *O*(log *n*).

```cpp
#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
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.

```lua
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
Pythonissa on sisäänrakennettu assosiaatiotaulu, josta käytetään sanaa *dictionary* (`dict`), sanakirja.

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


## Katso myös
* Punamusta puu

### Muita abstrakteja tietotyyppejä
* Jono
* Säiliö
* Pino
* Prioriteettijono

## Lähteet
* 

* 

### Viitteet

## Aiheesta muualla
* TRAKLA2: Hakurakenteet