3.3 DRILL — Linear-probing håndkjøring og insert-pseudokode

Full drill på sjanger E (håndkjør linear-probing-innsetting, oppgi hele tabellen) og I (skriv insert-prosedyren korrekt).

80 min

12 oppgaver

DRILLLinear-probing håndkjøringinsert-pseudokode

Din fremgang i kapitlet

0 / 12 oppgaver

Kapitlets plass i kurset

Bygger på

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

Dette er drillkapitlet for de to hashing-sjangrene, og begge har vært på alle
sju settene (100 %):

- Sjanger E — håndkjøring, altså at du utfører innsettingene steg for steg og
oppgir hele tabellen som sluttilstand.
- Sjanger I — hashing i pseudokode, altså at du skriver Insert eller
Contains selv og oppgir kjøretiden.

Si det som det er: dette er tyngre enn i et generisk algoritmepensum. Ved
NTNUs TDT4120 er hashing et faktapunkt i under halvparten av settene. Her er det
en utførelsesferdighet som testes i hvert eneste sett, på to måter samtidig.
Kommer du fra en generisk algoritmebok, har du sannsynligvis lest hashing som et
kapittel om «forventet $O(1)$ » og gått videre. Det holder ikke her.

Den gode nyheten: håndkjøring er den mest mekaniske ferdigheten i hele faget.
Det finnes ingen innsikt å få — det finnes en oppskrift, og den kan trenes til den
er feilfri. Det er nettopp det dette kapitlet er til for.

Prioritet: høyeste.

Slik er kapitlet lagt opp (80 min): oppskriften og et sensor-kommentert case
først (ca. 20 min), så tolv oppgaver i tre bolker à ca. 20 min. Bolkene er
uavhengige — ta gjerne én per kveld. Etter hver bolk står en boks som sier hva
oppgavene testet.

Forkunnskaper

- kap. 3.1 — hashtabellen, $h(k) = k \bmod N$ , lineær
probing, wraparound og overskriving ved lik nøkkel. Alt du driller her, er
derfra.
- kap. 3.2 — load-faktor og rehashing, som brukes i de siste
oppgavene.

Og fra Del 1: kap. 1.2 om løkketelling, som gir kjøretidene
i pseudokodeoppgavene.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for sjanger E og I

To oppskrifter, én for hver sjanger. Første steg er å se hvilken du har.

Sjanger E — håndkjøring. Du får nøkler, en tabellstørrelse og en
hashfunksjon, og skal levere sluttilstanden.

1. Tegn tabellen først. Skriv indeksene $0$ til $N-1$ på én linje og la det
være plass under hver. Nå kan du ikke miste tellingen.
2. Regn ut $h(k)$ for ALLE nøklene, i en egen linje, før du setter inn noe.
Dette ene grepet fjerner de fleste regnefeilene, og det gir deg et regnestykke
å kontrollere mot etterpå.
3. Sett inn én om gangen. Er plassen opptatt av en annen nøkkel, gå til
$(i+1) \bmod N$ . Er den opptatt av samme nøkkel, skriv over og stopp.
4. Skriv opp probing-sekvensen for hver nøkkel mens du går. Det koster tre
sekunder og gir delvis uttelling hvis sluttilstanden blir feil.
5. Lever hele tabellen, kommaseparert, med _ for tomme plasser.

Sjanger I — pseudokode. Du skal skrive prosedyren og oppgi kjøretiden.

1. Navngi problemet: «innsetting i hashtabell med lukket hashing og lineær
probing».
2. Oppgi antagelser om representasjon: array med N plasser fra 0, hver plass
tom eller med én nøkkel, h(k) = k mod N, tabellen ikke full.
3. Skriv algoritmen. De to detaljene som gir poeng, ligger begge i
while-linja: mod N i oppdateringen og and T[i] er ulik k i betingelsen.
4. Oppgi kjøretiden som matcher koden: $O(1)$ forventet, $O(n)$ verste,
med $n$ definert som antall lagrede nøkler.

De to kontrollene som tar to sekunder hver, og som fanger nesten alt:

- Er noen indeks i sporingen din større enn $N-1$ ? Da har du glemt mod N.
- Stemmer antall nøkler i tabellen med antall ULIKE nøkler du fikk utdelt? Er
det flere, har du duplisert en nøkkel i stedet for å overskrive.

