Gepubliceerd op 25 augustus 2026 · Bijgewerkt op 31 augustus 2026 · 16 min leestijd

Hashtabellen uitgelegd

Stel je een garderobe met een miljoen jassen voor. Voor iedere jas noteert de medewerker een afhaalcode en de plank waarop de jas ligt. Eén regel kan de code CAT verbinden aan plank 12. Wanneer de eigenaar terugkomt, moet de medewerker die korte code weer omzetten in de juiste plank. De eenvoudigste administratie is één lange lijst. De medewerker begint bij de eerste regel en vergelijkt afhaalcodes totdat CAT verschijnt. Dat werkt, maar een ongunstige zoekopdracht bekijkt bijna alle miljoen regels. In een gesorteerde lijst kan een halverende zoekmethode sneller zoeken, maar iedere nieuwe regel moet dan wel op de juiste plek worden ingevoegd. Ook het bewaren van die volgorde kost werk.

Een hashtabel kiest een minder ordelijke route. Ze zet de afhaalcode om in een getal en gebruikt dat getal om een klein deel van een array te kiezen. De medewerker doorzoekt meestal een kort groepje regels in plaats van de hele verzameling. Daar staat tegenover dat de tabel meer geheugen reserveert dan alleen haar regels nodig hebben en dat verschillende afhaalcodes soms dezelfde plek kiezen. De tabel moet extra administratie bijhouden wanneer dat gebeurt. We krijgen daarmee een exacte datastructuur waarvan de gewone bewerkingen snel zijn. Opzoeken, invoegen en verwijderen kosten gemiddeld constante tijd wanneer de tabel genoeg vrije ruimte heeft en haar sleutels goed verspreidt. Constante tijd betekent dat de verwachte hoeveelheid werk niet groeit met het aantal opgeslagen regels. Het betekent niet één processorinstructie en belooft ook geen gelijke uitvoeringstijd voor iedere zoekopdracht. Als veel sleutels op dezelfde plek terechtkomen, kan de tabel alsnog iedere regel moeten bekijken.

Hoe werkt een hashtabel?

Een hashtabel bewaart sleutel-waardeparen. De sleutel wijst een waarde aan. In het garderobevoorbeeld is CAT de sleutel en plank 12 de waarde. De klant toont de sleutel en de medewerker wil de bijbehorende waarde terugvinden. Een gewone array biedt al snelle toegang als het programma een numerieke positie kent. Stel je die array voor als een rij genummerde plekken in het geheugen, met plek 0, plek 1, plek 2 en zo verder. Het programma kan uitrekenen waar een bekende plek zich bevindt en haar rechtstreeks lezen. Alleen is de tekst CAT nog geen geldige arraypositie. We hebben een herhaalbare berekening nodig die er een getal van maakt.

Zo’n berekening heet een hashfunctie. Ze ontvangt een sleutel en geeft een geheel getal terug dat we de hashcode noemen. Voor een klein voorbeeld maken we een oefenfunctie die de tekencode van iedere letter optelt. Tekencodes zijn getallen waarmee de computer tekst in het geheugen voorstelt. Hier is C gelijk aan 67, A aan 65 en T aan 84.

hashcode voor "CAT" = 67 + 65 + 84 = 216

Deze oefenfunctie is expres slecht. Woorden met dezelfde letters krijgen dezelfde uitkomst en soortgelijke tekst hoopt zich snel op. Echte hashfuncties mengen hun invoer zorgvuldiger. De eenvoudige optelling is hier nuttig omdat we haar kunnen volgen zonder de tabel achter pagina’s rekenwerk te verbergen.

Onze tabel heeft een array met acht plekken, die we buckets noemen. Iedere bucket is een bakje waarin straks een klein aantal regels past. Hashcode 216 kan geen arraypositie zijn, want de enige geldige posities lopen van 0 tot en met 7. Het programma deelt 216 door acht en bewaart de rest. Deze restbewerking geeft altijd een getal dat in de array past.

216 gedeeld door 8 laat rest 0 over
bucketindex voor "CAT" = 0

