Hashtabel

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een hashtabel of hashmap 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.

Hashtabellen worden zeer vaak gebruikt in een configuratiebestand.

De werking van een hashtabel berust op een hashfunctie die de sleutel omzet in een hashwaarde die 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 berekenen van de hashwaarde en het uiteindelijk vinden van de combinatie is een hashtabel het meest geschikt voor gevallen waarbij een groot aantal combinaties worden gebruikt.

De onderliggende werking berust erop dat de sleutels met behulp van een hashfunctie worden omgezet in een semi-willekeurig getal, de hashwaarde, in een bepaald bereik. Als een 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 meeste 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 arrays vervangen.

Collisies[bewerken]

Bij het invoegen van items in de hashtabel kan het voorkomen dat de berekende positie al bezet is (een botsing of collision). De volgende methoden kunnen dit probleem oplossen: