Hashtabel
Een hashtabel zoals gebruikt in de informatica is een datastructuur waarbij sleutels worden geassocieerd met waardes. Dit wordt primair gebruikt voor een zoekoperatie waar men, voor een gegeven sleutel, bijvoorbeeld een naam, een bijbehorende waarde wil weten, bijvoorbeeld de woonplaats.
De werking van een hashtabel berust op een hashfunctie die de sleutel omzet in een hashwaarde welke gebruikt wordt om de sleutel-waarde combinatie efficiënt te vinden. Gemiddeld genomen levert een hashtabel de gezochte waarde in een constante tijd, O(1), net zoals voor een normale array maar in uitzonderlijke gevallen kan de tijd evenredig zijn met het aantal elementen in de hashtabel O(n). Door de tijd die benodigd is voor het bereken van de hashwaarde en het uiteindelijk vinden van de sleutel-waarde combinatie is een hashtabel het meest geschikt voor gevallen waarbij een groot aantal sleutel-waarde combinaties worden gebruikt.
De onderliggende werking berust erop dat de sleutels worden omgezet in een semi-willekeurig getal, de hashwaarde, in een bepaald bereik. Als een sleutel-waarde combinatie moet worden opgezocht wordt deze hashwaarde gebruikt als index in een lineaire tabel en gekeken of de waarde op de plek van de index overeenkomt met de sleutel. Is dit het geval, dan kan de waarde worden teruggegeven, O(1). Is dit niet het geval dan moet worden nagegaan of niet toevallig meerdere sleutels bestaan met de huidige waarde waardoor de sleutel niet op de index te vinden is maar op een alternative plek bijvoorbeeld de volgende index of in een gelinkte lijst achter de eerst gevonden index of dat de gezochte sleutel in zijn geheel niet aanwezig is in de hashtabel.
Een nadeel van een hashtabel is dat de sleutels eigenlijk willekeurig verdeeld staan in het geheugen. Als toegang tot de sleutels in een bepaalde volgorde nodig is, is dit waarschijnlijk niet de efficiëntste oplossing. In dat geval zou bijvoorbeeld een gebalanceerde binaire boom een betere oplossing kunnen zijn.
Hashtabellen worden in allerlei soorten programma's gebruikt. De meest programmeertalen bieden ondersteuning voor hashtabellen aan in hun standaard bibliotheken; voor C is er bijvoorbeeld GNU GLib. De meeste scripttalen ondersteunen hashtabellen met een speciale syntaxis (bijvoorbeeld Perl, Python, PHP en Ruby). In deze talen worden hashtabellen ook wel veelvoudig gebruikt als datastructuren waarbij ze soms structuren en array's vervangen.
[bewerk] Collisies
Bij het invoegen van items in de hashtabel kan het voorkomen dat de berekende positie al bezet is (een collisie). De volgende methoden kunnen dit probleem oplossen:
