Hashtabel

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

En hashtabel er en datastruktur, hvor man hurtigt kan finde data ud fra en nøgle. Nøglen behandles med en hashfunktion, og resultatet bruges som indeks til selve opslaget.

Statisk hashtabel[redigér | redigér wikikode]

I en statisk hashtabel er størrelsen af tabellen givet på forhånd. En enkel hashfunktion kunne være h(nøgle) = nøgle modulo tabellængden.

I tabellen gemmes tre ting i hver række. Nøglen, de tilhørende data og oplysninger om der er andre data, med den aktuelle hashværdi.

Eksempel[redigér | redigér wikikode]

Et simpelt eksempel: Data gemmes i en tabel med plads til 11 poster. Det antages, at nøglen er et heltal. Hashfunktionen er h(nøgle) = nøgle modulo 11.

Hvis data med nøglerne 5, 14, 23, 32 og 42 indsættes, ser det sådan ud:

Index Nøgle Kollision

 0
 1    23
 2
 3    14
 4
 5     5
 6
 7
 8
 9    42
10    32

Hvis der som i eksemplet ingen kollision er, kan data findes direkte. Det rigtige indeks kan beregnes entydigt ud fra nøglen. Kollisioner opstår, når to eller flere nøgler giver samme hash-værdi. Hvis der i tabellen ovenfor blev tilføjet data med nøglen 3, ville der opstå en kollision. Både h(14) og h(3) giver 3.

Kollisioner[redigér | redigér wikikode]

Alt efter, hvordan hashtabellen er designet behandles kollisioner forskelligt. En mulighed er, at afsætte plads til de ekstra data, og så gennemsøge dette område sekventielt. Hvis der er plads til det, kan det registreres, hvilken adresse de kolliderende data befinder sig på:

Index Nøgle Kollision

 0
 1    23
 2
 3    14     11
 4
 5     5
 6
 7
 8
 9    42
10    32
--------------------
11     3
12
13
14
15

Da der også er et adressefelt i overløbsområdet, kan flere kollisioner på samme adresse håndteres så længe, der er plads.

Tidskompleksitet
Operation Relativ tid
Find O(1)
Indsæt O(1)
Slet O(1)

Kilder[redigér | redigér wikikode]

It Stub
Denne it-artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.