Hash table (hash map)
Data structure that maps keys to values in O(1) amortised time — the building block behind dict/HashMap/object in nearly every language.
A hash function maps key → bucket index. Collisions handled via chaining (a linked list per bucket — Java HashMap default) or open addressing (linear probing, quadratic probing — Python dict, Go map, Rust HashBrown). Resize when load factor exceeds ~0.75.
Worst-case O(n) with a bad hash. HashDoS attacks (2011) forced every language to use seeded hashes (SipHash). Robin Hood hashing and hopscotch hashing are modern variants with better cache locality.