Wat is een haspel?
In de informatica is een hashtable een gegevensstructuur voor het opslaan van gegevens die bestaat uit een lijst met waarden, sleutels genoemd, die worden gekoppeld aan een overeenkomstige lijst met waarden, een array genoemd. Een bedrijfsnaam kan bijvoorbeeld worden gekoppeld aan het adres. Gewoonlijk heeft elke waarde in de array een positienummer dat een hash wordt genoemd. De hash-functie is meestal een set instructies of een algoritme dat elke sleutelwaarde toewijst aan een hash, bijvoorbeeld door de bedrijfsnaam te koppelen aan het adres, het telefoonnummer en de bedrijfscategorie. Het doel van de hash-functie is om elke sleutel toe te wijzen aan een unieke overeenkomstige waarde in de array; dit wordt gewoonlijk hashing genoemd. Hash-functies moeten correct zijn opgemaakt om een hashtable goed te laten werken.
De prestaties van een hashtable op een set gegevens zijn afhankelijk van de efficiëntie van de hashfunctie. Een goede hashfunctie zorgt meestal voor een uniforme opzoeking van sleutels en een gelijkmatige verdeling van toewijzingen in de bijbehorende array. Een hashbotsing treedt op wanneer twee sleutels aan dezelfde overeenkomstige waarde worden toegewezen. Wanneer een hashbotsing optreedt, wordt de hashfunctie meestal opnieuw uitgevoerd totdat een unieke overeenkomstige waarde wordt gevonden; dit resulteert meestal in langere hashing-tijden. Hoewel het aantal sleutels in een hashtable meestal vast is, kunnen er soms dubbele sleutels zijn. Toch heeft een goed ontworpen hashtable effectieve hash-functies die elke sleutel toewijzen aan een unieke overeenkomstige waarde in de array.
Soms kunnen inefficiënte hashfuncties in een hashtabel ook een cluster van toewijzingen produceren. Als een hashfunctie een cluster van toewijzingen voor bestaande sleutels maakt, kan dit de hoeveelheid tijd verlengen die nodig is om de bijbehorende waarden op te zoeken. Dit kan de hashing voor toekomstige toetsen vertragen, aangezien de meeste hashfuncties over het algemeen zoeken naar de volgende beschikbare positie in de array. Als er al een groot cluster met waarden is toegewezen, duurt het meestal veel langer om te zoeken naar een niet-toegewezen waarde voor een nieuwe sleutel.
De belastingsfactor is een ander concept dat verband houdt met de efficiëntie van een hashfunctie; de belastingsfactor is de hoeveelheid bestaande hashings in verhouding tot de totale grootte van de overeenkomstige array in een hashtable. Het wordt meestal gedefinieerd door het aantal reeds toegewezen sleutels te delen door de grootte van de bijbehorende array. Naarmate de belastingsfactor toeneemt, behoudt een goede hashfunctie normaal gesproken nog steeds een constant aantal botsingen en clusters tot een bepaald punt. Vaak kan deze drempel worden gebruikt om te bepalen hoe efficiënt een hashfunctie is met een bepaald aantal toetsen en wanneer een nieuwe hashfunctie nodig kan zijn.
Veel informatica-onderzoekers hebben ernaar gestreefd de perfecte hash-functie te produceren - een functie die geen botsingen of clusters oplevert bij een toenemende belastingsfactor. In theorie is de sleutel tot het produceren van een perfecte hashtable het produceren van een perfecte hash-functie. Over het algemeen zijn onderzoekers van mening dat een perfecte hashfunctie constante prestaties moet hebben - het aantal botsingen en clusters - met een toenemende belastingsfactor. In het ergste geval zou een perfecte hashfunctie nog steeds een constante hashing mogelijk maken zonder een drempel te bereiken.