For alternative betydninger, seTabel (flertydig).(Se også artikler, som begynder med Tabel)Enhashtabel er endatastruktur, hvor man hurtigt kan finde data ud fra en nøgle. Nøglen behandles med enhashfunktion, og resultatet bruges som indeks til selve opslaget.
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.
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 4210 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.
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 4210 32--------------------11 312131415
Da der også er et adressefelt i overløbsområdet, kan flere kollisioner på samme adresse håndteres så længe, der er plads.
| Operation | Relativ tid |
|---|---|
| Find | O(1) |
| Indsæt | O(1) |
| Slet | O(1) |
 | Spire Denne artikel omdatalogi eller et datalogi-relateret emne er enspire som bør udbygges. Du er velkommen til athjælpe Wikipedia ved atudvide den. |
