Kurssiviikko 12

Itseopiskelu¶

Viikon aihe: Hajautustaulut

Aiheiden opetusvideot ja kalvot:

Hajautustaulut¶

Kysymys 1

Miten hakuavainta käytetään hajautustaulun yhteydessä?

Hajautustaulun oletustila on, että se on lukittu, toisin sanoen hajautustaulun alkioita ei voi käyttää. Hakuavaimella voimme avata hajautustaulun lukituksen.

Hajautustaulu on käytännössä vain vektori ja kuhunkin paikkaan (tai indeksiin) voidaan tallentaa tietueen. Hakuavain on vain mahtipontinen synonyymi vektorin indeksille.

Tyypillisesti hajautustaulu sisältää useita hakuavaimia, joista jokainen toistetaan. Siksi hajautustaulussa on kaksi paikkaa (tai ämpäriä), jotka sisältävät saman hakuavaimen. Hajautustaulun käyttämiseksi on etsittävä kaksi paikkaa, jotka sisältävät saman hakuavaimen.

Yksikäsitteinen hakuavain liittyy jokaiseen alkioon, joka on tallennettu jonnekin hajautustauluun. Hakuavaimen avulla voidaan löytää alkion sijainnin ja siten käyttää alkion sisältöä.

Kysymys 2

Oletetaan, että halutaan tallentaa hajautustauluun kaksi hakuavainta \(k1\) ja \(k2\) ja niihin liittyvät tietueet. Oletetaan, että \(k1\) tallennetaan ennen hakuavainta \(k2\). Jos \(k1\) ja \(k2\) osoittavat samaan ämpäriin, miten tämä tilanne hoidetaan ketjutetussa hajautuksessa?

Jokaiseen ämpäriin on liitetty tietorakenne, yleensä linkitetty lista. Hakuavaimet \(k1\) ja \(k2\) ja niihin liittyvät tietueet tallennetaan molemmat jonnekin tähän tietorakenteeseen.

Kun hakuavain \(k2\) ja siihen liittyvä tietue on tarkoitus tallentaa, luodaan kokonaan uusi tyhjä hajautustaulu, johon tallennetaan vain hakuavain \(k2\). Hakuavain \(k1\) pysyy tallennettuna vanhaan hajautustauluun.

Ketjutetussa hajautuksessa käytetty hajautusfunktio muuttaa toistuvasti hakuavaimen \(k2\) uudeksi arvoksi, kunnes se löytää tyhjän ämpärin. Sitten se tallentaa uuden hakuavaimen \(k2\) ja sen tietueen ja palauttaa uuden \(k2\) käyttäjälle.

Koska ämpäri, johon \(k2\) osoittaa ei ole tyhjä, hajautustaulusta etsitään tyhjää ämpäriä, johon voidaan tallentaa \(k2\).

Kysymys 3

Jokaiseen ämpäriin on liitetty tietorakenne, yleensä linkitetty lista. Hakuavaimet \(k1\) ja \(k2\) ja niihin liittyvät tietueet tallennetaan molemmat jonnekin tähän tietorakenteeseen.

Suljetussa hajautuksessa käytetty hajautusfunktio muuttaa toistuvasti hakuavaimen \(k2\) uudeksi arvoksi, kunnes se löytää tyhjän ämpärin. Sitten se tallentaa uuden hakuavaimen \(k2\) ja sen tietueen ja palauttaa uuden \(k2\) käyttäjälle.

Koska ämpäri, johon \(k2\) osoittaa ei ole tyhjä, hajautustaulusta etsitään tyhjää ämpäriä, johon voidaan tallentaa \(k2\).

Kysymys 4

Mitkä seuraavista ovat hyvän hajautusfunktion ominaisuuksia? (Enemmän kuin 1 ominaisuus voi olla oikea.)

Se jakaa hakuavaimet tasaisesti kaikkien ämpäreiden kesken.

Se tarjoaa täsmälleen kaksi erilaista ämpäriehdokasta kullekin hakuavaimelle.

Se käyttää kaikkia hakuavaimessa annettuja tietoja.

Se osoittaa aina kaikki samanpituiset hakuavaimet samaan ämpäriin.

Sen käyttö johtaa aina siihen, että vähintään yksi ämpäri on tyhjä.

Se voidaan laskea nopeasti, joten sen laskenta pitäisi olla vakioaikainen (\(O(1)\)).

Kysymys 5

Oletetaan, että käytetään STL:n std:unordered_map-säiliötä. Missä seuraavista tilanteista on muodostettava oma hajautusfunktio?

Kun hakuavaimet, joita käytetään, ovat kaikki std:string -tyyppiä.

