3.4 Hashing

Hashtabeller med kjeding, kollisjoner, lastfaktor og hva som gjør en hashfunksjon god — et voksende tema (3/3 i 2022–23).

45 min

8 oppgaver

Hashing

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

1.1Asymptotisk notasjon — de fem symbolene

Hashing er temaet som vokser. Det er talt i 7 av de 17 settene i
grunnlaget (41 %) — men det er med i alle tre settene fra 2022 og 2023.
Prioriteten i pensumoversikten er «kjenne til», og det står ved lag, men gitt
trenden bør du prioritere det høyere enn prosenten alene tilsier. Dette er 45
minutter som med god margin kan gi poeng.

Temaet testes i tre sjangre, og alle tre trenes her:

- Sjanger D — definisjon «med egne ord», altså at du skriver én presis
setning med hovedpoenget først. «Hva er lastfaktoren i en hashtabell?»
- Sjanger E — kjøretidskunnskap, altså at du oppgir det strammeste
uttrykket, med \Theta der grensen er tett og O der bare den øvre er vist.
- Sjanger F — «stemmer dette?», altså at du svarer ja eller nei først, og
så begrunner med én setning. Dette er hashingens hovedsjanger, og fella er
nesten alltid den samme: er søk i en hashtabell «alltid raskt»?

Det ene du må ha helt presist: søk i en hashtabell med kjeding er
$\Theta(1+\alpha)$ forventet under enkel uniform hashing, og $\Theta(n)$ i
verste tilfelle. Skriver du «garantert $O(1)$ », har du svart feil på det
spørsmålet som stilles oftest.

Slik er kapitlet lagt opp (45 min):

Del	Innhold	Tid
1	Hashtabellen, kollisjoner og kjeding	ca. 15 min
2	Lastfaktoren og hva søk faktisk koster	ca. 15 min
3	Hva som gjør en hashfunksjon god	ca. 15 min

Forkunnskaper

- kap. 1.1 — de asymptotiske symbolene. Du trenger
særlig skillet mellom $\Theta$ (tett grense, både over og under) og $O$ (bare
øvre grense), og hva det vil si at noe er en forventet kjøretid framfor en
garantert.

Dette sto der: $\Theta(g(n))$ brukes når du har vist at kjøretiden både er minst
og høyst av størrelsesorden $g(n)$ , mens $O(g(n))$ bare lover et tak. En
«forventet» kjøretid er et gjennomsnitt over noe tilfeldig — her over hvordan
nøklene fordeler seg — og sier ingenting om hva som skjer i det verste tilfellet.

Trenger du en mykere inngang til $O$ -notasjonen først, ligger den i
Algoritmedefinisjon, pseudokode og kompleksitet (Big-O).

Du trenger ikke hauger eller søketrær for dette kapitlet. Hashtabellen er en
helt egen struktur, og den sammenlignes med søketreet først helt til slutt.

Notasjons- og pseudokodeliste

Hashtabellen, kollisjoner og kjeding (~15 min)

Et idrettslag låner ut nøkkelbrikker til klubbhuset. Hver brikke har et
femsifret nummer, og i løpet av et år er det kanskje tre hundre brikker i
omløp. Skal du kunne slå opp «hvem har brikke 40 231?» raskt, har du to
åpenbare, dårlige alternativer.

Du kan lage én plass for hvert mulige brikkenummer. Det gir oppslag på ett
øyeblikk, men krever hundre tusen plasser for tre hundre brikker. Eller du kan
legge brikkene i en liste og lete gjennom den. Det tar minimalt med plass, men
oppslaget koster $\Theta(n)$ .

Hashtabellen er kompromisset: du velger et håndterbart antall plasser, og
lar en regel bestemme hvilken plass hver nøkkel hører hjemme i. Regelen er
hashfunksjonen. Med tre hundre brikker holder det med for eksempel 401 plasser —
og oppslaget blir raskt likevel.

Hashtabell

m

Hashfunksjon

h

Kollisjon

h(k_1) = h(k_2)

Kjeding

O(1)

📜Pseudokode-kontrakt: `Chained-Hash-Insert` og `Chained-Hash-Search`

