3.1 Hashtabeller og lukket hashing (linear probing)

Hashtabellen med lukket hashing og lineær probing — hashfunksjon, kollisjonshåndtering og håndkjøring av innsetting i array-form.

55 min

7 oppgaver

Hashtabellerlukket hashing (linear probing)

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

1.2Kjøretidsanalyse fra kode — løkketelling

Brukes videre i

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

Les dette avsnittet selv om du pleier å hoppe over eksamensvinkel-boksene.

Hashing har vært på alle sju settene i arkivet (100 %), og den testes på
to måter i hvert eneste sett:

- Sjanger E — håndkjøring, altså at du utfører operasjonen steg for steg og
oppgir sluttilstanden. Du får noen nøkler, en tabellstørrelse og en
hashfunksjon, og skal levere hele tabellen.
- Sjanger I — hashing og søk i pseudokode, altså at du skriver
Insert-prosedyren selv, med riktig wraparound og riktig håndtering av lik
nøkkel, og oppgir kjøretiden.

Det er verdt å si dette rett ut: hashing er tyngre i IN2010 enn i et typisk
algoritmepensum. Ved NTNUs TDT4120 dukker hashing opp i under halvparten av
settene, og da stort sett som et faktapunkt du kan krysse av på. Her er det en
utførelsesferdighet: du skal kunne føre en tabell gjennom en innsettingsrekke
uten å bomme på én eneste indeks, og du skal kunne skrive prosedyren fra bunnen.
Studenter som kommer fra en generisk algoritmebok, eller fra et NTNU-pensum,
undervurderer dette systematisk. Har du hørt at hashing er et randtema, tar du
feil her.

Prioritet: høyeste. Dette kapitlet og drillen i
kap. 3.3 er de to viktigste i Del 3.

Slik er kapitlet lagt opp (55 min): fire løkker med tidsanslag, og
pausepunkter underveis.

Forkunnskaper

- kap. 1.2 — løkketelling. Kjøretidene her leses ut av
hvor mange plasser en probing-løkke må innom.
- kap. 1.1 — forskjellen mellom forventet og verste
tilfelle. Hashing er hele fagets tydeligste eksempel på at de to er forskjellige.

Er array-tenkning ferskt:

- Lister — indeksering fra 0, som er alt hashtabellen er
bygget på.
- Ordbøker — den samme strukturen sett fra brukersiden. Det
er maskineriet under den du møter her.

Notasjons- og pseudokodeliste

Løkke 1 — garderoben med nummererte knagger (ca. 12 min)

Se for deg en garderobe med sju knagger, nummerert 0 til 6. Du får en jakke med et
lappnummer, for eksempel 15, og skal henge den et sted du selv kan finne den
igjen uten å lete gjennom hele rekka.

Trikset er å regne ut knaggen fra lappnummeret: ta resten når du deler på 7.
$15 = 2 \cdot 7 + 1$ , så jakke 15 skal på knagg 1. Kommer du tilbake senere,
regner du ut det samme og går rett til knagg 1. Ingen leting.

Det er en hashtabell. Regnestykket «rest ved divisjon med tabellstørrelsen»
er hashfunksjonen, og den skrives $h(k) = k \bmod N$ .

Så oppstår problemet som hele resten av kapitlet handler om: neste jakke har
lappnummer 22, og $22 = 3 \cdot 7 + 1$ — også knagg 1. To jakker, én knagg. Det
kalles en kollisjon, og måten IN2010 løser den på, er den enkleste som
finnes: heng jakka på neste ledige knagg.

Hashtabell

N

Hashfunksjon

h(k) = k \bmod N,

Kollisjon

h(k_1) = h(k_2)

Lukket hashing med lineær probing

(i+1) \bmod N

📜Pseudokode-kontrakt: `Insert`

Antagelser om representasjon. T er et array med N plasser indeksert fra 0.
En plass er enten tom eller inneholder én nøkkel. Nøklene er heltall, og
hashfunksjonen er h(k) = k mod N. Vi antar at tabellen ikke er full — er den
det, må den utvides først, se kap. 3.2.

Prebetingelse: minst én plass i T er tom, eller k finnes allerede i T.
Postbetingelse: k finnes i T nøyaktig én gang, og alle andre nøkler står
uendret.

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

Grunnideen i én setning: søket etter en ledig plass starter alltid på $h(k)$
og går framover i faste steg, så den samme sekvensen kan følges på nytt når
nøkkelen skal finnes igjen.