De hashcode en bucketindex zijn verschillende getallen. De hashfunctie maakte hashcode 216 uit de sleutel. Daarna combineerde de tabel 216 met haar huidige arraygrootte om bucket 0 te kiezen. Dat verschil wordt belangrijk wanneer de array later groter wordt.

De buckets in het geheugen volgen

We handelen botsingen af met een methode die separate chaining heet, oftewel aparte ketens. Iedere bucket bewaart een verwijzing naar een korte lijst met regels. Zo’n verwijzing vertelt het programma waar andere gegevens in het geheugen staan. Iedere regel bevat zowel de oorspronkelijke sleutel als de bijbehorende waarde. Aan het begin reserveert het programma een array met acht lege buckets.

bucket 0 -> leeg
bucket 1 -> leeg
bucket 2 -> leeg
bucket 3 -> leeg
bucket 4 -> leeg
bucket 5 -> leeg
bucket 6 -> leeg
bucket 7 -> leeg

Voeg nu CAT -> plank 12 toe. Het programma berekent hashcode 216, kiest bucket 0 en vindt daar geen regels. Het reserveert geheugen voor een nieuwe regel met de oorspronkelijke sleutel CAT en de waarde plank 12. Bucket 0 krijgt een verwijzing naar die regel. De andere zeven buckets veranderen niet.

bucket 0 -> [CAT, plank 12]
bucket 1 -> leeg
bucket 2 -> leeg
bucket 3 -> leeg
bucket 4 -> leeg
bucket 5 -> leeg
bucket 6 -> leeg
bucket 7 -> leeg

Voeg daarna ACT -> plank 31 toe. De letters hebben dezelfde tekencodes in een andere volgorde, dus onze oefenfunctie geeft opnieuw 216 terug. Ook deze sleutel kiest bucket 0. Dit is een botsing. Twee ongelijke sleutels hebben dezelfde bucket gekozen, maar dat bewijst niet dat de sleutels gelijk zijn en betekent ook niet dat de tabel is mislukt. Het programma reserveert een tweede regel en voegt die toe aan de lijst van bucket 0. De eerste garderoberegel blijft staan.

bucket 0 -> [CAT, plank 12] -> [ACT, plank 31]
bucket 1 -> leeg
bucket 2 -> leeg
bucket 3 -> leeg
bucket 4 -> leeg
bucket 5 -> leeg
bucket 6 -> leeg
bucket 7 -> leeg

Een zoekopdracht naar ACT herhaalt dezelfde hashberekening en gaat rechtstreeks naar bucket 0. Het programma vergelijkt de gevraagde sleutel eerst met de opgeslagen sleutel CAT. Ze verschillen, dus het volgt de volgende verwijzing en vergelijkt ACT met ACT. Die vergelijking slaagt en het programma geeft plank 31 terug. De hash heeft het zoekgebied beperkt tot één bucket. De vergelijking van de oorspronkelijke sleutels bepaalde welke regel de juiste was.

Een waarde bijwerken volgt dezelfde route. Stel dat de jas met code CAT naar plank 44 verhuist. Het programma doorzoekt bucket 0, vindt de bestaande regel voor CAT en vervangt alleen plank 12 door plank 44. Het reserveert geen tweede regel, waardoor de tabel nog steeds twee sleutel-waardeparen bevat.

Een bruikbare hashfunctie moet aan een paar voorwaarden voldoen. Een onveranderde sleutel moet dezelfde hashcode blijven geven zolang ze in de tabel staat. Twee sleutels die het programma als gelijk beschouwt, moeten ook dezelfde hashcode hebben. De uitkomsten horen realistische sleutels over de buckets te verspreiden in plaats van ze in een paar lijsten op te hopen. Ongelijke sleutels mogen nog steeds dezelfde uitkomst hebben. Daarom heeft iedere correcte tabel zowel een botsingsstrategie als gelijkheidscontroles nodig.

