Tehtävä:
Hajautustaulun muistinkäyttö

Lyhyt MathCheck-ohje (uuteen välilehteen)

Hajautus­taulu (hash table) on erittäin tehokas tieto­rakenne silloin, kun tietoja tarvitsee lisätä, poistaa ja etsiä avaimen perusteella, mutta ei tarvitse esimerkiksi selata suuruus­järjestyksessä. Hajautus­tauluun kannattaa tallettaa esimerkiksi puhelin­luettelo, josta etsitään puhelin­numeroita nimien perusteella, mutta ei toisinpäin. (Toisinpäin etsimistä varten voi olla toinen hajautus­taulu.) Tällöin avaimena on nimi. Hyvin suunniteltu hajautus­taulu on erittäin nopea eikä tuhlaa muistia. Tässä tehtä­vässä tarkastellaan hajautus­taulun muistin­kulutusta.

Hajautustauluesimerkki Oheinen kuva esittää ha­jau­tus­taulua. Siinä on tau­luk­ko, jonka alkiot ovat osoit­timia. Osoit­timesta al­kaa linki­tetty lista, jonka kukin tietue sisältää yhden hyöty­kuorman, siis esimer­kiksi yhden nimen ja puhelin­numeron. Kuvassa hyöty­kuormana on lukuja. Tietueessa on myös osoitin listan seuraavaan alkioon.

Lista, johon kukin hyöty­kuorma sijoitetaan, valitaan hajautus­funktion avulla. Se ottaa avaimen ja tuottaa luvun väliltä `0,``...,``M-1`, missä `M` on taulukon koko ja taulukkoa indeksoidaan nollasta alkaen. Hajautusfunktio pyritään valitsemaan siten, että eri avaimet jakautuisivat mahdollisimman tasaisesti eri listoihin. Tällä tavoitellaan sitä, että pisin lista olisi mahdollisimman lyhyt. Hajautus­taulu on sitä hitaampi, mitä enemmän on pitkiä listoja ja mitä pitempia ne ovat. Hyvän hajautus­funktion suunnit­telu vaatii taitoa. Emme käsittele sitä tässä yhteydessä tämän enempää, mutta mainittakoon, että usein hajautus­funktioissa hyödyn­netään modulaarista aritme­tiikkaa.

Mitä suurempi taulukko valitaan, sitä lyhyempiä listoista keski­määrin tulee, mutta sitä enemmän muistia taulukko itse vie.

Nykyaikaisissa tietokoneissa on tavallista, että tällaisissa tilanteissa muistia annetaan 8 tavua kerrallaan. Siksi oletamme, että osoitin vie 8 tavua ja yksi hyöty­kuorma (eli esimerkiksi yksi nimi ja yksi puhelin­numero) vie `8h` tavua. Hajautus­tauluun on talletettava `n` hyöty­kuormaa.

Kirjoita lausekkeet, jotka kertovat muistin käytön `n`:n, `M`:n ja/tai `h`:n funktiona.

Taulukko kuluttaa muistia tavua.
Yksi listan alkio kuluttaa tavua.
Listat kuluttavat yhteensä tavua.
Kaikkiaan muistia kuluu tavua.
tai

Jos listan keskimääräinen pituus on `p`, niin `M =` ja muistia kuluu kaikkiaan (ilmaistuna muiden muuttujien kuin `M` avulla) tavua.
tai

Klikkaamalla nappia saat käyrän, joka esittää muistin kulutusta `p`:n funktiona muiden muuttujien realistislla arvoilla `n` = 100 000 ja `h` = 3.
tai

Käyrän perusteella vaikuttaa siltä, että
On tärkeää, että `p` on mahdollisimman pieni.
`p` ei saa olla pieni.
Ei ole paljoa merkitystä, onko `p` pieni vai keskisuuri.
On tärkeää, että `p` on mahdollisimman suuri.
`p` ei saa olla suuri.
Ei ole paljoa merkitystä, onko `p` keskisuuri vai suuri.
tai

Kaiken tähän­astisen tiedon valossa paras valinta `p`:n arvoksi on
pieni
keskisuuri
suuri
tai

Ei ole olemassa selvää rajaa sille, mitkä `p`:n arvot ovat pieniä, mitkä keski­suuria ja mitkä suuria. Koska hajautus­funktion laskenta vie oman aikansa, nopeuden kannalta hyviä ovat ainakin ne `p`:n arvot, joille (kirjoita ≤ tai ≥). Koska muistin kulutus ei voi olla negatiivinen ja koska 0 tavua vievä hyöty­kuorma ei voi sisältää mitään hyödyllistä, voimme olettaa, että .
tai

Olettamalla mahdollisimman pieni hyöty­kuorma ja sijoit­tamalla `p=2` saadaan muistin kulutukseksi `n`:n funktiona tavua. Muistin kulutus saadaan mini­moitua (ja nopeus pilattua) valitsemalla `p =` . Muistia kuluu tällöin (olettamalla nytkin mahdollisimman pieni hyöty­kuorma) tavua. Edellinen on alle % enemmän kuin jälkimmäinen (valitse mahdolli­simman tiukka luku). Näin pieni muistin lisäys on yleensä varaa maksaa, kun vasti­neeksi saadaan valtava parannus nopeudessa. Jos hyöty­kuormaa on enemmän, on muistin lisä­kulutus prosentteina vielä pienempi, koska taulukon suhteellinen osuus muistin kokonais­määrästä pienenee.
tai

Jos listojen keskipituus `p = 1/2` ja hyötykuorma yhä järkevässä minimissään, niin muistia kuluu tavua. Se on alle % enemmän kuin muistin kulutus silloin, kun listoja on vain yksi (valitse mahdolli­simman tiukka luku). Tämäkin muistin lisäys on yleensä hyväksyt­tävissä, ja nytkin lisä­kulutus prosentteina pienenee, jos hyöty­kuormaa on enemmän.
tai

Voidaan siis varsin huoletta antaa `p`:n liikkua välillä `1/2 <= p <= 2`. Muutkin `p`:n arvot voivat olla käyttö­kelpoisia riippuen mm. `h`:n arvosta, hajautus­funktion laskemiseen kuluvasta ajasta ja siitä, kuinka huolellisesti suoritus­kyky tarvitsee optimoida.