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 - som ansluter företagsnamnet till sin adress, dess 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 formateras korrekt för att en hashtable ska fungera korrekt.

Prestanda för en hashtable på en uppsättning data är beroende av effektiviteten i dess hashfunktion. En bra hashfunktionstypAlly tillhandahåller 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 hashtabla också producera ett kluster av mappningar. 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 klusterav värden har redan tilldelats, det skulle 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; Belastningsfaktorn är mängden redan befintliga hashingar i förhållande till den totala storleken på motsvarande matris i en hashtable. 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 datavetenskapliga forskare har strävat efter att producera den perfekta hashfunktionen - en som inte producerar några kollisioner eller kluster med tanke på en ökande belastningsfaktor. I teorin är nyckeln till att producera en perfekt hashtable till proffsStår av en perfekt hashfunktion. I allmänhet tror forskare att en perfekt hash -funktion bör ha konstant prestanda - antalet kollisioner och kluster - med en ökande lastfaktor. I värsta fall skulle en perfekt hashfunktion fortfarande möjliggöra konstant hashing utan att nå en tröskel.