Hash table (hash map)
Datastruktur som mappar nycklar till värden i O(1) amortiserad tid — basblocket bakom dict/HashMap/object i nästan alla språk.
Hash-funktion mappar nyckel → bucket-index. Kollisioner hanteras via chaining (länkad lista per bucket — Java HashMap default) eller open addressing (linear probing, quadratic probing — Python dict, Go map, Rust HashBrown). Resize när load factor överstiger ~0.75.
Worst-case O(n) vid dålig hash. HashDoS-attacker (2011) tvingade alla språk att använda seedade hash-funktioner (SipHash). Robin Hood hashing och hopscotch hashing är moderna varianter med bättre cache locality.