Hashtabel (hashmap)
Datastructuur die sleutels aan waarden koppelt in geamortiseerd O(1): de bouwsteen achter dict, HashMap en object in vrijwel elke taal.
Een hashfunctie zet de sleutel om in een bucketindex. Botsingen worden opgelost met chaining (een gelinkte lijst per bucket, de standaard van Java HashMap) of open addressing (lineair of kwadratisch zoeken: Python dict, Go map, Rust HashBrown). Bij een bezettingsgraad boven ongeveer 0,75 wordt de tabel vergroot.
In het slechtste geval O(n) bij een slechte hash. HashDoS-aanvallen (2011) dwongen elke taal tot geseede hashes (SipHash). Robin Hood-hashing en hopscotch-hashing zijn moderne varianten met betere cachelokaliteit.