Hash Maps (Dictionaries)
DSA · Hashing
Theory
A hash map stores key-value pairs and finds the value for a key in average O(1) time. It works by passing the key through a hash function that converts it to an index in an internal array of buckets. To insert, Python hashes the key and stores the pair in that bucket; to look up, it hashes the key again and goes straight to the bucket, instead of scanning every element. Python's dict is a highly optimised hash map that also keeps insertion order. Keys must be hashable (immutable types like str, int, tuple). Hash maps are the single most useful structure in coding interviews: counting frequencies, grouping items, caching results and the famous Two Sum problem all rely on them.
Why we use it
They turn many O(n^2) "search inside a loop" solutions into O(n) by remembering what you have already seen. Lookups, inserts and deletes are all O(1) on average.
When to use it
Use a hash map when you need to look something up by a key, count occurrences, group related items or memoise results. Use a sorted structure instead when you need keys in order or range queries.
How it works
- For each item
- Key already in map? Yes: Update value (e.g. count + 1). No: Insert key with initial value.
- Continue with next item
- Use map for O(1) lookups, counts and grouping
Syntax
d[key] = value insert/update O(1) avg
d.get(key, default) lookup O(1) avg
key in d membership O(1) avg
del d[key] delete O(1) avg
Worst case (many collisions) O(n)Example
from collections import Counter, defaultdict
# 1. Frequency count
words = "to be or not to be".split()
freq = {}
for w in words:
freq[w] = freq.get(w, 0) + 1
print("Counts:", freq)
print("Counter:", Counter(words).most_common(2))
# 2. Grouping
employees = [("Asha", "Eng"), ("Ravi", "Sales"), ("Meera", "Eng")]
by_dept = defaultdict(list)
for name, dept in employees:
by_dept[dept].append(name)
print("Grouped:", dict(by_dept))
# 3. Two Sum in O(n)
def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
print("Two Sum:", two_sum([2, 7, 11, 15], 9))Key points
- Average O(1) insert, lookup and delete
- Keys must be immutable (hashable)
- Counter and defaultdict cover most counting and grouping tasks
- The "seen" dictionary pattern solves Two Sum and many variants