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 mdash;Tilslutning af forretningsnavnet til dets adresse, dets telefonnummer og dets forretningskategori, for eksempel.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.

ydelsen af en hashtable på et datasæt afhænger af effektiviteten af dens hash -funktion.En god hash -funktion giver typisk mulighed 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 der allerede er tildelt en stor klynge af værdier, ville det 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 mdash;En, der producerer ingen kollisioner eller klynger, der er givet en stigende belastningsfaktor.I teorien er nøglen til at producere en perfekt hashtabel at producere en perfekt hash -funktion.Generelt mener forskere, at en perfekt hash -funktion skal have konstant ydeevne mdash;Antallet af kollisioner og klynger mdash;med en stigende belastningsfaktor.I værste fald vil scenarier stadig give mulighed for konstant hashing uden at nå en tærskel.