De to detaljene sensor trekker for, og de er begge i while-linja:

1. mod N. Uten den vil i = i + 1 løpe utenfor 0..N-1 så snart en klynge
når enden av arrayet. Dette er felle #11 i bokas feilregister — probing som
går utenfor tabellen, eller som ikke overskriver en lik nøkkel.
2. and T[i] er ulik k. Uten den stopper løkka først på en tom plass, og en
nøkkel som allerede finnes, blir lagt inn en gang til. En hashtabell skal ha
hver nøkkel én gang.

Kjøretid: $O(1)$ forventet — sprer hashfunksjonen nøklene jevnt, er
probing-sekvensen kort. $O(n)$ i verste tilfelle, når alle nøklene har havnet i
én sammenhengende klynge og løkka må gå gjennom hele. Å oppgi $O(1)$ uten ordet
«forventet» er en fast trekkgrunn.

✏️Eksempel 1: Innsetting med klyngedannelse

Sett inn nøklene 15, 22, 8, 29 og 3 i denne rekkefølgen i en tom hashtabell med
$N = 7$ og $h(k) = k \bmod 7$ , med lineær probing. Oppgi hele tabellen.

Regn ut $h(k)$ for hver nøkkel først: $15 \bmod 7 = 1$ , $22 \bmod 7 = 1$ ,
$8 \bmod 7 = 1$ , $29 \bmod 7 = 1$ , $3 \bmod 7 = 3$ .

Fire av fem nøkler starter på samme plass. Det er nettopp poenget med eksempelet.

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

Sluttilstand — dette er svaret du leverer:

indeks:   0    1    2    3    4    5    6
T:        _    15   22   8    29   3    _

Eller på én linje: _, 15, 22, 8, 29, 3, _
Legg merke til steg 5. Nøkkelen 3 hasher til plass 3, som er sin egen
riktige plass — men den er opptatt av 8, som havnet der på grunn av en helt annen
kollisjon. Klyngen som de fire første nøklene bygget, sperrer nå for en nøkkel som

ikke hadde noe med dem å gjøre. Det heter primær klyngedannelse, og det er

lineær probings viktigste svakhet.

Totalt antall prøver: $1 + 2 + 3 + 4 + 3 = 13$ , altså 2,6 per innsetting. På

en tom tabell hadde det vært 1 per innsetting. Det er slik en klynge koster.
Fellenote. Fella her er felle #11 — å levere bare de innsatte nøklene i
stedet for hele tabellen. Sensor ber om hele tabellen, med _ for tomme
plasser, fordi det er de tomme plassene som viser at du har fulgt
probing-sekvensen riktig.

📝Oppgave 1

(Innstegsoppgave, sjanger E — håndkjøring, altså at du utfører operasjonen steg
for steg og oppgir sluttilstanden.) En hashtabell har $N = 5$ og
$h(k) = k \bmod 5$ .

a) Regn ut $h(k)$ for nøklene 11, 6, 7 og 20.
b) Sett dem inn i den rekkefølgen, med lineær probing, og oppgi hele
tabellen.

Løkke 2 — wraparound: når klyngen når enden (ca. 13 min)

— naturlig pausepunkt —

Nå kommer detaljen som skiller en riktig håndkjøring fra en gal, og den er verdt
et helt poeng i hvert eneste sett.

Hva skjer når en nøkkel hasher til den siste plassen i tabellen, og den er
opptatt?

Svaret er ikke «plass $N$ » — den finnes ikke. Svaret er at du går rundt til
plass 0. Det er derfor probing-steget skrives

$i_{\text{neste}} = (i + 1) \bmod N$

og ikke bare $i + 1$ . Tabellen er en ring, ikke en linje.

Uten mod N går indeksen utenfor arrayet. Det er felle #11 i bokas
feilregister, og på en programmeringsoppgave ville det gitt en feilmelding; på en
håndkjøring gir det et svar sensor ikke kan gi poeng for.

📜Wraparound-regelen

Probing-sekvensen for en nøkkel

k

i en tabell med

N

plasser er

$h(k),\quad (h(k)+1) \bmod N,\quad (h(k)+2) \bmod N,\quad \ldots$

Den besøker alle $N$ plassene før den kommer tilbake til utgangspunktet. Derfor:

