Hashtabel

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.

For alternative betydninger, se Tabel (flertydig). (Se også artikler, som begynder med Tabel)

Statisk hashtabel

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

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

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

• File organization and Processing af Allan L. Tharp ISBN 0-471-61766-0

Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.