✏️Gjennomarbeidet eksamenscase med sensorkommentarer

(Eksamensnivå, sjanger E og I.) Et sett har denne oppgaven, verdt 6 poeng:

a) (3 p) Sett inn nøklene 31, 20, 42, 9, 53 og 64 i denne rekkefølgen i en tom
hashtabell med $N = 11$ og $h(k) = k \bmod 11$ , med lineær probing. Oppgi hele
tabellen.

b) (2 p) Skriv Insert(T, k) i pseudokode, og oppgi kjøretiden.

c) (1 p) Hva er load-faktoren etter innsettingene, og hva sier antall prøver om
hvor godt hashfunksjonen fungerte her?

a) Håndkjøringen.

Steg 2 i oppskriften først — regn ut alle hashverdiene:

$31 = 2 \cdot 11 + 9$ , $20 = 1 \cdot 11 + 9$ , $42 = 3 \cdot 11 + 9$ ,
$9 = 0 \cdot 11 + 9$ , $53 = 4 \cdot 11 + 9$ , $64 = 5 \cdot 11 + 9$ .

Alle seks gir $h(k) = 9$ . Det er en opplysning verdt å ha før du begynner: du
vet nå at dette blir én lang klynge, og at wraparound kommer i spill, siden 9 er
nest siste plass.

Steg	Nøkkel $k$	$h(k)$	Prøvde indekser	Tabell etter steget
1	31	9	`9`	`_, _, _, _, _, _, _, _, _, 31, _`
2	20	9	`9 -> 10`	`_, _, _, _, _, _, _, _, _, 31, 20`
3	42	9	`9 -> 10 -> 0`	`42, _, _, _, _, _, _, _, _, 31, 20`
4	9	9	`9 -> 10 -> 0 -> 1`	`42, 9, _, _, _, _, _, _, _, 31, 20`
5	53	9	`9 -> 10 -> 0 -> 1 -> 2`	`42, 9, 53, _, _, _, _, _, _, 31, 20`
6	64	9	`9 -> 10 -> 0 -> 1 -> 2 -> 3`	`42, 9, 53, 64, _, _, _, _, _, 31, 20`

Sluttilstand:

indeks:  0   1   2   3   4   5   6   7   8   9   10
T:       42  9   53  64  _   _   _   _   _   31  20

På én linje: 42, 9, 53, 64, _, _, _, _, _, 31, 20

Sensornotat, a) — 3 poeng. Typisk fordeling: 1 p for riktige hashverdier,
1 p for riktig probing med wraparound, 1 p for at hele tabellen er oppgitt med
tomme plasser markert.
Delvis riktig tilstand gir delvis uttelling. Har du riktig sekvens men
bommer på én plassering, får du som regel to av tre poeng. Det siste poenget
henger på to ting: at ingen indeks er utenfor $0$ til $10$ , og at tabellen
er levert hel, ikke som en liste over hvor nøklene havnet.
Steg 3 er der poenget vinnes eller tapes: fra plass 10 går sekvensen til plass
0, ikke til plass 11.

b) Pseudokoden.

Problemet: innsetting i hashtabell med lukket hashing og lineær probing.
Antagelser om representasjon: T er et array med N plasser indeksert fra 0;
hver plass er tom eller inneholder én nøkkel; h(k) = k mod N; tabellen er ikke
full.

Procedure Insert(T, k)
  Input:  hashtabell T som array med N plasser (indeks fra 0), noekkel k
  Output: T med k satt inn; lik noekkel overskrives i stedet for aa dupliseres
  N = T.length
  i = k mod N
  while T[i] er ikke tom and T[i] er ulik k:
      i = (i + 1) mod N
  T[i] = k

Kjøretid:

O(1)

forventet,

O(n)

i verste tilfelle, der

n

er antall

nøkler i tabellen.

Sensornotat, b) — 2 poeng. 1 p for korrekt løkke med begge detaljene
(mod N og sjekken for lik nøkkel), 1 p for kjøretiden med begge tilfellene.
En besvarelse med riktig kode men uten kjøretid får 1 p. En som skriver
« $O(1)$ » uten «forventet», mister som regel et halvt. En som glemmer mod N,
mister kodepoenget helt — det er felle #11, probing som går utenfor
$0$ til $N-1$ .