Het woord “hash” komt ook voor in de cryptografie, maar daar liggen de prioriteiten anders. De hashfunctie van een tabel is vooral gekozen voor snelheid en een goede verspreiding. Sommige ontwerpen beschermen zich daarnaast tegen botsingen die een aanvaller doelbewust maakt. De functie verbergt een sleutel niet automatisch en maakt terugrekenen niet vanzelf onhaalbaar. Cryptografische hashfuncties zijn voor andere garanties ontworpen.

Hoe werkt een hashtabel in code?

De pseudocode hieronder maakt dezelfde tabel met acht buckets. De bewerkingen zijn als woorden geschreven en de botsingslijsten blijven zichtbaar, zodat iedere verandering in het geheugen te volgen is. maakArrayMet roept zijn functie één keer per bucket aan, waardoor iedere bucket een eigen lijst krijgt. voegToeAan voegt een regel aan de gekozen lijst toe zonder de lijst te vervangen.

; Het geheugen begint met een array van acht lege bucketlijsten.
(define aantalBuckets 8)
(define buckets
  (maakArrayMet aantalBuckets (function () (maakLegeLijst))))
(define aantalRegels 0)

(define hashSleutel (function sleutel)
  (define hashcode 0)

  (forEach teken sleutel
    (set hashcode
      (telOp hashcode (tekencode teken))))

  (return hashcode)))

(define bucketIndexVoor (function sleutel)
  (return (rest (hashSleutel sleutel) aantalBuckets))))

(define stelWaardeIn (function sleutel waarde)
  (define bucketIndex (bucketIndexVoor sleutel))
  (define bucketRegels (leesArray buckets bucketIndex))

  ; Een gelijke sleutel in deze bucket betekent dat dit een wijziging is.
  ; Alleen de waarde vervangen reserveert geen dubbele regel.
  (forEach regel bucketRegels
    (if (gelijk (regelSleutel regel) sleutel)
      (do
        (stelRegelWaardeIn regel waarde)
        (return))))

  ; Deze bucket bevat geen gelijke sleutel.
  ; Reserveer één regel en voeg haar verwijzing toe aan de bucketlijst.
  (voegToeAan bucketRegels (maakRegel sleutel waarde))
  (set aantalRegels (telOp aantalRegels 1))))

(define haalWaardeOp (function sleutel)
  (define bucketIndex (bucketIndexVoor sleutel))
  (define bucketRegels (leesArray buckets bucketIndex))

  ; Een zoekopdracht verandert het opgeslagen geheugen niet.
  ; Alleen de gekozen bucket wordt doorlopen.
  (forEach regel bucketRegels
    (if (gelijk (regelSleutel regel) sleutel)
      (return (regelWaarde regel))))

  (return nietGevonden)))

(stelWaardeIn "CAT" "plank 12")
; bucket 0 bevat nu [CAT, plank 12].

(stelWaardeIn "ACT" "plank 31")
; Na [CAT, plank 12] staat nu [ACT, plank 31] in bucket 0.

(haalWaardeOp "ACT")
; Geeft "plank 31" terug na twee sleutelvergelijkingen.
; De buckets en regels blijven gelijk.

(stelWaardeIn "CAT" "plank 44")
; De waarde van de eerste regel verandert. aantalRegels blijft 2.

Volg de eerste toevoeging in het geheugen. hashSleutel begint met een tijdelijk getal op nul en vervangt het terwijl de functie ieder teken leest. Na C, A en T bevat dat getal 216. bucketIndexVoor brengt het terug tot nul. stelWaardeIn leest de verwijzing op arraypositie nul, vindt een lege lijst en voegt een nieuw aangemaakte regel toe. De tijdelijke berekening kan daarna verdwijnen. Het opgeslagen geheugen bestaat uit de bucketarray, de lijstverwijzing en de regel met beide tekstreeksen.

De zoekopdracht reserveert geen nieuwe regel en verplaatst niets. Ze berekent dezelfde positie, leest de lijstverwijzing en loopt door de regels die daar al staan. Als geen enkele opgeslagen sleutel gelijk is aan de gevraagde sleutel, geeft ze nietGevonden terug. In een echte interface moet dat resultaat te onderscheiden zijn van een waarde die de aanroeper mag opslaan. Programmeertalen lossen dit op met een aparte aanwezigheidsvlag, een resultaat dat expliciet een waarde of niets voorstelt, of een fout voor een ontbrekende sleutel.

