Referanseside · Kapittel 11

Begreper & formler

Alle nøkkelbegrepene og formlene fra Hash-tabeller, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Direkte adressering

Bruker nøkkelen direkte som indeks når nøkkelområdet er lite.

02Hash-funksjon

En funksjon $h (k)$ som beregner en tabellindeks fra nøkkelen $k$ .

03Kollisjon

Når to nøkler får samme hash-verdi, må de håndteres via kjeding eller åpen adressering.

04Kjeding (chaining)

Hver tabellplass peker på en lenket liste med elementer som har samme hash-verdi.

05Åpen adressering

Lagrer alle elementene direkte i tabellen og søker etter neste ledige plass ved kollisjon.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

α = \frac{n}{m}

O (1 + α)

h_{a, b} (k) = ((ak + b) mod p) mod m