c) Load-faktor og prøvetelling.

$\alpha = n/N = 6/11 \approx 0{,}545$ .
Antall prøver: $1 + 2 + 3 + 4 + 5 + 6 = 21$ , altså 3,5 per innsetting.

Med en hashfunksjon som spredte nøklene jevnt, ville snittet ligget nær 1. Her ga
alle seks nøklene samme hashverdi, og tabellen degenererte til et lineært søk.
Det er nøyaktig verste tilfelle $O(n)$ , og det illustrerer hvorfor kjøretiden
$O(1)$ alltid må ha ordet «forventet» foran seg.

Sensornotat, c) — 1 poeng. Løsningen får poenget for load-faktoren alene;
observasjonen om prøvetallet er det som skiller en god besvarelse fra en
tilstrekkelig. Merk at nøklene her er valgt slik at de alle er $9$ modulo $11$ —
et eksamenssett gjør sjelden det ved et uhell.

Margnotat om delvis uttelling. Denne oppgaven er verdt 6 poeng, og du kan få
4 av dem uten å ha en eneste feilfri tabell: pseudokoden, kjøretiden og
load-faktoren er alle uavhengige av at håndkjøringen stemmer. La aldri en

deloppgave stå tom.

Bolk 1 — grunnleggende håndkjøring (ca. 20 min)

Fire oppgaver som bygger opp fra ingen kollisjoner til full klynge. Bruk
oppskriften hver gang, også når oppgaven ser triviell ut — det er vanen du skal
ha på eksamensdagen.

📝Oppgave 1

Eksamensnivå, sjanger E

N = 7

h(k) = k \bmod 7

. Sett inn 8, 16, 3
og 11 i denne rekkefølgen.

a) Regn ut $h(k)$ for alle fire først.
b) Oppgi hele tabellen.
c) Hvor mange prøver kostet innsettingene til sammen?

📝Oppgave 2

Eksamensnivå, sjanger E

N = 7

h(k) = k \bmod 7

. Sett inn 14, 21, 28 og 35.

a) Regn ut $h(k)$ for alle fire.
b) Oppgi hele tabellen.
c) Sammenlign antall prøver med oppgave 1. Hva forklarer forskjellen?

📝Oppgave 3

Eksamensnivå, sjanger E

N = 10

h(k) = k \bmod 10

. Sett inn 19, 29, 39 og
5.

a) Oppgi hele tabellen.
b) Hvilke av innsettingene brukte wraparound?
c) Hvorfor havnet ikke 5 i klyngen?

📝Oppgave 4

Eksamensnivå, sjanger E

N = 9

h(k) = k \bmod 9

. Sett inn 21, 30, 21 og 12
i denne rekkefølgen.

a) Oppgi hele tabellen.
b) Hvor mange nøkler ligger i tabellen til slutt?
c) Hva ville tabellen sett ut som hvis Insert ikke hadde sjekket for lik
nøkkel?

De fire oppgavene rullerte grunnmekanikken:

- Oppgave 1 testet det enkleste tilfellet — ingen kollisjoner — og at du
likevel bruker oppskriften.
- Oppgave 2 testet full klynge fra plass 0, og at du ser forskjellen mellom en
tabell som ser klumpete ut og en som er det.
- Oppgave 3 testet wraparound over slutten av tabellen, som er felle #11.
- Oppgave 4 testet overskriving ved lik nøkkel, som er den andre halvdelen av
samme felle.

Klarte du 3 og 4 uten å nøle, sitter de to detaljene som gir flest poeng.
Bommet du på en av dem, er de to kontrollene fra oppskriften verdt å gjøre til en
vane: ingen indeks over $N-1$ , og antall nøkler = antall ulike nøkler.

Bolk 2 — søk, større tabeller og rehashing (ca. 20 min)

— naturlig pausepunkt —

Fire oppgaver som utvider repertoaret: søk i en ferdig tabell, større $N$ , og en
rehashing.

📝Oppgave 5

Eksamensnivå, sjanger E

N = 9

h(k) = k \bmod 9

. Sett inn 18, 27, 4, 13 og
22.

