Hashtabell

Hashtabell er ein av datafagets viktigaste datastrukturar. I staden for å leite gjennom ein serie, som kan ta O(N) i verste fall, eller ei sortert liste på O(log N) tid, vil leitetida i ein hashtabell vere konstant, O(1).

Ei telefonbok lagra i ein hashtabell. Vi ser at namna til abonnenten t.v. blir brukt som nøkkel (key), for å berekne det eigenlege staden i lageret. Kapasiteten i lageret er N=1000 objekt, og i dette tilfellet vil eit objekt vere ein peikar til ytterlegare informasjon om abonnenten.

Leiting etter eit objekt blir iverksett på basis av ein nøkkel x, som klienten oppgjev. Nøkkelen kan vere eit tal eller ei tekst. Plassen blir så berekna til k=h(x), der h(x) er hashfunksjonen som då skal vere utført på O(1) tid. Objektet kan så hentast ut frå plass k, som er ein av dei N-EN plassane til rådvelde. Ein hashtabell blir såleis kalla assosiativ tabell, i og med at han assosierer (kopler) nøkkel og verd (engelsk: key og value).

Lagerstaden er vanlegvis ein tabell i maskina sitt hurtigminne, der ein har O(1) tilgjenge til alle plassane. Den seinare tida har det vorte utvikla distribuerte hashtabellar som spreier lagringa på ei eller fleire maskiner for å auke pålitelegheit og yting. Lageret vil til ei kvar tid ha ein lastfaktor på B/N, der B er mengda belagde plassar.

Viss fleire nøklar blir kopla til same plass oppstår det ein kollisjon. Hashfunksjonen er laga for å unngå kollisjonar, men ved kollisjon må objektet lagrast ein annan stad, til dømes i ekstra datastrukturar (tre, lister, såkalla «chaining»). Ein alternativ teknikk er å ta i bruk neste ledige lagerplass (lineær prøving), eventuelt leite seg eksponensielt fram til ein ledig stad (kvadratisk prøving); ein tredje teknikk er tilfeldig prøving, der ein seriekoplar fleire hashfunksjonar for å berekne staden. Dette aukar tida for å berekne h(x), men er då meint å redusere mengder kollisjonar, og slik gje redusert leitetid. Sjansen for kollisjon aukar med lastfaktor. Ein kan då auke lagerplassen (N), etterfylgd av «rehashing», der objekta blir plassert på det som vil vere ny korrekt stad. Dette er ein O(N) operasjon.

Eksempel på hashfunksjon er h(x) = x MOD N (der nøkkel er eit heiltal). Viss nøkkelen er ei tekst (eksempelvis namnet til ein abonnent, som i figuren) kan h(x) vere berekna ut frå summen av eit utval av teikna til teksta. Målet vil alltid vere å unngå kollisjon, i hovudsak, ved å spreie nytta jamt over tabellen.

Denne informatikkartikkelen er ei spire. Du kan hjelpe Nynorsk Wikipedia gjennom å utvide han.