- Sekvensen går aldri utenfor $0$ til $N-1$ . Er du på plass $N-1$ og skal
videre, er neste plass 0.
- Sekvensen finner alltid en ledig plass hvis det finnes én. Den prøver hele
tabellen.
- Den samme sekvensen må følges ved søk. Det er derfor Contains bruker
nøyaktig samme regnestykke som Insert.

Beslektet felle: #7 — å glemme siste ledd i en syklisk struktur, altså å
iterere rundt uten mod N. Den dukker opp igjen i NP-delen senere i boka, og den
har samme rot: en ring behandlet som en linje.

✏️Eksempel 2: Wraparound over slutten av tabellen

Sett inn nøklene 17, 26, 8, 35 og 9 i denne rekkefølgen i en tom hashtabell med
$N = 9$ og $h(k) = k \bmod 9$ . Oppgi hele tabellen.

Hashverdiene: $17 \bmod 9 = 8$ , $26 \bmod 9 = 8$ , $8 \bmod 9 = 8$ ,
$35 \bmod 9 = 8$ , $9 \bmod 9 = 0$ .

De fire første starter på plass 8 — den siste plassen i tabellen.

Steg	Nøkkel $k$	$h(k)$	Prøvde indekser	Tabell etter steget
1	17	8	8	`_, _, _, _, _, _, _, _, 17`
2	26	8	`8 -> 0`	`26, _, _, _, _, _, _, _, 17`
3	8	8	`8 -> 0 -> 1`	`26, 8, _, _, _, _, _, _, 17`
4	35	8	`8 -> 0 -> 1 -> 2`	`26, 8, 35, _, _, _, _, _, 17`
5	9	0	`0 -> 1 -> 2 -> 3`	`26, 8, 35, 9, _, _, _, _, 17`

Sluttilstand:

indeks:   0    1    2    3    4    5    6    7    8
T:        26   8    35   9    _    _    _    _    17

Eller på én linje: 26, 8, 35, 9, _, _, _, _, 17
Se på steg 2. Nøkkelen 26 hasher til plass 8, som er opptatt. Neste plass er

(8+1) \bmod 9 = 0

— altså helt i starten av tabellen. Uten mod N ville du
skrevet «plass 9», som ikke finnes.

Legg merke til hvordan klyngen ser ut. Den ligger på indeks 8, 0, 1, 2, 3 —

sammenhengende, men den «brekker» over kanten. Skriver du tabellen på papir, ser

den ut som to klynger; i virkeligheten er den én, fordi tabellen er en ring.

Kontrollregning. Fem nøkler, og antall prøver ble $1+2+3+4+4 = 14$ . Alle fem
plassene som ble fylt, ligger i probing-sekvensen fra 8, og ingen indeks utenfor
$0$ til $8$ ble noen gang berørt. Den kontrollen — at ingen indeks er utenfor

området — tar to sekunder og fanger felle #11.
Fellenote. Fella her er felle #11 — probing som går utenfor $0$ til $N-1$
fordi mod N er glemt.

📝Oppgave 2

Sjanger E

En hashtabell har $N = 8$ og $h(k) = k \bmod 8$ . Sett inn nøklene
7, 15, 23, 6 og 31 i denne rekkefølgen.

a) Oppgi hele tabellen etter alle innsettingene.
b) Hvor mange plasser ble prøvd for nøkkelen 31?
c) Hvilken nøkkel havnet på en plass som ikke er dens egen hashverdi, uten at
den kolliderte med en nøkkel som hadde samme hashverdi?

Løkke 3 — lik nøkkel skal overskrives (ca. 12 min)

Den andre detaljen sensor trekker for, er kortere å forklare og like lett å
glemme.

En hashtabell lagrer hver nøkkel én gang. Setter du inn 10, og senere setter
inn 10 igjen, skal tabellen fortsatt inneholde nøyaktig én 10-er. Den nye verdien
overskriver den gamle på samme plass.

I pseudokoden er det den ene betingelsen and T[i] er ulik k som sørger for det.
Løkka stopper på to typer plasser: en tom plass, eller en plass som allerede
inneholder nøkkelen. I begge tilfeller er T[i] = k riktig handling.

Fjerner du den betingelsen, går løkka forbi den eksisterende 10-eren og fortsetter
til første tomme plass. Da står 10 to steder, og alle senere søk finner den
første — mens all data som ble lagret sammen med den andre, er utilgjengelig.
Dette er den andre halvdelen av felle #11.

Overskriving ved lik nøkkel