Antagelser om representasjon. T er en tabell med

m

plasser, indeksert
T[0] til T[m-1]. Hver plass peker til en lenket liste, som er tom i
utgangspunktet. Hashfunksjonen h gir et heltall i 0..m-1 for enhver nøkkel.

Prebetingelse: T er en gyldig hashtabell med kjeding. Postbetingelse for
innsetting: x ligger fremst i lista T[h(x.key)], og ingen andre elementer
er flyttet.

Chained-Hash-Insert(T, x)
  Input:  hashtabell T med kjeding, element x med noekkel x.key
  Output: x lagt inn fremst i lista T[h(x.key)]
  sett x fremst i den lenkede lista T[h(x.key)]
  Kjoretid: O(1)

Chained-Hash-Search(T, k)
  Input:  hashtabell T med kjeding, noekkel k
  Output: elementet med noekkel k, eller NIL
  i = h(k)
  for hvert element y i den lenkede lista T[i]
      if y.key == k
          return y
  return NIL
  Kjoretid: Theta(1 + alfa) forventet, Theta(n) verste

Grunnideen i én setning: hashfunksjonen gjør om et søk i hele datamengden til
et søk i én enkelt kjede, og alt henger på hvor korte de kjedene er.

Kjøretid: innsetting er $O(1)$ fordi den ikke leter — den legger elementet
fremst uten å sjekke om nøkkelen finnes fra før. Søk koster én hashutregning
pluss gjennomgangen av kjeden, altså $\Theta(1+\alpha)$ forventet under enkel
uniform hashing, og $\Theta(n)$ når alle $n$ nøklene ligger i samme bøtte.

✏️Eksempel 1: Seks nøkler inn i en tabell med sju bøtter

En hashtabell har $m = 7$ bøtter og bruker divisjonsmetoden $h(k) = k \bmod 7$ .
Sett inn nøklene 26, 13, 40, 9, 18, 31 i denne rekkefølgen.

a) Hvordan ser tabellen ut etterpå?
b) Hva er lastfaktoren?
c) Hvor mange sammenligninger koster et mislykket søk etter nøkkelen 5?

a) Vi regner ut

h(k)

for hver nøkkel og legger den fremst i sin bøtte.

Steg	Nøkkel `k`	`h(k) = k mod 7`	Kollisjon?	Bøtta etter innsettingen
1	26	26 mod 7 = 5	nei	`26`
2	13	13 mod 7 = 6	nei	`13`
3	40	40 mod 7 = 5	ja (1 element der fra før)	`40 -> 26`
4	9	9 mod 7 = 2	nei	`9`
5	18	18 mod 7 = 4	nei	`18`
6	31	31 mod 7 = 3	nei	`31`

Tabellen til slutt:

T[0]: tom
T[1]: tom
T[2]: 9
T[3]: 31
T[4]: 18
T[5]: 40 -> 26
T[6]: 13

\alpha = n/m = 6/7 \approx 0{,}86

.
c)

h(5) = 5

, så søket går til bøtte 5. Der ligger 40 og 26. Begge må
sammenlignes med 5 før søket kan svare at nøkkelen ikke finnes: to
sammenligninger.
Legg merke til rekkefølgen i bøtte 5. Nøkkelen 40 kom sist, men ligger

først. Chained-Hash-Insert legger alltid det nye elementet fremst, fordi det er

$O(1)$ — å legge det bakerst ville krevd at man gikk gjennom hele lista.

Legg merke til hva et mislykket søk koster. Det er dyrere enn et vellykket

søk i gjennomsnitt, fordi det alltid må gå gjennom hele kjeden. Et vellykket
søk kan stoppe underveis.

📝Oppgave 1

Eksamensnivå, sjanger C

En hashtabell med kjeding har $m = 5$ bøtter og bruker $h(k) = k \bmod 5$ . Sett
inn nøklene 14, 29, 7, 20, 33, 11 i denne rekkefølgen.

a) Oppgi innholdet i hver av de fem bøttene.
b) Hva er lastfaktoren?

Lastfaktoren og hva et søk faktisk koster (~15 min)