Wanneer worden hashtabellen gebruikt?

Veel programmeertalen gebruiken een hashtabel achter een bekend ingebouwd type. Een Python-dictionary verbindt sleutels aan waarden, waardoor een uitdrukking zoals gebruikerPerEmail[email] dit idee achter de korte schrijfwijze gebruikt. De implementatie hoeft niet met de gekoppelde lijsten uit ons oefenvoorbeeld te werken, maar ze hasht nog steeds het e-mailadres, controleert mogelijke regels en vergelijkt de sleutels. Een hashset gebruikt soortgelijke techniek wanneer een programma alleen sleutels hoeft te onthouden. Stel dat een import een miljoen e-mailadressen bevat en dubbele adressen moet weigeren. Het programma kan ieder adres in een hashset plaatsen en daarna vragen of het volgende adres al aanwezig is. Het hoeft niet voor iedere nieuwe rij alle eerdere adressen te doorzoeken. De set bewaart geen afzonderlijke plankwaarde, want het lidmaatschap zelf is de nuttige informatie.

Compilers gebruiken hashtabellen om namen in broncode te verbinden aan informatie over variabelen en functies. Caches verbinden een identificator voor een verzoek aan een eerder berekend resultaat. Webtoepassingen kunnen actieve sessies indexeren met een willekeurige sessiecode en spellen kunnen objectnamen aan de objecten zelf verbinden. Al deze toepassingen stellen met één exacte sleutel dezelfde vraag: “Welke waarde hoort bij deze sleutel?”

Databases gebruiken de structuur ook. Tijdens een hash join kan PostgreSQL rijen uit één invoer lezen en een hashtabel bouwen met de joinkolom als sleutel. Daarna leest de database de andere invoer, hasht ze iedere joinwaarde en controleert ze de bijbehorende bucket op rijen die samengevoegd moeten worden. Zo hoeft PostgreSQL niet iedere rij aan de ene kant met iedere rij aan de andere kant te vergelijken. De databaseplanner kijkt nog steeds naar de hoeveelheid gegevens, het beschikbare geheugen en andere mogelijke plannen voordat die voor een hash join kiest.

Een hashtabel past slecht bij een vraag die van volgorde afhangt. De bucketposities volgen geen alfabetische of numerieke volgorde, waardoor de tabel niet vanzelf antwoord geeft op “geef alle tijdstippen tussen 10.00 en 11.00 uur” of “vind de eerstvolgende grotere sleutel”. Een gebalanceerde zoekboom of geordende database-index past beter bij bereikvragen. Voor vijf of tien regels kan een gewone lijst ook eenvoudiger zijn en minder geheugen innemen. Snel verwacht opzoeken is nuttig, maar niet gratis.

Botsingen zijn normaal

De array heeft een beperkt aantal buckets, terwijl er veel meer mogelijke sleutels zijn. Als negen jassen op acht planken moeten liggen, krijgt minstens één plank twee jassen. Geen enkele slimme hashfunctie kan die wiskundige grens verwijderen. Ze kan botsingen alleen zeldzaam maken en gelijkmatig verspreiden voor de sleutels die een toepassing werkelijk gebruikt.

Aparte ketens vormen één veelgebruikte oplossing. Iedere bucket heeft een kleine verzameling en botsende regels komen in die verzameling terecht. Verwijderen betekent dat de tabel een regel uit de juiste lijst haalt. Dit ontwerp is makkelijk uit te leggen en verdraagt meer regels dan buckets, maar de verwijzingen en losse geheugentoewijzingen vragen extra geheugen. Door die verwijzingen te volgen, benut het programma het nabijgelegen geheugen van de processor soms ook minder goed.

