Hashtabel
Een hashtabel of hashmap zoals gebruikt in de informatica is een datastructuur waarbij sleutels worden geassocieerd met waardes. Het is een implementatie van een associatieve array. 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 vaak gebruikt voor de implementatie van configuratiebestanden. 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 andere plaats, 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 verspreid staan in het geheugen: ongebruikte sleutels nemen ruimte in beslag tussen de gebruikte sleutels. 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 standaardbibliotheken; C++ biedt bijvoorbeeld (vanaf de versie C++11) de klasse unordered_map aan en Java de klasse HashMap. 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.
Een hashtabel of hashmap zoals gebruikt in de informatica is een datastructuur waarbij sleutels worden geassocieerd met waardes. Het is een implementatie van een associatieve array. 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 vaak gebruikt voor de implementatie van configuratiebestanden.
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 andere plaats, 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 verspreid staan in het geheugen: ongebruikte sleutels nemen ruimte in beslag tussen de gebruikte sleutels. 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 standaardbibliotheken; C++ biedt bijvoorbeeld (vanaf de versie C++11) de klasse unordered_map aan en Java de klasse HashMap. 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 | brontekst bewerken]Bij het invoegen van items in de hashtabel kan het voorkomen dat de berekende positie al bezet is (een botsing of collision). Soms kan de oude waarde simpelweg verwijderd worden, bijvoorbeeld wanneer de hashtabel gebruikt wordt voor de implementatie van een cache. Wanneer de oude waarde niet verwijderd mag worden kan voor een van de volgende methoden gekozen worden: