Hvad er en hashtable?
I datalogi er en hashtable en datastruktur til lagring af data, der består af en liste over værdier, kaldet Keys, der bliver parret med en tilsvarende liste over værdier, kaldet en matrix. For eksempel kan et forretningsnavn blive parret med sin adresse. Typisk har hver værdi i matrixen et positionsnummer, der kaldes en hash. Hash -funktionen er generelt et sæt instruktioner eller en algoritme, der kortlægger hver nøgleværdi til en hash - for eksempel at forbinde forretningsnavnet til dets adresse, dets telefonnummer og dets forretningskategori. Formålet med hash -funktionen er at tildele hver nøgle til en unik tilsvarende værdi i matrixen; Dette omtales ofte som hashing. Hash -funktioner skal være korrekt formateret til en hashtable for at fungere korrekt.
Udførelsen af en hashtable på et datasæt afhænger af effektiviteten af dens hash -funktion. En god hashfunktionstypiskAlly sørger for en ensartet opslag af nøgler og en jævn fordeling af kortlægninger i den tilsvarende matrix. En hash -kollision opstår, når to nøgler tildeles den samme tilsvarende værdi. Når en hash -kollision opstår, udføres hash -funktionen normalt igen, indtil der findes en unik tilsvarende værdi; Dette resulterer ofte i længere hashing -tider. 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 hash-funktioner, 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ægninger for eksisterende nøgler, kan dette øge den tid, det tager at opkøre de tilsvarende værdier. Dette kan bremse hashing for fremtidige nøgler, da de fleste hash -funktioner generelt ser efter den næste tilgængelige position i matrixen. Hvis en stor klyngeAf værdier er allerede tildelt, det vil typisk tage meget længere tid at se efter en ikke -tildelt værdi for en ny nøgle.
Lastfaktoren er et andet koncept relateret til effektiviteten af en hash -funktion; Lastfaktoren er mængden af allerede eksisterende hashinger i forhold til den samlede størrelse af den tilsvarende matrix i en hashtable. Det defineres normalt ved at dividere antallet af allerede tildelte nøgler efter størrelsen på den tilsvarende matrix. Når belastningsfaktoren øges, vil en god hash -funktion normalt stadig opretholde et konstant antal kollisioner og klynger op til et bestemt punkt. Ofte kan denne tærskel bruges til at bestemme, hvor effektiv en hash -funktion er med et givet antal nøgler, og hvornår en ny hash -funktion kan være nødvendig.
Mange datalogi -forskere har bestræbt sig på at producere den perfekte hash -funktion - en, der ikke producerer nogen kollisioner eller klynger, der er givet en stigende belastningsfaktor. I teorien er nøglen til at producere en perfekt hashtabel at proDuce en perfekt hash -funktion. Generelt mener forskere, at en perfekt hash -funktion skal have konstant ydelse - antallet af kollisioner og klynger - med en stigende belastningsfaktor. I værste fald vil scenarier stadig give mulighed for konstant hashing uden at nå en tærskel.