Een andere familie ontwerpen gebruikt open adressering. Alle regels blijven in de hoofdarray. Als op de eerste positie al een andere sleutel staat, controleert de tabel volgens een vaste reeks andere posities totdat ze de sleutel of een geschikte lege plek vindt. Regels bij elkaar houden kan het aantal geheugentoewijzingen verlagen en de toegang tot het geheugen verbeteren, maar verwijderen wordt lastiger. Een verwijderde positie heeft soms een speciaal teken nodig dat zegt: “Hier stond eerder een regel, dus zoek verder.” Anders kan een zoekopdracht te vroeg stoppen en een botsende sleutel verderop in de reeks missen.

Productiehashtabellen werken deze ideeën op verschillende manieren uit. CPython-dictionaries gebruiken open adressering en bewaren speciale tekens voor verwijderde posities. Java’s HashMap kan een bucket met veel botsingen veranderen van een gekoppelde lijst in een gebalanceerde boom. De keuzes volgen uit de manier waarop iedere programmeertaal haar regels opslaat en het gedrag dat haar ingebouwde woordenboektype belooft. Programmeertalen hoeven dus niet dezelfde botsingsstrategie te gebruiken.

Vrije ruimte en vergroten

Een tabel wordt trager als ze voller raakt. De beladingsgraad beschrijft hoe vol ze is. Deel het aantal regels door het aantal buckets en zes regels in acht buckets geven een beladingsgraad van 0,75. Een hoge beladingsgraad verspilt weinig arrayruimte, maar vergroot de kans op langere lijsten of zoekreeksen. Een lage beladingsgraad besteedt meer geheugen aan korte zoekopdrachten. Zodra de tabel haar gekozen grens overschrijdt, reserveert ze een grotere bucketarray en berekent ze voor iedere bestaande regel een nieuwe positie. De oude positie kopiëren is niet genoeg, omdat de arraygrootte onderdeel is van de restberekening. Hashcode 10 kiest bucket 2 in een array met acht buckets, want na deling door acht blijft rest 2 over. In een array met zestien buckets kiest dezelfde code bucket 10.

Tijdens het vergroten staan de oude en nieuwe array tijdelijk allebei in het geheugen. Het programma loopt door de bestaande regels, plaatst iedere verwijzing in de juiste nieuwe bucket en geeft de oude bucketarray daarna vrij. De sleutel-waardeparen zelf kunnen op hun plek blijven wanneer de implementatie alleen hun verwijzingen hoeft te verplaatsen. Andere indelingen kopiëren de regels naar nieuwe plekken. In beide gevallen verandert de indeling, terwijl de opgeslagen sleutels en waarden gelijk blijven. Eén invoeging kan daardoor duur zijn. De meeste invoegingen raken één korte bucket, maar de invoeging die de groei veroorzaakt kan iedere regel opnieuw verdelen. Dat dure moment komt maar af en toe voor. Als we het werk over een lange reeks invoegingen verdelen, blijven de verwachte kosten per invoeging constant. Dit heet geamortiseerde constante tijd. Sommige afzonderlijke bewerkingen kosten meer, terwijl de gemiddelde kosten over de hele reeks begrensd blijven. In het artikel over Big O-notatie lees je meer over dit soort analyse.

Een subtiele valkuil: een sleutel veranderen

De hash en gelijkheidsregels van een sleutel moeten stabiel blijven zolang de sleutel in de tabel staat. Neem een object met de velden stad: Utrecht en jaar: 2026. Stel dat de hashcode bucket 5 kiest, waar de tabel een verwijzing naar het object en de bijbehorende waarde bewaart. Code op een andere plek verandert de stad in hetzelfde object daarna in Rotterdam. Als de stad meetelt in de hashberekening, kan het veranderde object nu bucket 1 kiezen. De regel zelf is niet verplaatst en hangt nog steeds aan bucket 5. Een zoekopdracht hasht de nieuwe inhoud, doorzoekt bucket 1 en meldt dat de sleutel ontbreekt, terwijl ergens anders in de tabel nog een regel met een verwijzing naar dat object staat.