Hashtabellens hastighet er ikke en egenskap ved strukturen alene. Den avhenger
av hvor full tabellen er, og av hvor jevnt nøklene har fordelt seg. Det første
måles av lastfaktoren.

Lastfaktor

\alpha = n/m

📜Forventet søketid med kjeding

Antakelsen kalles enkel uniform hashing: hver nøkkel er like sannsynlig
å hashe til hver av de

m

bøttene, uavhengig av hvor de andre nøklene havner.
Dette er en antakelse om nøklene og hashfunksjonen sammen — ikke noe algoritmen
kan garantere.

Under den antakelsen er den forventede lengden på en kjede lik lastfaktoren
$\alpha = n/m$ . Et søk koster da

$\Theta(1 + \alpha),$

der leddet 1 er hashutregningen og oppslaget i tabellen, som du betaler uansett,
og leddet $\alpha$ er gjennomgangen av kjeden.

Konsekvensen er den viktigste setningen i kapitlet: holder du $\alpha$
begrenset av en konstant — for eksempel ved å velge $m$ slik at
$n = O(m)$ — blir forventet søketid $\Theta(1)$ . Det er nettopp derfor
hashtabeller er raske i praksis.

Verste tilfelle er noe helt annet. Havner alle $n$ nøklene i samme bøtte, er
tabellen redusert til én lenket liste, og et søk koster $\Theta(n)$ . Det er ikke
et teoretisk grensetilfelle: velger du $m = 6$ og alle nøklene er delelige med 6,
skjer det.

Derfor: søk i en hashtabell med kjeding er $\Theta(1+\alpha)$ forventet
og $\Theta(n)$ i verste tilfelle. Uttrykket «garantert $O(1)$ » er galt, og
det er den feilen dette temaet oftest tester.

✏️Eksempel 2: Samme antall nøkler, mye dårligere fordeling

En hashtabell har $m = 9$ bøtter og $h(k) = k \bmod 9$ . Sett inn nøklene
18, 27, 45, 13, 36, 22, 31.

a) Hvordan ser tabellen ut?
b) Hva er lastfaktoren, og hva koster et mislykket søk etter nøkkelen 40?
c) Hva forteller dette om forskjellen mellom forventet og verste tilfelle?

Steg	Nøkkel `k`	`h(k) = k mod 9`	Kollisjon?	Bøtta etter innsettingen
1	18	18 mod 9 = 0	nei	`18`
2	27	27 mod 9 = 0	ja (1 element der fra før)	`27 -> 18`
3	45	45 mod 9 = 0	ja (2 elementer der fra før)	`45 -> 27 -> 18`
4	13	13 mod 9 = 4	nei	`13`
5	36	36 mod 9 = 0	ja (3 elementer der fra før)	`36 -> 45 -> 27 -> 18`
6	22	22 mod 9 = 4	ja (1 element der fra før)	`22 -> 13`
7	31	31 mod 9 = 4	ja (2 elementer der fra før)	`31 -> 22 -> 13`

T[0]: 36 -> 45 -> 27 -> 18
T[1]: tom
T[2]: tom
T[3]: tom
T[4]: 31 -> 22 -> 13
T[5]: tom
T[6]: tom
T[7]: tom
T[8]: tom

\alpha = 7/9 \approx 0{,}78

. Et mislykket søk etter 40 går til bøtte

40 \bmod 9 = 4

, og må gjennom hele kjeden der: tre sammenligninger.
c) Lastfaktoren er lavere enn i Eksempel 1 (

0{,}78

mot

0{,}86

), men
tabellen er klart dårligere. Sju av ni bøtter står tomme, og de to kjedene er
fire og tre lange. Lastfaktoren er et gjennomsnitt, og gjennomsnittet sier
ingenting om hvordan nøklene faktisk har spredt seg.
Hvorfor det gikk galt her. Fire av nøklene er delelige med 9, så de gir alle

$h(k) = 0$ . Med $m = 9$ blir hashfunksjonen dermed helt avhengig av om nøklene

tilfeldigvis har en felles faktor med 9. Det er ikke tilfeldig at anbefalingen er
å velge $m$ som et primtall som ikke ligger nær en potens av 2: da er det

