Vad är en Hashtable?

Inom datavetenskap är en hashtable en datastruktur för lagring av data som består av en lista med värden, kallade nycklar, som kommer att kopplas ihop med en motsvarande lista med värden, kallad en matris. Till exempel kan ett företagsnamn kopplas ihop med dess adress. Typiskt har varje värde i matrisen ett positionsnummer som kallas en hash. Hashfunktionen är vanligtvis en uppsättning instruktioner eller en algoritm som kartlägger varje nyckelvärde till en hash - till exempel kopplar företagsnamnet till sin adress, dess telefonnummer och dess verksamhetskategori. Syftet med hashfunktionen är att tilldela varje nyckel till ett unikt motsvarande värde i arrayen; detta kallas ofta hashing. Hashfunktioner måste vara korrekt formaterade för att en hashtable ska fungera korrekt.

Prestandan för en hashtable på en uppsättning data är beroende av effektiviteten i dess hashfunktion. En bra hashfunktion tillhandahåller vanligtvis en enhetlig sökning av nycklar och en jämn fördelning av kartläggningar i motsvarande matris. En hashkollision uppstår när två tangenter tilldelas samma motsvarande värde. När en hashkollision inträffar körs hashfunktionen vanligtvis igen tills ett unikt motsvarande värde hittas; detta resulterar ofta i längre hashtider. Även om antalet nycklar i en hashtable vanligtvis är fast kan det ibland finnas duplikatnycklar. Trots det har en väl designad 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 slå motsvarande värden. Detta kan bromsa hasningen för framtida nycklar eftersom de flesta hash-funktioner i allmänhet letar efter nästa tillgängliga position i matrisen. Om ett stort kluster av värden redan har tilldelats, tar det vanligtvis mycket längre tid att leta efter ett otilldelat värde för en ny nyckel.

Lastfaktorn är ett annat koncept relaterat till effektiviteten hos en hashfunktion; lastfaktorn är mängden redan existerande hasningar i förhållande till den totala storleken på motsvarande matris i en hashtable. Det definieras vanligtvis genom att dela antalet redan tilldelade nycklar med storleken på motsvarande array. 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 tangenter 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 kollisioner eller kluster med en ökande belastningsfaktor. I teorin är nyckeln till att producera en perfekt hashtable att producera en perfekt hash-funktion. I allmänhet anser forskare att en perfekt hashfunktion 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 hasning utan att nå en tröskel.