Hash Map
Turns a key into a bucket index via a hash function, giving average O(1) lookup, insert, and delete. Collisions — two keys landing in one bucket — are handled by chaining.
A hash map is an array of buckets plus a hash function that maps any key to a bucket index (hash(key) mod bucket-count). A good hash function scatters keys uniformly, so each bucket holds at most a couple of entries and every operation touches only that chain.
Collisions are unavoidable (pigeonhole principle) and handled two main ways: separate chaining stores a small list per bucket; open addressing probes for the next free slot. Either way, performance depends on the load factor — entries divided by buckets. Past ~0.75 the table typically resizes: allocate double the buckets and rehash every key, an O(n) pause paid rarely enough that operations stay amortised O(1).
The worst case is an adversarial or terrible hash function driving every key into one bucket — O(n) per lookup. That is why languages randomise string hashing and why keys must be immutable: mutate a stored key and it silently ends up "filed under the wrong letter", unreachable.
Operations
| Operation | Complexity |
|---|---|
| get / put / remove | O(1) average |
| worst case (bad hash) | O(n) |
| resize + rehash | O(n), amortised |
| iterate | O(n + buckets) |
Where it's used
Anything keyed: dictionaries, caches, indexes, de-duplication, counting frequencies. The most-used data structure in practice.