Hva er en Hashtable?

I informatikk er en hashtable en datastruktur for lagring av data som består av en liste over verdier, kalt nøkler, som blir sammenkoblet med en tilsvarende liste over verdier, kalt en matrise. For eksempel kan et firmanavn bli sammenkoblet med adressen. Vanligvis har hver verdi i matrisen et posisjonsnummer referert til som en hash. Hash-funksjonen er vanligvis et sett med instruksjoner eller en algoritme som kartlegger hver nøkkelverdi til en hash - for eksempel å koble virksomhetsnavnet til adressen, telefonnummeret og virksomhetskategorien. Hensikten med hasjfunksjonen er å tilordne hver tast til en unik tilsvarende verdi i matrisen; dette blir ofte referert til som hashing. Hash-funksjoner må være riktig formatert for at en hashtable skal fungere ordentlig.

Ytelsen til en hashtable på et sett med data er avhengig av effektiviteten til hasjfunksjonen. En god hasjfunksjon sørger typisk for en jevn oppslag av nøkler og en jevn fordeling av kartlegginger i den tilsvarende matrisen. En hasjkollisjon oppstår når to nøkler er tilordnet den samme korresponderende verdien. Når en hasjkollisjon oppstår, utføres hasjfunksjonen vanligvis igjen til en unik tilsvarende verdi blir funnet; dette resulterer ofte i lengre hashing-tider. Selv om antall nøkler i en hashtable vanligvis er fast, kan det noen ganger være dupliserte nøkler. Likevel har en godt designet hashtable effektive hashfunksjoner som kartlegger hver nøkkel til en unik tilsvarende verdi i matrisen.

Noen ganger kan ineffektive hasjfunksjoner i en hashtable også produsere en klynge av kartlegginger. Hvis en hasjfunksjon oppretter en klynge av kartlegginger for eksisterende nøkler, kan dette øke tiden det tar å slå opp de tilsvarende verdiene. Dette kan bremse hasningen for fremtidige nøkler siden de fleste hasjfunksjoner generelt ser etter den neste tilgjengelige posisjonen i matrisen. Hvis det allerede er tilordnet en stor verdiklynge, vil det vanligvis ta mye lenger tid å se etter en ikke tilordnet verdi for en ny nøkkel.

Lastfaktoren er et annet konsept relatert til effektiviteten til en hasjfunksjon; lastfaktoren er mengden av allerede eksisterende hasj i forhold til den totale størrelsen på den tilsvarende arrayen i en hashtable. Det defineres vanligvis ved å dele antall allerede tildelte nøkler med størrelsen på den tilhørende matrisen. Når belastningsfaktoren øker, vil en god hasjfunksjon normalt fremdeles opprettholde et konstant antall kollisjoner og klynger opp til et bestemt punkt. Ofte kan denne terskelen brukes til å bestemme hvor effektiv en hasjfunksjon er med et gitt antall nøkler, og når en ny hasjfunksjon kan være nødvendig.

Mange informasjonsforskere har forsøkt å produsere den perfekte hasjfunksjonen - en som ikke produserer kollisjoner eller klynger som får en økende belastningsfaktor. I teorien er nøkkelen til å produsere en perfekt hashtable å produsere en perfekt hasjfunksjon. Generelt mener forskere at en perfekt hasjfunksjon bør ha konstant ytelse - antall kollisjoner og klynger - med en økende belastningsfaktor. I verste fall vil en perfekt hasjfunksjon fortsatt tillate kontinuerlig hashing uten å nå en terskel.