Back to Topics
Hash Map
A hash map (dictionary) maps keys to values using a hash function to compute an index into a backing array. It provides average-case O(1) for insert, delete, and lookup — making it the most versatile tool for trading space for speed. Hash sets offer the same performance for membership testing.
Key Ideas
- Hash function converts a key to an index; a good hash minimises collisions
- Collisions handled by chaining (linked list per bucket) or open addressing
- Average O(1) insert/lookup; worst-case O(n) with many collisions (rare in practice)
- Use a hash map whenever you need fast lookup by an arbitrary key
- Two-sum pattern: store complement → index while iterating once
- Grouping pattern: map a canonical key (sorted string, tuple) → list of items
Complexity
| Operation | Time | Space |
|---|---|---|
| Insert | O(1) avg | O(n) |
| Delete | O(1) avg | O(1) |
| Lookup | O(1) avg | O(1) |
| Iteration | O(n) | O(1) |
Common Patterns
Two Sum / ComplementStore seen values and check if the complement of the current value exists.
Grouping / BucketingMap a canonical form (e.g. sorted word) to a bucket of equivalent items.
Frequency CountCount occurrences of elements for majority element, top-K, or anagram problems.
MemoisationCache computed results of sub-problems to avoid redundant work (dynamic programming).
Code Example
Two Sum — O(n) with complement mappython
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {} # value → index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []💡
If your brute-force is O(n²) due to searching, ask: can a hash map make the inner lookup O(1)?