Møter probing-sekvensen en plass som allerede inneholder nøyaktig den nøkkelen du skal sette inn, stopper den der og skriver over. Konsekvensen: en hashtabell inneholder aldri to like nøkler, og antall prøver ved en gjentatt innsetting er nøyaktig det samme som ved det første oppslaget. Uten denne regelen får du duplikater som ingen senere søk vil finne.

✏️Eksempel 3: Samme nøkkel satt inn to ganger

Sett inn nøklene 10, 17, 24 og deretter 10 én gang til, i en tom hashtabell med
$N = 7$ og $h(k) = k \bmod 7$ . Oppgi hele tabellen, og si hva som skiller riktig
og gal håndtering av det siste steget.

Hashverdiene: $10 \bmod 7 = 3$ , $17 \bmod 7 = 3$ , $24 \bmod 7 = 3$ , og
$10 \bmod 7 = 3$ igjen.

Steg	Nøkkel $k$	$h(k)$	Prøvde indekser	Tabell etter steget
1	10	3	3	`_, _, _, 10, _, _, _`
2	17	3	`3 -> 4`	`_, _, _, 10, 17, _, _`
3	24	3	`3 -> 4 -> 5`	`_, _, _, 10, 17, 24, _`
4	10	3	3	`_, _, _, 10, 17, 24, _`

Sluttilstand: _, _, _, 10, 17, 24, _
Se på steg 4. Probingen starter på plass 3, finner nøkkelen 10 der — og
stopper. Løkkebetingelsen er T[i] er ikke tom **and** T[i] er ulik k, og andre
ledd er usant, så løkka avsluttes umiddelbart. T[3] = 10 skriver over den samme
verdien, og tabellen er uendret. Bare én prøve.

Hva galt ville sett ut som. Uten and T[i] er ulik k ville løkka behandlet

plass 3 som opptatt og gått videre til 4, så 5, så 6 — og lagt inn en ny 10-er på
plass 6:
_, _, _, 10, 17, 24, 10
Tabellen har nå to 10-ere. Et søk etter 10 starter på plass 3, finner den første

og returnerer. Den andre kopien er permanent utilgjengelig, og plassen den tar er
tapt.
Fellenote. Dette er andre halvdel av felle #11 — probing som ikke

overskriver en lik nøkkel. Førstehalvdelen var manglende mod N. Begge sitter i

den samme while-linja, og begge koster poeng på sjanger I.

📝Oppgave 3

Sjanger E

En hashtabell har $N = 6$ og $h(k) = k \bmod 6$ . Sett inn 13, 19, 13
og 25 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?

Løkke 4 — søk, og de to kjøretidene (ca. 14 min)

— naturlig pausepunkt —

Å finne igjen en nøkkel bruker nøyaktig samme regnestykke som å sette den inn:
start på $h(k)$ , gå framover med mod N. Forskjellen er hva du gjør underveis og
når du stopper.

Du stopper når du finner nøkkelen — da finnes den — eller når du treffer en tom
plass. Den tomme plassen er beviset på at nøkkelen ikke finnes: hadde den vært
satt inn, ville probing-sekvensen stoppet der, og den ville ligget på den plassen
eller tidligere.

📜Pseudokode-kontrakt: `Contains`

Antagelser om representasjon. Samme som for Insert: T er et array med N
plasser indeksert fra 0, hver plass er tom eller inneholder én nøkkel, og
h(k) = k mod N. Vi antar at ingen nøkler er slettet fra tabellen.

Prebetingelse: ingen. Postbetingelse: returverdien er sant hvis og bare
hvis k finnes i T; tabellen er uendret.

Procedure Contains(T, k)
  Input:  hashtabell T som array med N plasser (indeks fra 0), noekkel k
  Output: sant hvis k finnes i T, ellers usant
  N = T.length
  i = k mod N
  antall = 0
  while T[i] er ikke tom and antall < N:
      if T[i] er lik k:
          return sant
      i = (i + 1) mod N
      antall = antall + 1
  return usant

Invarianten i én setning: når løkka har prøvd plassene $h(k)$ til $i$ , er k
garantert ikke å ligge på noen av dem — så finner du en tom plass, kan k ikke
finnes noe sted.

Hvorfor antall < N? For at søket skal stoppe i en full tabell. Uten
telleren ville probingen gå rundt i ring for alltid når ingen plass er tom og
nøkkelen ikke finnes. Dette er et kanttilfelle sensor gir delpoeng for å ha
tenkt på.

