Hashtabel: verschil tussen versies

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, ''[[Complexiteitsgraad#Begrenzing_van_boven|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.

 

 

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 <code>unordered_map</code> aan en [[Java (programmeertaal)|Java]] de klasse <code>HashMap</code>. De meeste [[scripttaal|scripttalen]] ondersteunen hashtabellen met een speciale [[Syntaxis (informatica)|syntaxis]] (bijvoorbeeld [[Perl (programmeertaal)|Perl]], [[Python (programmeertaal)|Python]], [[PHP]] en [[Ruby (programmeertaal)|Ruby]]). In deze talen worden hashtabellen ook wel veelvoudig gebruikt als datastructuren waarbij ze soms structuren en arrays vervangen.