Hvad er en Hashtable?
Inden for datalogi er en hashtable en datastruktur til lagring af data, der består af en liste over værdier, kaldte taster, som bliver parret med en tilsvarende liste over værdier, kaldet en matrix. For eksempel kan et forretningsnavn muligvis parres med dets adresse. Typisk har hver værdi i matrixen et positionsnummer, der omtales som en hash. Hash-funktionen er generelt et sæt instruktioner eller en algoritme, der kortlægger hver nøgleværdi til en hash - forbinder f.eks. Virksomhedsnavnet til dens adresse, sit telefonnummer og dets forretningskategori. Formålet med hashfunktionen er at tildele hver nøgle til en unik tilsvarende værdi i matrixen; dette kaldes ofte hashing. Hash-funktioner skal være formateret korrekt for at en hashtable skal fungere korrekt.
Udførelsen af en hashtable på et datasæt afhænger af effektiviteten af dens hashfunktion. En god hash-funktion sørger typisk for en ensartet opslag af nøgler og en jævn fordeling af kortlægninger i det tilsvarende array. En hash-kollision opstår, når to taster tildeles den samme tilsvarende værdi. Når der sker en hash-kollision, udføres hash-funktionen normalt igen, indtil der findes en unik tilsvarende værdi; dette resulterer ofte i længere hashingtider. Selvom antallet af nøgler i en hashtable normalt er fast, kan der undertiden være duplikatnøgler. Alligevel har en godt designet hashtable effektive hashfunktioner, der kortlægger hver nøgle til en unik tilsvarende værdi i matrixen.
Nogle gange kan ineffektive hashfunktioner i en hashtable også producere en klynge af kortlægninger. Hvis en hash-funktion opretter en klynge af kortlægning af eksisterende taster, kan dette øge den tid, det tager at slå de tilsvarende værdier op. Dette kan bremse hasningen for fremtidige taster, da de fleste hashfunktioner generelt ser efter den næste tilgængelige position i matrixen. Hvis der allerede er tildelt en stor klynge af værdier, vil det typisk tage meget længere tid at se efter en ikke-tildelt værdi for en ny nøgle.
Belastningsfaktoren er et andet koncept relateret til effektiviteten af en hashfunktion; belastningsfaktoren er mængden af allerede eksisterende hashings i forhold til den samlede størrelse af den tilsvarende array i en hashtable. Det defineres normalt ved at dele antallet af allerede tildelte nøgler med størrelsen på den tilsvarende array. Når belastningsfaktoren stiger, opretholder en god hashfunktion normalt stadig et konstant antal kollisioner og klynger op til et bestemt punkt. Ofte kan denne tærskel anvendes til at bestemme, hvor effektiv en hash-funktion er med et givet antal taster, og hvornår en ny hash-funktion kan være nødvendig.
Mange datalogiske forskere har bestræbt sig på at producere den perfekte hash-funktion - en, der ikke producerer kollisioner eller klynger, der får en stigende belastningsfaktor. I teorien er nøglen til at fremstille en perfekt hashtable at producere en perfekt hash-funktion. Generelt mener forskere, at en perfekt hashfunktion bør have konstant ydeevne - antallet af kollisioner og klynger - med en stigende belastningsfaktor. I værste fald ville en perfekt hashfunktion stadig give mulighed for konstant hashing uden at nå en tærskel.