Kjøretid: $O(1)$ forventet, $O(n)$ i verste tilfelle. Verste tilfelle
inntreffer når nøklene ligger i én lang klynge, slik at sekvensen må gjennom hele.
Skriv alltid begge, og skriv alltid ordet «forventet».

✏️Eksempel 4: Søk i tabellen fra eksempel 1

Tabellen fra eksempel 1 er _, 15, 22, 8, 29, 3, _ med $N = 7$ . Søk etter
nøklene 29, 16 og 3, og vis probing-sekvensen for hver.

Nøkkel	$h(k)$	Prøvde indekser	Resultat
29	1	`1 -> 2 -> 3 -> 4`	funnet på plass 4
16	2	`2 -> 3 -> 4 -> 5 -> 6`	ikke funnet — plass 6 er tom
3	3	`3 -> 4 -> 5`	funnet på plass 5

Se på søket etter 16.

16 \bmod 7 = 2

. Sekvensen går gjennom 22, 8, 29 og 3
uten treff, og stopper på plass 6, som er tom. Da vet vi sikkert at 16 ikke finnes
— for hadde den blitt satt inn, ville den ha stoppet på første ledige plass i sin
egen sekvens, og det ville vært plass 6 eller tidligere.

Fem prøver for å konkludere at noe ikke finnes. Det er den prisen
klyngedannelsen krever, og det illustrerer forskjellen mellom forventet og verste
tilfelle bedre enn noen tabell: i en tom tabell hadde det holdt med én prøve.
Merk søket etter 3. Nøkkelen ligger ikke på plass 3, som er dens egen

hashverdi, men på plass 5 — fordi klyngen sperret. Søket finner den likevel, fordi
det følger nøyaktig den samme sekvensen som innsettingen gjorde. Det er hele
grunnen til at probing-regelen må være deterministisk.

En viktig konsekvens du bør merke deg: dette forklarer hvorfor sletting er
vanskelig i lukket hashing. Fjerner du 8 fra plass 3 og lar plassen stå tom, vil
søket etter 29 stoppe på plass 3 og feilaktig melde «ikke funnet». Løsningen er å
markere plassen som slettet i stedet for tom — det er utenfor det som testes her,

men det er verdt å vite at problemet finnes.

📝Oppgave 4

Sjanger E og I

Tabellen 15, 23, 31, _, _, _, 6, 7 med $N = 8$ er resultatet
fra oppgave 2.

a) Søk etter nøkkelen 23. Hvilke indekser prøves?
b) Søk etter nøkkelen 39. Hvilke indekser prøves, og hva blir svaret?
c) Hvorfor kan søket stoppe på en tom plass i stedet for å lete videre?

Typiske feil

De to første er begge felle #11 i bokas feilregister — linear probing som går
utenfor $0$ til $N-1$ , eller som ikke overskriver en lik nøkkel — og de er de to
dyreste i hele Del 3.

- Å glemme mod N i probing-steget. Når en klynge når enden av tabellen, må
neste plass være 0. Skriver du i = i + 1 uten mod N, går indeksen utenfor
arrayet. Kontrollen: ingen indeks i sporingen din skal noen gang være større
enn $N-1$ .
- Å ikke overskrive ved lik nøkkel. Løkkebetingelsen må ha `and T[i] er ulik
k`. Uten den får du duplikater som ingen senere søk vil finne, og klyngen blir
lengre for alle som kommer etter.
- Å oppgi bare de innsatte nøklene i stedet for hele tabellen. Sensor ber om
hele tabellen med _ for tomme plasser. De tomme plassene er en del av
svaret.
- Å regne feil $h(k)$ . $22 \bmod 7$ er 1, ikke 3. Regn ut alle hashverdiene
først, i en egen linje, før du begynner å sette inn. Da har du et regnestykke
å kontrollere mot.
- Å oppgi $O(1)$ uten ordet «forventet». Hashtabellens oppslag er $O(1)$
forventet og $O(n)$ i verste tilfelle. Begge skal med.

Og den gjennomgående: å bruke $n$ og $N$ om hverandre. $N$ er
tabellstørrelsen, $n$ er antall lagrede nøkler. Å bruke dem uten å definere dem er
felle #10 — å oppgi kjøretid uten å si hva størrelsene er.

📝Oppgave 5

Sjanger I

Skriv Insert(T, k) for en hashtabell med lukket hashing og lineær
probing. Oppgi antagelser om representasjon og kjøretid, og forklar de to
detaljene som er lette å utelate.

