{ } AssociativeCore interactive
Hash Table
Key → bucket via a hash function. O(1) average.
hash_table
load factor 0.50
0
8
→16
1
empty
2
42
3
empty
4
empty
5
empty
6
empty
7
23
hash(key) = key % 8 picks the bucket. Collisions chain.
How it works
A hash table maps keys to array slots through a hash function. Average-case insert, lookup, and delete are O(1). Collisions — two keys landing in the same bucket — are resolved by chaining or open addressing, and a good load factor keeps things fast.
Mental models
- hash(key) % capacity picks the bucket — collisions are inevitable.
- Chaining stores a list per bucket; open addressing probes for a free slot.
- Resizing when the load factor passes ~0.75 keeps lookups near O(1).
Common pitfalls
- Worst case is O(n) when every key collides into one bucket.
- Iteration order is not insertion order (unless the map guarantees it).
Complexity
- Insert
- O(1) avgO(n) worst case
- Lookup
- O(1) avg
- Delete
- O(1) avg
- Space
- O(n)
Reach for it when
- Caches & memoization
- De-duplication / sets
- Counting frequencies