Daarom eist Python dat sleutels van een dictionary hashable zijn en mogen veranderlijke lijsten geen sleutel zijn. Zeggen dat sleutels altijd onveranderlijk moeten zijn, is net iets breder dan de echte regel. Een sleutel mag veranderende gegevens bevatten die de tabel negeert. Ieder deel waarmee de hashcode of gelijkheid wordt bepaald, moet wel gelijk blijven. Als die informatie moet veranderen, verwijder dan eerst de oude sleutel en voeg de veranderde sleutel opnieuw toe. De tabel kan haar dan in de juiste bucket plaatsen.

Slechtste gevallen en vijandige invoer

Een goede verspreiding houdt bucketlijsten bij normaal gebruik kort, maar garandeert dat niet. Als iedere sleutel in één bucket belandt, wordt een zoekopdracht een gewone doorloop van alle opgeslagen regels. Met een miljoen regels in die bucket is de garderobemedewerker terug bij af. Verwachte constante tijd is dan lineaire tijd geworden. Een zwakke hashfunctie kan dit per ongeluk veroorzaken. Een aanvaller kan ook doelbewust botsende sleutels kiezen en ze in een verzoek naar een server sturen. Als het verwerken van dat verzoek voor iedere toevoeging of zoekopdracht een lange doorloop veroorzaakt, kan het processorgebruik genoeg groeien om andere gebruikers geen dienst meer te verlenen. Zo’n aanval wordt vaak HashDoS genoemd.

Implementaties kunnen een willekeurige startwaarde voor hun hashfunctie gebruiken, zodat een aanvaller botsingen niet vooraf kan voorspellen. Andere mogelijkheden zijn een hashfunctie die zulke invoer weerstaat, een grens aan de beladingsgraad of een gebalanceerde boom voor een overvolle bucket. Sterkere bescherming maakt de hashberekening of de tabel zelf duurder. Rust geeft de standaardhashfunctie van HashMap bijvoorbeeld zo’n willekeurige startwaarde als onderdeel van de bescherming tegen HashDoS-aanvallen.

Ook de volgorde van buckets wordt makkelijk verkeerd begrepen. Hashing bewaart van zichzelf geen gesorteerde volgorde of invoegvolgorde. Python-dictionaries bewaren de invoegvolgorde wel, maar dat is een garantie van die implementatie en geen eigenschap van hashtabellen zelf. Bij het vergroten kan iedere bucketpositie veranderen. Gelijktijdige toegang is een afzonderlijk probleem. Een veranderlijke tabel is niet automatisch veilig wanneer meerdere threads er tegelijk naar schrijven. Een toepassing heeft dan een implementatie voor gelijktijdige toegang nodig of moet veranderingen zelf synchroniseren.

Samenvatting

Een hashtabel besteedt extra geheugen om niet ieder opgeslagen item te hoeven doorzoeken. Ze voert een sleutel door een herhaalbare hashfunctie, zet de hashcode om in een bucketpositie en vergelijkt de oorspronkelijke sleutels binnen die bucket. Botsingen zijn onvermijdelijk. Gelijkheidscontroles en een botsingsstrategie horen daarom bij het ontwerp en zijn geen reparaties achteraf. Vrije ruimte en een goede verspreiding houden de zoekopdracht bij normaal gebruik kort. Door de tabel te vergroten, ontstaat die vrije ruimte opnieuw wanneer de verzameling groeit.

Als er maar één idee blijft hangen, laat het dan dit zijn: een hash vertelt de tabel niet waar een item moet staan, maar waar ze moet beginnen met zoeken. Dankzij die kortere route kosten opzoeken, invoegen en verwijderen naar verwachting constante tijd. Een slechte verspreiding, veranderde sleutels, een te volle tabel of vijandige invoer kan dat voordeel wegnemen.

Meer lezen

• Big O-notatie uitgelegd
• Cryptografische hashfuncties uitgelegd
• Open Data Structures: Hash tables
• Python-documentatie: Hoe worden dictionaries in CPython geïmplementeerd?
• PostgreSQL-documentatie: Planner en optimizer
• Oracle-documentatie: Java HashMap