3.2 Load-faktor, rehashing og hashmap/-set som verktøy

Load-faktor og når man rehasher, og hashmap/-set som Del 2-verktøyet for O(n)-løsninger.

45 min

6 oppgaver

Load-faktorrehashinghashmap/-set som verktøy

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

3.1Hashtabeller og lukket hashing (linear probing)

Brukes videre i

3.3DRILL — Linear-probing håndkjøring og insert-pseudokode 3.4Søk i pseudokode — binærsøk, finn duplikat og finn par 7.2Drøft to strategier

To temaer i dette kapitlet, og de testes på hver sin måte.

Load-faktor og rehashing kommer som sjanger C — kjøretids- og teorifakta,
altså rene sant/usant-påstander i Del 1. Det faste punktet er at hashverdiene
endrer seg når tabellen utvides, slik at alt må settes inn på nytt. Påstanden
«rehashing kan gjenbruke de gamle indeksene» er usann, og den er en fast
distraktor.

Hashmap og hash-set som verktøy er derimot en Del 2-ferdighet, sjanger I. Det
er dette kapitlet som gir deg lisensen til å skrive «bruk et hash-set» i en
pseudokodebesvarelse og få $O(n)$ forventet der en sortering ville gitt
$O(n \log n)$ . På poengtrappen er det ett helt trinn, og det gjelder på nesten
hvert eneste sett.

Til sammen har temaene 100 % frekvens — 7 av 7 sett.

Prioritet: høyeste. Kapitlet er kort, men det er broen mellom håndkjøringen i
kap. 3.1 og Del 2-oppgavene i
kap. 3.4.

Slik er kapitlet lagt opp (45 min): tre løkker med tidsanslag.

Forkunnskaper

- kap. 3.1 — hashtabellen, $h(k) = k \bmod N$ , lineær
probing og forskjellen på forventet og verste kjøretid. Alt her bygger direkte
på det.
- kap. 2.2 — sortér-og-skann-strategien, som er alternativet
hash-settet skal sammenlignes mot.

Har du brukt en ordbok i et introkurs, kjenner du allerede grensesnittet:
Ordbøker — der er hashmap-en ferdig laget; her ser du hva
den koster.

Notasjons- og pseudokodeliste

Løkke 1 — load-faktoren: hvor full er tabellen? (ca. 12 min)

Klyngedannelsen du så i kap. 3.1 blir raskt verre jo mer
tabellen fylles opp. Med tre nøkler i en tabell på elleve plasser er kollisjoner
sjeldne. Med ti nøkler i den samme tabellen er de nesten uunngåelige, og
probing-sekvensene blir lange.

Målet på hvor full tabellen er, heter load-faktoren:

$\alpha = \frac{n}{N}$

der $n$ er antall lagrede nøkler og $N$ er antall plasser. Er $\alpha = 0{,}5$ ,
er halvparten av plassene i bruk. Er $\alpha = 1$ , er tabellen full, og ingen ny
nøkkel får plass.

Rekkefølgen i brøken er verdt å låse fast: nøkler over plasser. Snur du
brøken, får du et tall over 1 så snart tabellen er mindre enn halvfull, og det
gir ingen mening.

Load-faktor

\alpha = n/N

✏️Eksempel 1: Load-faktor og hva den betyr

En hashtabell har $N = 7$ plasser. Regn ut load-faktoren etter at 4 nøkler er
satt inn, og etter at 6 er satt inn. Hva sier tallene om kjøretiden?

Med 4 nøkler:

\alpha = 4/7 \approx 0{,}571

. Litt over halvparten av
plassene er i bruk.

Med 6 nøkler: $\alpha = 6/7 \approx 0{,}857$ . Bare én plass er ledig.

Hva tallene betyr. Ved $\alpha \approx 0{,}57$ er det fortsatt tre ledige
plasser spredt utover, og en ny nøkkel har god sjanse til å finne plass raskt.
Ved $\alpha \approx 0{,}86$ må en ny nøkkel i verste fall probe seg gjennom nesten
hele tabellen for å finne den ene ledige plassen.

