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 forretningsnavn bli sammenkoblet med adressen. Vanligvis har hver verdi i matrisen et posisjonsnummer referert til som en hasj. Hash -funksjonen er generelt et sett med instruksjoner eller en algoritme som kartlegger hver nøkkelverdi til en hasj - som kobler til forretningsnavnet til adressen, telefonnummeret og forretningskategorien, for eksempel. Hensikten med Hash -funksjonen er å tilordne hver tast til en unik tilsvarende verdi i matrisen; Dette blir ofte referert til som hashing. Hashfunksjoner må formateres riktig for at en hashtable skal fungere ordentlig.

Ytelsen til en hashtable på et sett med data er avhengig av effektiviteten til hashfunksjonen. En god hasjfunksjonstypiskAlly sørger 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 tilordnes samme tilsvarende verdi. Når en hasjkollisjon oppstår, utføres hashfunksjonen vanligvis igjen til en unik tilsvarende verdi er funnet; Dette resulterer ofte i lengre hasjetider. Selv om antall nøkler i en hashtable vanligvis er løst, kan det noen ganger være dupliserte nøkler. Likevel har en godt designet hashtable effektive hashfunksjoner som kartlegger hver tast til en unik tilsvarende verdi i matrisen.

Noen ganger kan ineffektive hash -funksjoner i en hashtable også produsere en klynge av kartlegginger. Hvis en hash -funksjon skaper en klynge av kartlegginger for eksisterende nøkler, kan dette øke tiden det tar å slå opp de tilsvarende verdiene. Dette kan bremse hashing for fremtidige nøkler siden de fleste hasjfunksjoner generelt ser etter den neste tilgjengelige posisjonen i matrisen. Hvis en stor klyngeav verdier er allerede tildelt, det vil vanligvis ta mye lengre 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 allerede eksisterende hashinger i forhold til den totale størrelsen på den tilsvarende matrisen i en hashtable. Det er vanligvis definert ved å dele antall allerede tildelte nøkler med størrelsen på den tilsvarende matrisen. Når belastningsfaktoren øker, vil en god hasjfunksjon normalt fortsatt opprettholde et konstant antall kollisjoner og klynger opp til et visst 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 informatikkforskere har forsøkt å produsere den perfekte hasjfunksjonen - en som ikke produserer noen kollisjoner eller klynger gitt en økende belastningsfaktor. I teorien er nøkkelen til å produsere en perfekt hashtable å proffeDuce 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 scenarier, en perfekt hasjfunksjon fortsatt gi rom for konstant hashing uten å nå en terskel.