Hashtabel: verschil tussen versies

De werking van een hashtabel berust op een [[hashfunctie]] die de sleutel omzet in een ''hashwaarde'' welkediee 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 berekenberekenen 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.

Hashtabellen worden in allerlei soorten programma's gebruikt. De meeste programmeertalen bieden ondersteuning voor hashtabellen aan in hun standaard bibliotheken; voor [[C (programmeertaal)|C]] is er bijvoorbeeld [[GNU]] GLib. 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 array'sarrays vervangen.

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