Taustoja: Mikä on hajautustaulu? (Epäformaali johdanto)

Taulukko hakurakenteena

Puhutaanpa ensin taulukosta. Taulukko on rakenne, johon voi laittaa haluamaansa dataa tietyn haluamansa indeksin kohdalle. Taulukosta voi vastaavasti hakea tuon tiedon käyttämällä indeksiä.

Kuvitellaan että haluaisimme tehdä tietojärjestelmän tälle kurssille, jonka avulla opiskelijalle voi antaa pisteitä opiskelijanumeroa indeksinä käyttäen. Pistetään opiskelijat taulukkoon - jokainen oman opiskelijanumeronsa kohdalle. Aallolla:lla on käytössä viisinumeroiset opiskelijanumerot, joten kunkin opiskelijan tiedot voisi sijoittaa taulukkoon jossa on satatuhatta paikkaa.

Anteeksi? Kurssillahan on vain parisataa opiskelijaa, joten taulukosta on käytössä vain 0.2%. Ei vaikuta oikein tehokkaalta tilankäytöltä. Toisaalta tiedon kyllä saa nopeasti. Olisiko mahdollista saada viittaus opiskelijaolioon yhä nopeasti, mutta käyttää paljon vähemmän tilaa?

Voisiko opiskelijat vain laittaa taulukkoon peräkkäin järjestykseen opiskelijanumeron mukaan? Tällaisesta järjestetystä taulukosta saa kyllä tiedon suht' nopeasti etsittyä, mutta opiskelijoiden poistaminen ja lisääminen vaatii pahimmillaan kaikkien muiden opiskelijoiden siirtämistä taulukossa.

Hajautus

Hajautuksen idea on ottaa suuri avainavaruus (100000) ja "puristaa" se kasaan niin että tauluun laitettavat alkiot saadaan sijoitettua pienempään tilaan. Vaikka tilaa varaisi 2,5 kertaa tallennettavien alkioiden määrän, olisi tilankäyttö esimerkissämme 200 kertaa tehokkaampaa.

Kuinka avaimet sitten sijoitetaan pienempään tauluun? Yksinkertainen idea voisi olla että opiskelijanumero jaetaan taulukon koolla ja jakojäännös kertoo sijoitettavan alkion paikan.

Jos opiskelijanumerot ovat jakautuneet tasaisesti, jakojäännös levittää kurssilla olijoiden opiskelijanumerot tasaisesti pienemmän taulukon indekseille. On kuitenkin selvää, että useampi alkio tulee kuvautumaan samoille indekseille. Tätä kutsutaan törmäykseksi. Menetelmiä, joilla tämä ratkaistaan on useita. Tässä harjoituksessa tutkittava luokka käyttää kaksoishajautusta. Tässä menetelmässä ensimmäinen kokeiltu paikka lasketaan yhdellä funktiolla ja jos paikka on jo käytössä, niin lasketaan toisella funktiolla arvo jonka välein kokeillaan uudelleen. Esim:

Haku

Kun etsitään alkiota, lasketaan kaavalla paikkoja kunnes vastaan tulee täysin käyttämätön paikka tai oikea alkio löytyy. Matkan varrella voi olla myös merkkejä käytössä olleista paikoista.

Lisäys

Kun sijoitetaan alkioita kelpaa täysin käyttämättömän paikan lisäksi myös aiemmin käytössä ollut paikka. Tällaisia paikkoja syntyy kun alkioita poistetaan hajautusrakenteesta. Jos poistettavan alkion kohdalle ei jäisi mitään merkkiä, ei alkioita etsivä rutiini löytäisi niitä, koska se keskeyttäisi liian aikaisin.

Poisto

Poistaminen on aluksi samanlainen kuin haku. Jos alkio löytyy, laitetaan sen tilalle merkki (Hashable.DELETED) siitä että paikka oli käytössä, jotta hakurutiini pääsee paikan ohi.

Rehash

