EasyVery High Frequency20 min
HashMap Fundamentals
Hash functions, collision resolution, and the frequency counting / grouping pattern.
HashMap = O(1) average insert/lookup. Trade O(n) space for O(1) time. The "frequency map" and "complement lookup" patterns solve hundreds of interview problems.
HashMap — O(1) Lookup
Operation Complexities
Operation
Time
Note
put(key, val)
O(1) avg
O(n) worst case with many hash collisions
get(key)
O(1) avg
Constant time lookup on average
containsKey(key)
O(1) avg
Backed by get()
remove(key)
O(1) avg
Unlinks from chain or tombstones slot
Iteration
O(n)
Visit all entries — no guaranteed order
Operations — Step by Step
Two Sum — Complement Lookup
O(n)One pass: for each x, look up (target-x) in the mapStep-by-step1 / 3
Scan input
Current lookup
Map starts empty, then stores keys for O(1) lookup.
Hash Map
empty
target=9. map={}
Empty map. Begin scanning.