Konkret, fra tabellen i kap. 3.1: der ble fem nøkler
satt inn i en tabell med $N = 7$ , altså $\alpha = 5/7 \approx 0{,}714$ , og
totalkostnaden var 13 prøver for fem innsettinger — 2,6 per innsetting. Hadde
tabellen vært dobbelt så stor, ville de samme fem nøklene hatt langt kortere vei.

Merk hva load-faktoren ikke sier. Den sier ingenting om hvordan nøklene
ligger. En tabell med $\alpha = 0{,}5$ der alle nøklene ligger i én klynge, er
verre enn en med $\alpha = 0{,}7$ der de er spredt. Load-faktoren er et
grovmål — men det er grovmålet implementasjoner faktisk bruker, fordi det er
billig å holde oppdatert.

📝Oppgave 1

(Innstegsoppgave, sjanger C — kjøretids- og teorifakta, altså rene
sant/usant-påstander.) En hashtabell har $N = 16$ plasser og inneholder 12
nøkler.

a) Hva er load-faktoren?
b) Kan load-faktoren i en tabell med lukket hashing bli større enn 1?
c) Sant eller usant: en lav load-faktor garanterer korte probing-sekvenser.

Løkke 2 — rehashing: hele tabellen bygges på nytt (ca. 16 min)

— naturlig pausepunkt —

Når load-faktoren blir for høy, må tabellen utvides. Og her ligger poenget som
har vært et sant/usant-punkt i sett etter sett.

Du kan ikke bare lage et større array og flytte nøklene over på de samme
indeksene.

Grunnen står i hashfunksjonen: $h(k) = k \bmod N$ . Den avhenger av $N$ . Dobler du
tabellen fra 7 til 14, endres alle hashverdier. Nøkkelen 22 hashet til plass
1 da $N = 7$ ; med $N = 14$ hasher den til plass 8. En nøkkel som ligger igjen på
plass 1, vil aldri bli funnet av et søk som starter på plass 8.

Derfor må hele tabellen bygges på nytt: opprett et nytt array, gå gjennom det
gamle, og sett inn hver nøkkel på nytt med den nye hashfunksjonen.

Rehashing

h(k) = k \bmod N

📜Pseudokode-kontrakt: `Rehash`

Antagelser om representasjon. T er et array med N plasser indeksert fra 0;
hver plass er tom eller inneholder én nøkkel. Insert er prosedyren fra
kap. 3.1, som bruker k mod T.length som hashfunksjon —
altså tabellens egen lengde.

Prebetingelse: ingen. Postbetingelse: returverdien er en ny tabell med
dobbelt så mange plasser, som inneholder nøyaktig de samme nøklene, hver på sin
nye plass.

Procedure Rehash(T)
  Input:  hashtabell T som array med N plasser (indeks fra 0)
  Output: en ny hashtabell med 2N plasser og de samme noeklene
  N = T.length
  ny = nytt array med 2N plasser, alle tomme
  for i = 0 to N-1:
      if T[i] er ikke tom:
          Insert(ny, T[i])
  return ny

Grunnideen i én setning: fordi Insert regner ut hashverdien fra tabellens
egen lengde, får hver nøkkel automatisk sin nye plass — du trenger ikke gjøre noe
mer enn å sette dem inn på nytt.

Rekkefølgen nøklene settes inn i er venstre mot høyre i det gamle arrayet.
Det er en antagelse du bør oppgi, for den avgjør hvor nøkler som kolliderer i den
nye tabellen, havner. En annen rekkefølge gir en like korrekt tabell, men en annen
plassering — så på en håndkjøring skal du si hvilken rekkefølge du brukte.

Kjøretid: løkka går gjennom alle $N$ plassene, og for hver av de $n$ nøklene
gjøres én innsetting på $O(1)$ forventet. Totalt $O(n + N)$ for én rehashing.

✏️Eksempel 2: Rehashing fra $N = 7$ til $N = 14$

Tabellen _, 15, 22, 8, 29, _, _ har $N = 7$ og inneholder fire nøkler, altså
$\alpha = 4/7 \approx 0{,}571$ . Terskelen for utvidelse er $\alpha > 0{,}5$ , så
tabellen skal rehashes til $N = 14$ . Vis hele prosessen.

Reinnsettingsrekkefølge: venstre mot høyre i den gamle tabellen, altså 15,
22, 8, 29.