langt færre nøkkelmønstre som kan kollapse på denne måten.

📝Oppgave 2

Eksamensnivå, sjanger C

En hashtabell med kjeding har $m = 8$ bøtter og $h(k) = k \bmod 8$ . Sett inn
nøklene 41, 17, 25, 33, 6, 19 i denne rekkefølgen.

a) Oppgi innholdet i hver bøtte.
b) Hva er lastfaktoren, og hva er den lengste kjeden?
c) Hvor mange sammenligninger koster et mislykket søk etter nøkkelen 12?

📝Oppgave 3

Eksamensnivå, sjanger C…

En hashtabell med kjeding har $m = 6$ bøtter og $h(k) = k \bmod 6$ . Sett inn
nøklene 12, 18, 24, 30, 7.

a) Oppgi innholdet i hver bøtte.
b) Hva koster et mislykket søk etter nøkkelen 42, målt i sammenligninger?
c) Hva er kjøretiden for søk i denne tabellen i verste tilfelle, uttrykt i
$n$ ?

📝Oppgave 4

Eksamensnivå, sjanger C…

En hashtabell med kjeding har $m = 11$ bøtter og $h(k) = k \bmod 11$ . Sett inn
nøklene 52, 19, 41, 30, 63, 8.

a) Oppgi innholdet i hver bøtte.
b) Er dette verstetilfellet for en hashtabell med kjeding og $n = 6$ ? Svar ja
eller nei, og begrunn med én setning.
c) Betyr resultatet at $m = 11$ er et dårlig valg? Begrunn med én setning.

Hva gjør en hashfunksjon god? (~15 min)

Kravene er tre, og de kan alle formuleres i én setning hver. Dette er
definisjonssjangeren i praksis: du blir bedt om å nevne kravene, ikke om å bevise
noe.

Uniform fordeling. Nøklene skal spres jevnt over bøttene, slik at ingen
kjede blir mye lengre enn de andre. Dette er det som gjør antakelsen om enkel
uniform hashing rimelig, og dermed det som gjør $\Theta(1+\alpha)$ til noe du kan
regne med i praksis.

Determinisme. Samme nøkkel må gi samme bøtte hver gang. Uten det kan du
sette inn en nøkkel og aldri finne den igjen. Kravet virker banalt, men det
utelukker enhver hashfunksjon som bruker tilfeldighet eller tid.

Hastighet. Utregningen av $h(k)$ må koste $O(1)$ . Er hashfunksjonen dyrere
enn å gå gjennom en kort kjede, har du tapt det du kom for.

Divisjonsmetoden

h(k) = k \bmod m

Multiplikasjonsmetoden

0..m-1

Typiske feil

- Å påstå at søk i en hashtabell er garantert $O(1)$ . Dette er kapitlets
hovedfelle, og den kommer igjen og igjen i «stemmer dette?»-oppgaver. Riktig
svar er at søk er $\Theta(1+\alpha)$ forventet under enkel uniform
hashing, og $\Theta(n)$ i verste tilfelle. Kontrollen: har du skrevet ordet
«forventet» eller «i gjennomsnitt» i svaret ditt? Hvis ikke, mangler det noe.
- Å blande kjeding med åpen adressering. Med kjeding ligger nøklene i
lenkede lister utenfor selve tabellplassen, og $\alpha$ kan være større enn 1.
Med åpen adressering — den andre hovedstrategien, der en kolliderende
nøkkel i stedet plasseres i en annen ledig bøtte i tabellen — ligger alle
nøklene inne i tabellen, og da må $\alpha \le 1$ . Sier en oppgave «kjeding»,
gjelder det første.
- Å glemme lastfaktorens rolle i svaret. Et svar som bare sier «søk er raskt»
får ikke uttelling. Det er $\alpha$ som styrer, og det er derfor tabellen må
vokse når $n$ vokser.
- Å tro at en lav lastfaktor garanterer korte kjeder. Lastfaktoren er et
gjennomsnitt. Med $m = 6$ og nøklene 12, 18, 24 og 30 er $\alpha$ under 1, mens
den lengste kjeden er fire.
- Å tro at enhver hashfunksjon gir uniform fordeling. Uniformitet er en
antakelse vi gjør for å kunne regne, og et mål når vi designer
funksjonen — ikke noe som følger av at funksjonen er en hashfunksjon.

