Hash maps

A hash map (hash table, dictionary, Object in JS, dict in Python, Map in most languages) stores key→value pairs with average O(1) insert, lookup, and delete. The trick: run the key through a hash function to get an index into an underlying array, and store the pair at that bucket. Collisions — two keys hashing to the same bucket — are handled with chaining (a list per bucket) or open addressing (probe for the next empty slot). Two things to actually know about them in practice: worst-case performance degrades to O(n) if the hash function is bad or an adversary picks collision-inducing keys (real DoS vector — most languages randomise the hash seed per-process to defend against this); and hash maps don't preserve insertion order by default, though modern JS and Python hash maps do as a convenience. Used everywhere — caches (Redis at its core is a big hash map), database indexes, compilers' symbol tables, deduplication via sets.