Nye hashverdier med $N = 14$ : $15 \bmod 14 = 1$ , $22 \bmod 14 = 8$ ,
$8 \bmod 14 = 8$ , $29 \bmod 14 = 1$ .

Legg merke til hvor mye som endret seg. I den gamle tabellen hashet alle fire
til plass 1. Nå fordeler de seg på to ulike startplasser.

Steg	Nøkkel $k$	gammel $h$	ny $h(k)$	Prøvde indekser	Tabell etter steget
1	15	1	1	`1`	`_, 15, _, _, _, _, _, _, _, _, _, _, _, _`
2	22	1	8	`8`	`_, 15, _, _, _, _, _, _, 22, _, _, _, _, _`
3	8	1	8	`8 -> 9`	`_, 15, _, _, _, _, _, _, 22, 8, _, _, _, _`
4	29	1	1	`1 -> 2`	`_, 15, 29, _, _, _, _, _, 22, 8, _, _, _, _`

Sluttilstand:

indeks:  0   1   2   3   4   5   6   7   8   9   10  11  12  13
T:       _   15  29  _   _   _   _   _   22  8   _   _   _   _

Ny load-faktor:

\alpha = 4/14 \approx 0{,}286

.
Se på kolonnen «gammel $h$ ». Alle fire var 1. Etter doblingen er to av dem 1
og to er 8. Det er nøyaktig dette som gjør at de gamle indeksene ikke kan

gjenbrukes: nøkkelen 22 lå på plass 2 i den gamle tabellen og skal på plass 8 i

den nye. Hadde vi bare kopiert arrayet over, ville et søk etter 22 startet på

plass 8, funnet den tom, og meldt «ikke funnet».

Hva vi vant. Den gamle tabellen hadde én sammenhengende klynge på fire
plasser; totalkostnaden for de fire innsettingene var 10 prøver. Den nye har to
små klynger, og de samme fire innsettingene kostet 6 prøver. Neste innsetting blir
billigere, og det er hele hensikten.
Fellenote. Fella her er å tro at rehashing er en flytteoperasjon. Den er en

reinnsetting: hver nøkkel går gjennom Insert på nytt, med den nye
tabellstørrelsen i hashfunksjonen.

📝Oppgave 2

Sjanger E og C

En hashtabell med $N = 5$ inneholder nøklene 12, 17 og 3 slik:
_, _, 12, 17, 3.

a) Hva er load-faktoren?
b) Tabellen rehashes til $N = 10$ . Regn ut de nye hashverdiene, og vis
reinnsettingen med rekkefølge venstre mot høyre i den gamle tabellen.
c) Oppgi den nye tabellen og den nye load-faktoren.

📜Hvorfor doblingen er billig i lengden

Én rehashing koster

O(n + N)

, og det ser dyrt ut. Men den skjer sjelden, og
regnestykket over mange innsettinger er verdt å kunne:

Starter du med tabellstørrelse $N_0$ og dobler hver gang tabellen blir for full,
har du etter $n$ innsettinger gjort rehashinger med samlet kostnad omtrent

$N_0 + 2N_0 + 4N_0 + \cdots + n.$

Dette er en doblingsrekke, og summen er mindre enn det dobbelte av siste ledd
— altså under $2n$ . Fordelt på $n$ innsettinger blir det en konstant per
innsetting.

Konklusjonen: $n$ innsettinger i en hashtabell med dobling koster $O(n)$
totalt, altså $O(1)$ per innsetting i snitt, selv om enkelte innsettinger
utløser en dyr rehashing.

Om ordet «amortisert». Denne typen analyse — å fordele kostnaden av en sjelden
dyr operasjon utover mange billige — kalles amortisert analyse. Begrepet nevnes
her bare for å avgrense det: amortisert analyse er ikke IN2010-pensum, og du
blir ikke bedt om å gjøre en slik analyse. Det du skal kunne, er konklusjonen: at
doblingen ikke ødelegger den forventede $O(1)$ -kostnaden per operasjon.

Løkke 3 — hashmap og hash-set som Del 2-verktøy (ca. 15 min)

Nå til den delen som gir poeng på Del 2.