📝Oppgave 5

Eksamensnivå, sjanger F

Stemmer det at søk i en hashtabell med kjeding alltid er $O(1)$ ?

📝Oppgave 6

Eksamensnivå, sjanger F

Svar ja eller nei på hver av påstandene, og begrunn hver med én setning.

a) Lastfaktoren i en hashtabell med kjeding kan ikke være større enn 1.
b) En hashfunksjon må være deterministisk.
c) Kollisjoner kan unngås helt hvis hashfunksjonen er god nok.

📝Oppgave 7

Eksamensnivå, sjanger D

a) Definer lastfaktoren i en hashtabell.
b) Oppgi forventet søketid for en hashtabell med kjeding, med den antakelsen
som kreves, og verste søketid.

📝Oppgave 8

Eksamensnivå, sjanger E…

To hashtabeller bruker begge kjeding, har begge $m = 6$ bøtter og lagrer begge
fem nøkler. Tabell 1 har nøklene 12, 18, 24, 30, 7; tabell 2 har nøklene
1, 2, 3, 4, 5. Begge bruker $h(k) = k \bmod 6$ .

a) Hva er lastfaktoren i hver av tabellene?
b) Hva er lengste kjede i hver av dem?
c) Stemmer det at to hashtabeller med samme lastfaktor har samme søketid i
verste tilfelle? Svar ja eller nei, og begrunn med én setning.

Kjøretidene, samlet

Operasjon	Forventet	Verste	Krav / egenskap
`Chained-Hash-Insert`	$O(1)$	$O(1)$	legger fremst i kjeden, sjekker ikke om nøkkelen finnes fra før
`Chained-Hash-Search`	$\Theta(1+\alpha)$	$\Theta(n)$	forventningen krever enkel uniform hashing
`Chained-Hash-Delete`	$O(1)$	$O(1)$	forutsetter dobbeltlenket liste og at elementet allerede er funnet
Plassbruk	$\Theta(m+n)$	$\Theta(m+n)$	$m$ bøtter pluss $n$ lagrede nøkler

Til sammenligning: et binært søketre gir

O(h)

på søk, der høyden

h

\Theta(\lg n)

forventet for et tilfeldig bygd tre og

\Theta(n)

i verste
tilfelle — se kap. 3.2. Hashtabellen er raskere i det
typiske tilfellet, men søketreet gir deg noe hashtabellen ikke gir: nøklene i
sortert rekkefølge, i

\Theta(n)

, via Inorder-Tree-Walk. Trenger du orden,

hjelper ingen hashfunksjon deg.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Bøtte

m

Enkel uniform hashing

m

Forventet søketid med kjeding

\Theta(1+\alpha)

Verste søketid med kjeding

\Theta(n)

Åpen adressering

den andre hovedstrategien for kollisjoner, der en kolliderende nøkkel plasseres i en annen ledig bøtte i selve tabellen i stedet for i en liste utenfor. Alle nøklene ligger da inne i tabellen, og lastfaktoren kan derfor ikke overstige 1. Kjeding og åpen adressering skal ikke blandes i et svar.

Mislykket søk

h(k)

Valg av

m

i divisjonsmetoden

m

Hashtabell mot binært søketre

\Theta(1+\alpha)

Hvorfor kollisjoner er uunngåelige

fordi nøkkeluniverset nesten alltid er mye større enn antall bøtter: med flere mulige nøkler enn plasser må minst to nøkler dele plass. En hashtabell er derfor alltid en tabell pluss en kollisjonsstrategi, og påstanden «med en god nok hashfunksjon slipper man kollisjoner» er gal.

Å holde lastfaktoren konstant

n

Sjanger F — «stemmer dette?»

oppgavetypen der du får en påstand og skal avgjøre om den holder. Svarformen er fast: ja eller nei først, deretter én presis setning som begrunner. Hashing er et av temaene som oftest kommer i denne formen, og påstanden handler nesten alltid om at søk skulle være garantert konstant.

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.