Teh­tä­vä:
Ha­jau­tus­tau­lun muis­tin­käyt­tö

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Ha­jau­tus­tau­lu (hash table) on erit­täin te­ho­kas tie­to­ra­ken­ne sil­loin, kun tie­to­ja tar­vit­see li­sä­tä, pois­taa ja et­siä avai­men pe­rus­teel­la, mut­ta ei tar­vit­se esi­mer­kik­si se­la­ta suu­ruus­jär­jes­tyk­ses­sä. Ha­jau­tus­tau­luun kan­nat­taa tal­let­taa esi­mer­kik­si pu­he­lin­luet­te­lo, jos­ta et­si­tään pu­he­lin­nu­me­roi­ta ni­mien pe­rus­teel­la, mut­ta ei toi­sin­päin. (Toi­sin­päin et­si­mis­tä var­ten voi ol­la toi­nen ha­jau­tus­tau­lu.) Täl­löin avai­me­na on ni­mi. Hy­vin suun­ni­tel­tu ha­jau­tus­tau­lu on erit­täin no­pea ei­kä tuh­laa muis­tia. Täs­sä teh­tä­väs­sä tar­kas­tel­laan ha­jau­tus­tau­lun muis­tin­ku­lu­tus­ta.

Hajautustauluesimerkki Ohei­nen ku­va esit­tää ha­jau­tus­tau­lua. Sii­nä on tau­luk­ko, jon­ka al­kiot ovat osoit­ti­mia. Osoit­ti­mes­ta al­kaa lin­ki­tet­ty lis­ta, jon­ka ku­kin tie­tue si­säl­tää yh­den hyö­ty­kuor­man, siis esi­mer­kik­si yh­den ni­men ja pu­he­lin­nu­me­ron. Ku­vas­sa hyö­ty­kuor­ma­na on lu­ku­ja. Tie­tuees­sa on myös osoi­tin lis­tan seu­raa­vaan al­kioon.

Lis­ta, jo­hon ku­kin hyö­ty­kuor­ma si­joi­te­taan, va­li­taan ha­jau­tus­funk­tion avul­la. Se ot­taa avai­men ja tuot­taa lu­vun vä­lil­tä 0, …, M − 1, mis­sä M on tau­lu­kon ko­ko ja tau­luk­koa in­dek­soi­daan nol­las­ta al­kaen. Ha­jau­tus­funk­tio py­ri­tään va­lit­se­maan si­ten, et­tä eri avai­met ja­kau­tui­si­vat mah­dol­li­sim­man ta­sai­ses­ti eri lis­toi­hin. Täl­lä ta­voi­tel­laan si­tä, et­tä pi­sin lis­ta oli­si mah­dol­li­sim­man ly­hyt. Ha­jau­tus­tau­lu on si­tä hi­taam­pi, mi­tä enem­män on pit­kiä lis­to­ja ja mi­tä pi­tem­piä ne ovat. Hy­vän ha­jau­tus­funk­tion suun­nit­te­lu vaa­tii tai­toa. Em­me kä­sit­te­le si­tä täs­sä yh­tey­des­sä tä­män enem­pää, mut­ta mai­nit­ta­koon, et­tä usein ha­jau­tus­funk­tiois­sa hyö­dyn­ne­tään mo­du­laa­ris­ta arit­me­tiik­kaa.

Mi­tä suu­rem­pi tau­luk­ko va­li­taan, si­tä ly­hyem­piä lis­tois­ta kes­ki­mää­rin tu­lee, mut­ta si­tä enem­män muis­tia tau­luk­ko it­se vie.

Ny­ky­ai­kai­sis­sa tie­to­ko­neis­sa on ta­val­lis­ta, et­tä täl­lai­sis­sa ti­lan­teis­sa muis­tia an­ne­taan 8 ta­vua ker­ral­laan. Sik­si ole­tam­me, et­tä osoi­tin vie 8 ta­vua ja yk­si hyö­ty­kuor­ma (eli esi­mer­kik­si yk­si ni­mi ja yk­si pu­he­lin­nu­me­ro) vie 8h ta­vua. Ha­jau­tus­tau­luun on tal­le­tet­ta­va n hyö­ty­kuor­maa.

Kir­joi­ta lau­sek­keet, jot­ka ker­to­vat muis­tin käy­tön n:n, M:n ja/tai h:n funk­tio­na.
Tau­luk­ko ku­lut­taa muis­tia ta­vua.
Yk­si lis­tan al­kio ku­lut­taa ta­vua.
Lis­tat ku­lut­ta­vat yh­teen­sä ta­vua.
Kaik­kiaan muis­tia ku­luu ta­vua.
tai

