Inom datavetenskap är en hashtabell en datastruktur för att lagra data som består av en lista med värden, kallade nycklar, som paras ihop med en motsvarande värdelista, som kallas en array. Till exempel kan ett företagsnamn kopplas ihop med dess adress. Vanligtvis har varje värde i arrayen ett positionsnummer som kallas en hash. Hashfunktionen är i allmänhet en uppsättning instruktioner eller en algoritm som mappar varje nyckelvärde till en hash – kopplar företagsnamnet till dess adress, dess telefonnummer och dess företagskategori, till exempel. Syftet med hashfunktionen är att tilldela varje nyckel till ett unikt motsvarande värde i arrayen; detta kallas vanligtvis hashing. Hashfunktioner måste vara korrekt formaterade för att en hashtabell ska fungera korrekt.
Prestandan för en hashtabell på en uppsättning data beror på effektiviteten hos dess hashfunktion. En bra hashfunktion ger vanligtvis en enhetlig uppslagning av nycklar och en jämn fördelning av mappningar i motsvarande array. En hashkollision uppstår när två nycklar tilldelas samma motsvarande värde. När en hashkollision inträffar exekveras hashfunktionen vanligtvis igen tills ett unikt motsvarande värde hittas; detta resulterar vanligtvis i längre hashtider. Även om antalet nycklar i en hashtabell vanligtvis är fast, kan det ibland finnas dubbletter av nycklar. Trots det har en väldesignad hashtabell effektiva hashfunktioner som mappar varje nyckel till ett unikt motsvarande värde i arrayen.
Ibland kan ineffektiva hashfunktioner i en hashtabell 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 slå upp motsvarande värden. Detta kan sakta ner hashningen för framtida nycklar eftersom de flesta hashfunktioner i allmänhet letar efter nästa tillgängliga position i arrayen. Om ett stort kluster av värden redan har tilldelats, skulle det vanligtvis ta mycket längre tid att leta efter ett otilldelat värde för en ny nyckel.
Belastningsfaktorn är ett annat begrepp relaterat till effektiviteten hos en hashfunktion; belastningsfaktorn är mängden redan existerande hashningar i förhållande till den totala storleken på motsvarande array i en hashtabell. Det definieras vanligtvis genom att dividera antalet redan tilldelade nycklar med storleken på motsvarande array. När belastningsfaktorn ö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 – en som inte ger några kollisioner eller kluster med en ökande belastningsfaktor. I teorin är nyckeln till att producera en perfekt hashtabell att producera en perfekt hashfunktion. Generellt anser forskare att en perfekt hashfunktion bör ha konstant prestanda – antalet kollisioner och kluster – med en ökande belastningsfaktor. I värsta fall skulle en perfekt hashfunktion fortfarande möjliggöra konstant hash utan att nå en tröskel.