Kun ämpäreiden lukumäärä on pariton.

Kun käytettävät hakuavaimet ovat kaikki jotain struct-tyyppiä, jonka käyttäjä on itse määritellyt.

Kun ollaan varma, että uudelleenhajautus on tehtävä jossain vaiheessa.

Kysymys 6

Uudelleenhajautus on välttämätöntä, kun …

vähintään puolet ämpäreistä on tyhjiä

täyttöaste on suurempi kuin jokin hyväksyttävä yläraja

hakuavaiten koot kasvavat liian suuriksi

ainakin yksi ämpäri alkaa vuotaa

Kysymys 7

Oletetaan, että käytetään hajautustaulua, jossa on ketjutettu hajautus. Mikä on tällaisen hajautustaulun täyttöaste?

tallennettujen alkioiden lukumäärä jaettuna käytettävissä olevien ämpäreiden kokonaismäärällä

käytettävissä olevien ämpäreiden kokonaismäärä jaettuna tallennettujen alkioiden lukumäärällä

suurin lukumäärä alkioita , jotka on tallennettu yhteen ämpäriin

tyhjien ämpäreiden lukumäärä jaettuna käytettävissä olevien ämpäreiden kokonaismäärällä

Kysymys 8

Oletetaan, että käytetään hajautustaulua, jossa on ketjutettu hajautus. Oletetaan, että halutaan etsiä hakuavainta \(k\) hajautustaulusta. Mikä on suoritusaajan tehokkuuden kannalta pahin mahdollinen tilanne tälle etsimistoiminnolle?

Ämpäri, johon hajautusfunktio osoittaa hakuavaimen \(k\), on tyhjä.

Kaikki hajautustaulussa tällä hetkellä tallennetut hakuavaimet ovat osoitettu samaan ämpäriin ja hajautusfunktio osoittaa myös hakuavaimen \(k\) tähän samaan ämpäriin.

On käytävä kaikkien hajautustaulun ämpäreiden läpi, jotta löydetään, mihin ämpäriin hajautusfunktio on tallennettu.

Hajautustauluun ei ole tällä hetkellä tallennettu yhtään hakuavaimia, joten on käytävä kaikkien ämpäreiden läpi, jotta voidaan varmistaa, että ne ovat kaikki tyhjiä.

Kysymys 9

Oletetaan, että käytetään hajautustaulua, jossa on ketjutettu hajautus ja hajautusfunktio jakaa hakuavaimet hyvin tasaisesti kaikkien ämpäreiden kesken. Kun määritellään, milloin uudelleenhajautus tehdään, on asetettava täyttöasteelle yläraja. Tämän ylärajan arvo on kompromissi, minkä kahden asian välillä?

kuinka usein uudelleenhajautus on tehtävä ja hajautusfunktion tehokkuus

yhden hakuoperaation suorittamiseen keskimäärin kuluva aika ja yhden poisto-operaation suorittamiseen keskimäärin kuluva aika

ämpäreihin tarvittavan muistin kokonaismäärä ja yhden haku- tai poisto-operaation suorittamiseen keskimäärin kuluva aika

kuinka paljon uutta muistia tarvitaan uudelleenhajautuksessa ja kuinka usein uudelleenhajautus on tehtävä

Kysymys 10

Mikä seuraavista väittämistä on tarkin hajautustaulun yhden hakuoperaation tehokkuuden suhteen?

Kun hajautusfunktio jakaa hyvin tasaisesti hakuavaimet ämpäreiden kesken, hakuoperaation iso-O tehokkuus on vakioaikainen.

Riippumatta siitä, kuinka hyvin hajautusfunktio jakaa hakuavaimet ämpäreiden kesken, hakuoperaation iso-O tehokkuus on vakioaikainen.

Kun hajautusfunktio jakaa hyvin tasaisesti hakuavaimet ämpäreiden kesken, hakuoperaation amortisoitu iso-O tehokkuus on vakioaikainen.

Riippumatta siitä, kuinka hyvin hajautusfunktio jakaa hakuavaimet ämpäreiden kesken, hakuoperaation iso-O tehokkuus on lineaarinen ämpäreiden lukumäärän suhteen.

Lisäinformaatiota aiheesta:

Viikko12 - Sanasto

Viikkoharjoitusten palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Kurssiviikko 12¶

Itseopiskelu¶

Hajautustaulut¶

Hajautustaulujen toteutus¶

Hajautustaulun tehokkuus ja uudelleenhajautus¶

Hajautusfunktiot¶

Hajautustaulut¶

Viikkoharjoitusten palautettavat kotitehtävät¶