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 og mdash;Koble forretningsnavnet til adressen, for eksempel telefonnummeret og dets forretningskategori.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 hasjfunksjon gir vanligvis en jevn oppslag av nøkler og en jevn distribusjon 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 klynge av verdier allerede er tildelt, vil det 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 mdash;En som ikke produserer noen kollisjoner eller klynger gitt 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 og mdash;antall kollisjoner og klynger og mdash;med en økende belastningsfaktor.I verste fall vil en perfekt hasjfunksjon fortsatt gi rom for konstant hashing uten å nå en terskel.