a) Oppgi hele tabellen.
b) Hva er load-faktoren etterpå?
c) Hvor mange klynger har tabellen?

📝Oppgave 6

Eksamensnivå, sjanger E…

Bruk tabellen fra oppgave 5:
18, 27, _, _, 4, 13, 22, _, _ med $N = 9$ .

a) Søk etter 13. Hvilke indekser prøves?
b) Søk etter 31. Hvilke indekser prøves, og hva blir svaret?
c) Søk etter 8. Hvilke indekser prøves, og hva blir svaret?
d) Hvorfor er søket i c) så mye kortere enn i b)?

📝Oppgave 7

Eksamensnivå, sjanger E

N = 13

h(k) = k \bmod 13

. Sett inn 27, 40, 14, 53
og 1.

a) Oppgi hele tabellen.
b) Hvor mange prøver kostet det til sammen?
c) Tabellen har 13 plasser og bare 5 nøkler. Hvorfor ble det likevel så mange
prøver?

📝Oppgave 8

Eksamensnivå, sjanger…

Tabellen 14, 21, 28, 35, _, _, _ med
$N = 7$ er resultatet fra oppgave 2. Terskelen for rehashing er $\alpha > 0{,}5$ .

a) Er terskelen overskredet?
b) Rehash tabellen til $N = 14$ . Regn ut de nye hashverdiene og vis
reinnsettingen, med rekkefølge venstre mot høyre i den gamle tabellen.
c) Oppgi den nye tabellen, den nye load-faktoren og antall prøver.

- Oppgave 5 testet at du ser hvor klyngegrensene går, og hvorfor to korte
klynger er bedre enn én lang.
- Oppgave 6 testet Contains på alle tre utfallene: funnet, ikke funnet etter
lang probing, og ikke funnet med én gang.
- Oppgave 7 testet at load-faktor og faktisk kostnad er to forskjellige ting.
Det er et poeng en drøftingsoppgave gjerne ber om.
- Oppgave 8 testet rehashing med korrekt reinnsetting, og hvorfor de gamle
indeksene er verdiløse.

Oppgave 7 er den som oftest overrasker: en tabell som er under halvfull kan
likevel oppføre seg som verste tilfelle, hvis hashfunksjonen er dårlig for nettopp
de nøklene.

Bolk 3 — pseudokode og kanttilfeller (ca. 20 min)

Fire oppgaver på sjanger I. Her er formen like viktig som innholdet: problemet
navngitt, antagelser oppgitt, algoritmen, og kjøretiden som matcher.

📝Oppgave 9

Eksamensnivå, sjanger I

Skriv Insert(T, k) for lukket hashing med lineær
probing.

a) Oppgi antagelser om representasjon.
b) Skriv prosedyren.
c) Oppgi kjøretiden, og forklar hvorfor den har to tilfeller.

📝Oppgave 10

Eksamensnivå, sjanger I

Skriv Contains(T, k), som avgjør om nøkkelen k
finnes i tabellen.

a) Skriv prosedyren.
b) Hvorfor kan søket avsluttes på en tom plass?
c) Hva skjer hvis tabellen er full og nøkkelen ikke finnes? Hvordan sikrer du
at prosedyren terminerer?

📝Oppgave 11

Eksamensnivå, sjanger…

En besvarelse har levert dette:

Procedure Insert(T, k)
  Input:  hashtabell T, noekkel k
  Output: T med k satt inn
  i = k mod T.length
  while T[i] er ikke tom:
      i = i + 1
      if i == T.length:
          i = 0
  T[i] = k
  Kjoeretid: O(1)

a) Er wraparound håndtert riktig?
b) Hvilke feil gjenstår?
c) Vis konkret hva som går galt med $N = 6$ , tabellen _, 13, 19, _, _, _ og
nøkkelen 13.

📝Oppgave 12

Eksamensnivå, sjanger E…

N = 5

h(k) = k \bmod 5

. Sett inn
10, 15, 20 og 25.

a) Oppgi hele tabellen og load-faktoren.
b) Hva skjer hvis du nå prøver å sette inn nøkkelen 30 med Insert fra
kap. 3.1?
c) Hva skjer hvis du prøver å sette inn 30 og tabellen i tillegg er helt full?
d) Hvordan bør en robust implementasjon håndtere dette?