Hashtabellen du har håndkjørt, er maskineriet. To grensesnitt bygger på det, og
begge har du sannsynligvis brukt før uten å tenke på kostnaden:

- Et hashmap lagrer par av nøkkel og verdi. Du slår opp på nøkkelen og får
verdien. «Hvor mange ganger forekommer hvert ord i teksten?» er en
hashmap-oppgave.
- Et hash-set lagrer bare nøkler, og svarer på ett spørsmål: finnes denne
her? «Har jeg sett dette elementet før?» er en hash-set-oppgave.

Begge gir $O(1)$ forventet for innsetting, oppslag og medlemskapstest, og
$O(n)$ i verste tilfelle. Og det er nettopp den forventede $O(1)$ -en som gjør at
en hel klasse Del 2-oppgaver kan løses i $O(n)$ i stedet for $O(n \log n)$ .

Hashmap

O(1)

Hash-set

O(1)

📜Broen til Del 2: når hash-set gir

O(n)

Mønsteret er alltid det samme, og det er verdt å kunne som en form:

Går du gjennom elementene én gang, og trenger du for hvert element å vite om
du har sett noe bestemt før, kan et hash-set gjøre hvert oppslag $O(1)$
forventet — og hele algoritmen $O(n)$ forventet.

Sammenligningen sensor forventer:

Strategi	Kjøretid	Forutsetning
Dobbel løkke over alle par	$O(n^2)$	ingen
Sortér og skann	$O(n \log n)$	elementene kan sammenlignes
Hash-set	$O(n)$ forventet, $O(n^2)$ verste	elementene kan hashes

Tre presiseringer som hver er verdt et delpoeng:
1. «Forventet» må stå. Hash-set-løsningen er

O(n)

forventet. I verste
tilfelle, når alt kolliderer, koster hvert oppslag

O(n)

og totalen blir

O(n^2)

— like dårlig som den naive løsningen.

2. Sortering er ikke feil. $O(n \log n)$ er en helt korrekt besvarelse og gir

uttelling. Den står bare ett trinn lavere i poengtrappen.
3. Bucket og radix er ikke lov som «rask sortering» med mindre verdiområdet er
kjent og begrenset — felle #5 i bokas feilregister, se
kap. 2.3.
Selve algoritmene skrives ut i kap. 3.4.

✏️Eksempel 3: Samme problem, tre kjøretider

Du har $n$ heltall i et usortert array og skal avgjøre om to av dem er like. Sett
opp de tre lovlige strategiene med kjøretid, og si hvilken som står øverst i
poengtrappen.

Problemet navngitt: duplikatsøk i en usortert mengde.

Antagelser om representasjon: A er et array med $n$ heltall indeksert fra 0.
Heltall kan hashes, og vi kan opprette nye strukturer.

Strategi 1 — dobbel løkke. Sammenlign hvert par:

for i = 0 to n-1:
    for j = i+1 to n-1:
        if A[i] == A[j]:
            return sant
return usant

To nøstede løkker over $n$ gir $\displaystyle \frac{n(n-1)}{2}$ sammenligninger, altså
$O(n^2)$ . Korrekt, men nederst i trappen.

Strategi 2 — sortér og skann. Sortér med flettesortering i $O(n \log n)$ , og
gå deretter gjennom naboparene i $O(n)$ . Sumregelen gir $O(n \log n)$ .

Strategi 3 — hash-set. Gå gjennom arrayet én gang. For hvert element: finnes
det allerede i settet? Da har du duplikatet. Ellers legg det inn.

S = tomt hash-set
for i = 0 to n-1:
    if Contains(S, A[i]):
        return sant
    Add(S, A[i])
return usant

Én løkke over $n$ elementer, og hvert oppslag er $O(1)$ forventet. Totalt
$O(n)$ forventet, der $n$ er antall elementer i A.

Poengtrappen:

Kjøretid	Strategi	Uttelling
$O(n)$ forventet	hash-set	full pott
$O(n \log n)$	sortér og skann	noe mindre
$O(n^2)$	dobbel løkke	minst

Kan dette gjøres raskere enn $O(n)$ ? Nei. Du må i verste fall se på hvert
element minst én gang for å kunne konkludere, så

O(n)