📝Oppgave 6

Sjanger E, krevende

En hashtabell har $N = 11$ og $h(k) = k \bmod 11$ . Sett
inn 31, 20, 42, 9, 53 og 64 i denne rekkefølgen.

a) Oppgi hele tabellen.
b) Hvor mange prøver kostet hver innsetting, og hva ble totalen?
c) Hva ville skjedd hvis rekkefølgen på nøklene hadde vært motsatt?

📝Oppgave 7

Sjanger I, krevende

En kollega har skrevet denne Insert-prosedyren:

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

a) Finn alle feilene.
b) Vis konkret hva som går galt med $N = 5$ , tabellen _, _, _, 8, 13 og
nøkkelen 18.
c) Skriv en korrekt versjon.

Begrepsbank

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

Probing-sekvensen

h(k)

Wraparound

N-1

Primær klyngedannelse

Fenomenet at nøkler som kolliderer, danner en sammenhengende blokk i tabellen — og at blokken deretter fanger opp nøkler som hasher til hvilken som helst plass inne i den. Konsekvensen er at klynger vokser raskere jo større de er, og at en nøkkel kan bli forskjøvet langt selv om ingen andre nøkler har samme hashverdi. Det er lineær probings viktigste svakhet.

Hele tabellen som svarformat

Sensor ber om hele hashtabellen som sluttilstand, kommaseparert, med_for tomme plasser og indeks fra 0. Å bare liste de innsatte nøklene er felle #11 : de tomme plassene er en del av svaret, fordi de viser at probing-sekvensen ble fulgt riktig.

Hashtabellens forventede kjøretid

O(1)

Hashtabellens verste kjøretid

O(n)

Tom plass som stoppkriterium i søk

Contains stopper og svarer «ikke funnet» når den treffer en tom plass. Argumentet: hadde nøkkelen vært satt inn, ville Insert fulgt samme sekvens og stoppet på den første ledige plassen, altså denne eller en tidligere. Argumentet forutsetter at ingenting er slettet — det er derfor lukket hashing markerer slettede plasser i stedet for å tømme dem.

Tabellstørrelsen N

0

Lukket kontra åpen hashing

Lukket hashing (også kalt åpen adressering) lagrer alle nøkler i selve arrayet og løser kollisjoner ved probing. Åpen hashing (kjeding) lar hver plass peke til en lenket liste med alle nøkler som hasher dit. IN2010 håndkjører lukket hashing med lineær probing. Kjeding nevnes som alternativ, men det er ikke den varianten som testes.

Modulo som operator

k \bmod N

Sjanger E — håndkjøring av datastruktur

Del 1-sjangeren der du får en operasjonsrekke og skal oppgi kun sluttilstanden til strukturen. Minst én per sett, ofte to, og linear probing er den nest hyppigste etter heap. Formatet er strengt: hele tabellen,_for tomme plasser, indeks fra 0. Delvis riktig tilstand gir delvis uttelling, så la aldri svaret stå tomt.

Sjanger I — hashing og søk i pseudokode

n

Hvorfor sletting er vanskelig i lukket hashing

Tømmer du en plass midt i en klynge, vil senere søk stoppe der og feilaktig melde «ikke funnet» for nøkler som ligger lenger ute i sekvensen. Løsningen er å markere plassen som slettet — en tilstand som ikke stopper søk, men som kan gjenbrukes ved innsetting. Detaljen håndkjøres ikke på eksamen, men den forklarer hvorfor Contains -argumentet forutsetter at ingenting er slettet.

Antall prøver som mål på klyngedannelse

Summen av prøver over alle innsettingene sier hvor hardt klyngedannelsen slår til. På en tom tabell er den 1 per innsetting; i en full klynge vokser den lineært. Bruk den som kontrollregning i en håndkjøring: får du 21 prøver på seks nøkler, har du hatt maksimal kollisjon, og det bør stemme med at alle hadde samme hashverdi.

Hashing er tyngre i IN2010 enn i et generisk pensum

Her testes hashing både som håndkjøring (sjanger E) og som pseudokode (sjanger I), i hvert eneste sett — 7 av 7 (100 %). Til sammenligning er hashing i NTNUs TDT4120 et faktapunkt i under halvparten av settene. Kommer du fra et slikt pensum, eller fra en generisk algoritmebok, er dette temaet du systematisk undervurderer.

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.