Jos lis­tan kes­ki­mää­räi­nen pi­tuus on p, niin M = ja muis­tia ku­luu kaik­kiaan (il­mais­tu­na mui­den muut­tu­jien kuin M avul­la) ta­vua.
tai

Klik­kaa­mal­la nap­pia saat käy­rän, jo­ka esit­tää muis­tin ku­lu­tus­ta p:n funk­tio­na mui­den muut­tu­jien rea­lis­ti­sil­la ar­voil­la n = 100 000 ja h = 3.
tai

Käy­rän pe­rus­teel­la vai­kut­taa sil­tä, et­tä
On tär­keää, et­tä p on mah­dol­li­sim­man pie­ni.
p ei saa ol­la pie­ni.
Ei ole pal­joa mer­ki­tys­tä, on­ko p pie­ni vai kes­ki­suu­ri.
On tär­keää, et­tä p on mah­dol­li­sim­man suu­ri.
p ei saa ol­la suu­ri.
Ei ole pal­joa mer­ki­tys­tä, on­ko p kes­ki­suu­ri vai suu­ri.
tai

Kai­ken tä­hän­as­ti­sen tie­don va­los­sa pa­ras va­lin­ta p:n ar­vok­si on
pie­ni
kes­ki­suu­ri
suu­ri
tai

Ei ole ole­mas­sa sel­vää ra­jaa sil­le, mit­kä p:n ar­vot ovat pie­niä, mit­kä kes­ki­suu­ria ja mit­kä suu­ria. Kos­ka ha­jau­tus­funk­tion las­ken­ta vie oman ai­kan­sa, no­peu­den kan­nal­ta hy­viä ovat ai­na­kin ne p:n ar­vot, joil­le (kir­joi­ta <= tai >=). Kos­ka muis­tin ku­lu­tus ei voi ol­la ne­ga­tii­vi­nen ja kos­ka 0 ta­vua vie­vä hyö­ty­kuor­ma ei voi si­säl­tää mi­tään hyö­dyl­lis­tä, voim­me olet­taa, et­tä .
tai

Olet­ta­mal­la mah­dol­li­sim­man pie­ni hyö­ty­kuor­ma ja si­joit­ta­mal­la p = 2 saa­daan muis­tin ku­lu­tuk­sek­si n:n funk­tio­na ta­vua. Muis­tin ku­lu­tus saa­daan mi­ni­moi­tua (ja no­peus pi­lat­tua) va­lit­se­mal­la p = . Muis­tia ku­luu täl­löin (olet­ta­mal­la nyt­kin mah­dol­li­sim­man pie­ni hyö­ty­kuor­ma) ta­vua.
tai

Juu­ri las­ke­tuis­ta muis­tin ku­lu­tuk­sis­ta edel­li­nen on al­le % enem­män kuin jäl­kim­mäi­nen (va­lit­se mah­dol­li­sim­man tiuk­ka lu­ku). Näin pie­ni muis­tin li­säys on yleen­sä va­raa mak­saa, kun vas­ti­neek­si saa­daan val­ta­va pa­ran­nus no­peu­des­sa. Jos hyö­ty­kuor­maa on enem­män, on muis­tin li­sä­ku­lu­tus pro­sent­tei­na vie­lä pie­nem­pi, kos­ka tau­lu­kon suh­teel­li­nen osuus muis­tin ko­ko­nais­mää­räs­tä pie­ne­nee.
tai

Jos lis­to­jen kes­ki­pi­tuus p =
1
2
ja hyö­ty­kuor­ma on yhä jär­ke­väs­sä mi­ni­mis­sään, niin muis­tia ku­luu ta­vua. Se on al­le % enem­män kuin muis­tin ku­lu­tus sil­loin, kun lis­to­ja on vain yk­si (va­lit­se mah­dol­li­sim­man tiuk­ka lu­ku). Tä­mä­kin muis­tin li­säys on yleen­sä hy­väk­syt­tä­vis­sä, ja nyt­kin li­sä­ku­lu­tus pro­sent­tei­na pie­ne­nee, jos hyö­ty­kuor­maa on enem­män.
tai

Voi­daan siis var­sin huo­let­ta an­taa p:n liik­kua vä­lil­lä
1
2
≤ p ≤ 2. Muut­kin p:n ar­vot voi­vat ol­la käyt­tö­kel­poi­sia riip­puen mm. h:n ar­vos­ta, ha­jau­tus­funk­tion las­ke­mi­seen ku­lu­vas­ta ajas­ta ja sii­tä, kuin­ka huo­lel­li­ses­ti suo­ri­tus­ky­ky tar­vit­see op­ti­moi­da.