Jos taulussa oleva käyttämätön tila käy liian vähiin, alkaa taulu toimimaan huonosti. Tällaisessa tilanteessa suoritetaan ns. uudelleenhajautus (rehash), jossa kaikki taulukon alkiot lisätään yksi kerrallaan suurempaan tauluun.

Esimerkki

Sijoitetaan tauluun jossa on 11 paikkaa kolme pupua jotka on numeroitu 30, 49 ja 16. Sijoittamiskaava on place = (number + (k * (1+ number % 7))) % 11) (30 menee paikkaan 8 ja 49 paikkaan 5) nyt pupua 16 lisättäessä kokeillaan ensin varattua paikkaa 5, sitten varattua paikkaa 11 ja vasta lopuksi vapaata paikkaa 0.

Poistetaan nyt pupu numero 30 ja yritetään sitten löytää pupu numero 16. Ylempi allaolevista kuvista esittää kolmannen pupun lisäämisen (kokeillaan paikkoja 5, 8 ja 0), alempi pupun 16 etsimisoperaation (etsitään paikoista (5, 8 ja 0). Poistuneen pupun kohdalla on "haamu".

Lisää tietoa

Paremman käsityksen algoritmin toiminnasta saa kun käy tutkimassa luokan DoubleHash koodia. Koodin pitäisi olla sen verran yksinkertainen että algoritmit pystyy ymmärtämään ylläolevan selostuksen avulla.

Tehokkuudesta

Selityksen perusteella tietorakenteen toiminta voi kuulostaa monimutkaiselta, mutta hajautustaulun lisäys, poisto ja haku ovat kaikki käytännössä erittäin tehokkaita operaatioita. Python tarjoaa kaksi valmista toteutusta: luokat dictionary ja set. Näitä tullaan hyödyntämään seuraavilla harjoituskierroksilla.

Tässä tehtävässä on kaksi osaa:

A) Korjataan DoubleHash-luokan metodi next_prime()

DoubleHash-luokassa on metodi nimeltään next_prime(self, old), joka saatuaan kokonaisluvun laskee uuden kokonaisluvun joka on:

1. Vähintään kaksi kertaa annettua lukua suurempi
2. Alkuluku

rehash()-metodi käyttää tätä metodia laskiessaan koon uudelle, suuremmalle taulukolle.Taulukon koon tulee olla alkuluku, jotta hajautus toimisi virheettä.

Vinkki : alkulukua muulla kuin ykkösellä jaettaessa jakojäännös (%) ei saa olla 0.

B) Testataan kattavasti kaikki DoubleHash-luokan koodi

Testimoduulin runkoon on jo toteutettu kaksi testiä malliksi. Ensimmäinen testaa meneekö yksittäinen rakenteeseen laitettava alkio oikelle paikalle. Toinen testi testaa next_prime-metodia. Tarkoitus on lisätä joukko testejä, jotka testaavat kaikki koodin rivit ja suorittavat if/for/while jne. lauseiden molemmat haarat. ts. jokaisen if-lauseen tulisi olla testatessa ainakin kerran tosi ja ainakin kerran epätosi.

Heti kun olet luonut itsellesi Eclipseen projektin, voit ajaa nämä testit. "Yksittäisen lisäyksen testin" pitäisi mennä läpi(ei tulosta mitään) ja "next_prime:n testin" epäonnistua. Voit nyt toteuttaa next_prime:n ja kokeilla meneekö testi sitten läpi.

Vinkki

Jos ohjelmaa palauttaessasi testaus katkeaa kesken, ohjelmasi joko jäi ikuiseen silmukkaan tai tekee tehtävänsä liian hitaasti kun kokeiltava alkuluku on suuri. Tämä tapahtuu alkuluvun generointikohdassa mm. jos kokeilee läpi kaikki testattavaa lukua pienemmät jakajat.
Vinkki: luvun neliöjuuri riittänee jakajia tutkittaessa, sillä jos luvulla on enemmän kuin 1 tekijä, niin pienin niistä on aina korkeintaan luvun neliöjuuren kokoinen. (neliöjuuren saa esim math.sqrt(luku)-metodilla, muista import math)