Vad är en hashtable?

I datavetenskap är en hashtable en datastruktur för att lagra data som består av en lista med värden, kallade nycklar, som kopplas ihop med en motsvarande lista över värden, kallad en matris.Till exempel kan ett företagsnamn kopplas ihop med sin adress.Vanligtvis har varje värde i matrisen ett positionsnummer som kallas en hash.Hash -funktionen är i allmänhet en uppsättning instruktioner eller en algoritm som kartlägger varje nyckelvärde till en hash mdash;Ansluta företagsnamnet till sin adress, sitt telefonnummer och dess affärskategori, till exempel.Syftet med hash -funktionen är att tilldela varje nyckel till ett unikt motsvarande värde i matrisen;Detta kallas vanligtvis hashing.Hash -funktioner måste vara korrekt formaterade för att en hashtable ska fungera korrekt.

EN Hashtables prestanda på en uppsättning data beror på effektiviteten i dess hashfunktion.En bra hashfunktion ger vanligtvis en enhetlig uppslag av nycklar och en jämn fördelning av kartläggningar i motsvarande matris.En hashkollision inträffar när två nycklar tilldelas samma motsvarande värde.När en hashkollision inträffar körs hash -funktionen vanligtvis igen tills ett unikt motsvarande värde hittas;Detta resulterar vanligtvis i längre hashtider.Även om antalet nycklar i en hashtable vanligtvis är fixerad, kan det ibland finnas duplicerade nycklar.Trots detta har en väl utformad hashtable effektiva hashfunktioner som kartlägger varje nyckel till ett unikt motsvarande värde i matrisen.

Ibland kan ineffektiva hashfunktioner i en hashtable också producera ett kluster av kartläggningar.Om en hashfunktion skapar ett kluster av mappningar för befintliga nycklar, kan detta öka den tid det tar att leta upp motsvarande värden.Detta kan bromsa hashing för framtida nycklar eftersom de flesta hashfunktioner i allmänhet letar efter nästa tillgängliga position i matrisen.Om ett stort kluster av värden redan har tilldelats skulle det vanligtvis ta mycket längre tid att leta efter ett oöverskådligt värde för en ny nyckel.

Lastfaktorn är ett annat koncept relaterat till effektiviteten i en hashfunktion;Lastfaktorn är mängden redan befintliga hashingar i förhållande till den totala storleken på motsvarande matris i en hashtabell.Det definieras vanligtvis genom att dela antalet redan tilldelade nycklar efter storleken på motsvarande matris.När lastfaktorn ökar kommer en bra hashfunktion normalt fortfarande att upprätthålla ett konstant antal kollisioner och kluster upp till en viss punkt.Ofta kan denna tröskel användas för att bestämma hur effektiv en hashfunktion är med ett givet antal nycklar och när en ny hashfunktion kan behövas.

Många datavetenskapsforskare har strävat efter att producera den perfekta hashfunktionen mdash;en som inte producerar några kollisioner eller kluster med tanke på en ökande lastfaktor.I teorin är nyckeln till att producera en perfekt hashtable att producera en perfekt hashfunktion.I allmänhet tror forskare att en perfekt hashfunktion bör ha konstant prestanda och mdash;antalet kollisioner och kluster mdash;med en ökande lastfaktor.I värsta fall skulle en perfekt hashfunktion fortfarande möjliggöra konstant hashing utan att nå en tröskel.