Typiske feil — fellekatalogen for sjanger E og I

Samlet, i den rekkefølgen de koster mest poeng. De to første er begge felle
#11 i bokas feilregister — probing som går utenfor $0$ til $N-1$ , eller som
ikke overskriver en lik nøkkel.

- Manglende mod N i probing-steget. Når klyngen når plass $N-1$ , må neste
plass være 0. Kontrollen: ingen indeks i sporingen din skal være større enn
$N-1$ .
- Manglende sjekk for lik nøkkel. Løkkebetingelsen må ha and T[i] er ulik k.
Kontrollen: antall nøkler i tabellen skal stemme med antall ulike nøkler
du fikk utdelt.
- Å levere bare de innsatte nøklene. Sensor ber om hele tabellen med _
for tomme plasser. De tomme plassene er en del av svaret.
- Regnefeil i $h(k)$ . $22 \bmod 7$ er 1, ikke 3. Regn ut alle hashverdiene i en
egen linje først — det er det enkleste grepet i hele kapitlet, og det fanger
flest feil.
- $O(1)$ uten «forventet». Kjøretiden må matche algoritmen: $O(1)$ forventet,
$O(n)$ verste. Begge skal med.
- Manglende kanttilfelle i Contains. Uten telleren antall < N terminerer
ikke løkka i en full tabell.
- $n$ og $N$ brukt om hverandre. $N$ er tabellstørrelsen, $n$ er antall lagrede
nøkler. Å bruke dem uten å definere dem er felle #10.

Og den viktigste vanen: skriv ned probing-sekvensen for hver nøkkel mens du
går. Blir sluttilstanden feil, viser sekvensen at metoden var riktig — og delvis
riktig gir delvis uttelling.

Begrepsbank

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

Håndkjøringsoppskriften for linear probing

0

De to kontrollene

N-1

Delvis uttelling på en håndkjøring

Sjanger E gir poeng per delmoment: riktige hashverdier, riktig probing med wraparound, og hele tabellen levert med tomme plasser markert. Derfor er det verdt å skrive ned probing-sekvensen selv om du er usikker på sluttilstanden, og derfor skal ingen deloppgave stå tom. Det siste poenget henger typisk på wraparound og på formatet.

Klynge kontra tilfeldig naboskap

Fire nøkler på rad i tabellen betyr ikke nødvendigvis en klynge. En klynge er nøkler som har blitt forskjøvet fordi plassen deres var opptatt. Ligger fire nøkler på rad, hver på sin egen hashverdi, er kostnaden 1 prøve per innsetting. Ligger de på rad fordi alle fire hashet til den første plassen, er kostnaden 10. Sluttilstanden ser lik ut; kostnaden gjør det ikke.

Load-faktor er ikke hele historien

En tabell kan være under halvfull og likevel oppføre seg som verste tilfelle, hvis alle nøklene hasher til samme plass. Løsningen på det er ikke en større tabell — det ville gitt samme problem med mer plass — men en bedre hashfunksjon. Skillet mellom «for lite plass» og «feil fordeling» er et poeng en drøftingsoppgave gjerne ber om.

Kostnaden ved et mislykket søk

h(k)

Termineringsvilkåret i `Contains`

N

Prebetingelsen «tabellen er ikke full»

Insert slik den er skrevet i boka, forutsetter at minst én plass er tom. Er tabellen full og nøkkelen ikke finnes, terminerer ikke løkka. Prosedyren er korrekt gitt sin prebetingelse . En robust implementasjon rehasher før tabellen fylles opp, eller legger inn en teller som melder fra. Å nevne dette er verdt et delpoeng.

Form kontra innhold i pseudokode

Sensor krever at løsningen er lett forståelig, entydig og presis — ikke at den ser ut som en bestemt fasit. En wraparound skrevet som if i == N: i = 0 er like riktig som (i + 1) mod N . Det motsatte gjelder også: en løsning som er teknisk riktig, men uklar, kan bli ignorert. Felle #12 i bokas feilregister er nettopp uklar eller unødig lang pseudokode.

Firestegsformen på et sjanger I-svar

n

Repetisjon — kortet du tar med til eksamen

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.