er nedre grense for
problemet. Den setningen er verdt å skrive: den viser at du vet at du har truffet
bunnen, og den er en del av det sensor ser etter i et Del 2-svar.

Og det ærlige forbeholdet: i verste tilfelle, når alle nøklene kolliderer, er
hash-set-løsningen $O(n^2)$ — nøyaktig like dårlig som den doble løkka. Det er
derfor ordet «forventet» ikke kan utelates.

📝Oppgave 3

Sjanger C

Avgjør sant eller usant, og begrunn hver med én setning.

a) Rehashing kan gjenbruke de gamle indeksene direkte etter en dobling.
b) Et hashmap har $O(1)$ oppslagstid i verste tilfelle.
c) Load-faktoren i en tabell med lukket hashing kan være 1,5.
d) Å sette inn $n$ nøkler i en hashtabell med dobling koster $O(n)$ totalt.

Typiske feil

- Å tro at rehashing bevarer indeksene. Den gjør ikke det: $h(k) = k \bmod N$
endres når $N$ endres, og hele tabellen må bygges på nytt. Dette er kapitlets
hyppigste sant/usant-punkt.
- Å oppgi hashmap-ets verste tilfelle som $O(1)$ . Det er $O(n)$ . $O(1)$ er
forventet, og ordet må stå.
- Å snu brøken i load-faktoren. $\alpha = n/N$ — nøkler over plasser. Snudd
gir den tall over 1 for en halvfull tabell.
- Å hoppe over «forventet» i et Del 2-svar. En hash-basert løsning er $O(n)$
forventet og $O(n^2)$ i verste tilfelle. Skriver du bare « $O(n)$ », har du oppgitt
en kjøretid som ikke matcher algoritmen — og det trekkes det eksplisitt for.
- Å bruke $n$ og $N$ om hverandre. $n$ er antall nøkler, $N$ er antall
plasser. Felle #10 i bokas feilregister er å oppgi kjøretid uten å definere
størrelsene; her er det to av dem, og de ligner på hverandre.

📝Oppgave 4

Sjanger I

Skriv Rehash(T), som dobler tabellen og setter inn alle nøklene på
nytt.

a) Oppgi antagelser om representasjon.
b) Skriv prosedyren.
c) Oppgi kjøretiden for én rehashing, og for $n$ innsettinger med dobling
totalt.

📝Oppgave 5

Sjanger I, krevende

Du får et usortert array A med $n$ heltall og et tall
x, og skal avgjøre om to elementer i A summerer til x.

a) Skriv en løsning med hash-set. Oppgi antagelser og kjøretid.
b) Hvorfor kan du ikke bare sjekke om x - A[i] finnes i settet før du
har lagt inn noe?
c) Hva blir kjøretiden hvis alle nøklene kolliderer?

📝Oppgave 6

Sjanger I, krevende

Du får en liste med $n$ ord og skal finne det ordet som
forekommer flest ganger.

a) Skriv en løsning med hashmap. Oppgi antagelser og kjøretid.
b) Hva ville en løsning uten hashmap kostet?
c) Hva skjer med kjøretiden hvis alle ordene er forskjellige?

Begrepsbank

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

Terskelen for rehashing

\alpha

Hvorfor hashverdiene endres ved dobling

h(k) = k \bmod N

Kostnaden ved én rehashing

O(n + N)

Doblingsrekkens sum

N_0 + 2N_0 + 4N_0 + \cdots + n

Reinnsettingsrekkefølge

Rekkefølgen nøklene settes inn i under en rehashing — vanligvis venstre mot høyre i det gamle arrayet. Den avgjør hvor nøkler som kolliderer i den nye tabellen havner, så den er en antagelse du skal oppgi i en håndkjøring. En annen rekkefølge gir en like korrekt tabell med andre plasseringer.

Hashmap-operasjonene

O(1)

Hash-set-operasjonene

O(1)

Hash-set-mønsteret for

O(n)

O(1)

Poengtrappen for søkeoppgaver

O(n)

«Forventet» er ikke pynt

O(n)

Hash-set kontra sortering

O(n)

Amortisert analyse — avgrenset bort

O(1)

Repetisjon — kapitlet på ett kort

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.