Hashtabell

En hashtabell eller nøkkeltabell er en av informatikkens viktigste datastrukturer. I stedet for å lete gjennom en serie, som kan ta O(N) i verste fall, eller en sortert liste på $O(logN)$ tid, vil letetiden i en hashtabell være konstant, $O(1)$.

En telefonbok lagret i en hashtabell. Man ser at abonnentens navn t.v. brukes som nøkkel (key), og brukes for å beregne det egentlige sted i lageret. Kapasiteten i lageret er N=1000 objekt, og i dette tilfelle vil et objekt være en peker til ytterligere informasjon om abonnenten.

Leting etter et objekt iverksettes på basis av en nøkkel $x$, som klienten oppgir. Nøkkelen kan være et tall eller en tekst. Plassen beregnes så til $k=h(x)$, der $h(x)$ er hashfunksjonen som da skal være utført på $O(1)$ tid. Objektet kan da hentes ut fra plass $k$, som er en av de $N$ plassene til rådighet. En hashtabell kalles således assosiativ tabell, da den assosierer (kobler) nøkkel og verdi (engelsk: key og value).

Lagerstedet er vanligvis en tabell i maskinens hurtigminne, der man har $O(1)$ tilgang til alle plassene. Man har den senere tid utviklet distribuert hashtabell som sprer lagringen på en eller flere maskiner for å øke pålitelighet og ytelse. Lageret vil til enhver tid ha en lastfaktor på B/N, der B er antall belagte plasser.

Hvis flere nøkler kobles til samme plass oppstår nøkkelkollisjon. Hashfunksjonen er laget for å unngå kollisjoner, men ved kollisjon må objektet lagres et annet sted, for eksempel i ekstra datastrukturer (trær, lister, såkalt «chaining»). En alternativ teknikk er å ta i bruk neste ledige lagerplass (lineær prøving), eventuelt lete seg eksponensielt frem til et ledig sted (kvadratisk prøving); en tredje teknikk er tilfeldig prøving, der man seriekobler flere hashfunksjoner for å beregne stedet. Dette øker tiden for å beregne $h(x)$, men er da ment å redusere antall kollisjoner, og derigjennom gi redusert letetid. Sjansen for kollisjon øker med lastfaktor. Man kan da øke lagerplassen (N), etterfulgt av «rehashing», der objektene plasseres på det som vil være nytt korrekt sted. Dette er en $O(N)$ operasjon.

Eksempler på hashfunksjon er $h(x)=x{\text{ MOD }}N$ (der nøkkel er et heltall). Hvis nøkkelen er en tekst (eksempelvis en abonnents navn, som i figuren) kan $h(x)$ være beregnet ut fra summen av et utvalg av tekstens tegn. Målet vil alltid være å unngå kollisjon, i hovedsak, ved å spre bruken jevnt over tabellen.

Referanser

Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.