Hash maps & hash sets
In one line
A hash map turns a key into an array index with a hash function, giving O(1) average insert, delete and lookup; a hash set is the same structure storing keys only.
What it is
A hash map (dict in Python, HashMap in Java, unordered_map in C++, object or Map in JavaScript) stores key-value pairs. A hash set (set, HashSet) stores just keys and answers 'have I seen this?'.
Underneath is an array of buckets. A hash function turns each key into a large integer, and that integer modulo the number of buckets picks the bucket. As long as keys spread evenly and the table is not too full, each operation looks at only a few slots, so insert, delete and lookup take O(1) on average. In the rare worst case where many keys collide, it degrades to O(n).
Why interviewers ask
The hash map is the single most useful tool in coding interviews: it turns many O(n^2) brute-force solutions into O(n) by trading memory for speed. Interviewers expect you to reach for it naturally, to know that O(1) is an average and not a guarantee, and to explain collisions, load factor and why keys must be immutable.
How it works
- 1Hash: compute hash(key), a fixed-size integer. Equal keys must always give equal hashes.
- 2Pick a bucket: index = hash mod capacity (or a bit mask when capacity is a power of two).
- 3Handle collisions: two keys can land in the same bucket. Separate chaining keeps a small list per bucket (Java HashMap). Open addressing probes other slots in the array until it finds a free one (Python dict).
- 4Lookup: hash the key, go to its bucket, and compare stored keys with == until a match is found or the bucket is exhausted.
- 5Resize: the load factor is entries divided by capacity. When it passes a threshold (0.75 in Java HashMap, about 2/3 in CPython dict), the table allocates a bigger array and re-inserts every entry. Like a dynamic array, this O(n) step is rare, so operations stay amortized O(1).
- 6A hash set is the same machine with no values; membership testing ('x in s') is O(1) on average, compared to O(n) for a list.
Worked example · Two Sum with a hash map: nums = [3, 2, 4], target = 6
- Goal: find two indices whose values add to 6. Brute force checks every pair, O(n^2). Instead, for each number ask 'have I already seen the partner I need?'.
- i = 0, x = 3. Need 6 - 3 = 3. seen is empty, so no. Store 3 -> 0. seen = {3: 0}.
- i = 1, x = 2. Need 4. Not in seen. Store 2 -> 1. seen = {3: 0, 2: 1}.
- i = 2, x = 4. Need 2. seen has 2 at index 1. Return [1, 2] because 2 + 4 = 6.
- Note the order: we check before storing. At i = 0 we needed 3 and 3 itself was not yet stored, so we never pair an element with itself.
- One pass and one O(1) lookup per element: O(n) time, O(n) extra space.
Picture it
A hash map is a coat check. You hand over your coat (value) and get a ticket number computed from your name (hash). To get the coat back, the attendant goes straight to that hook instead of searching every hook. If two people get the same hook, the coats hang together and the attendant checks the name tags.
Reference code
def two_sum(nums, target):
seen = {} # value -> index where we saw it
for i, x in enumerate(nums):
need = target - x
if need in seen: # O(1) average lookup
return [seen[need], i]
seen[x] = i # store AFTER checking
return []
def contains_duplicate(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
two_sum stores each value's index after checking whether its complement was already seen, so one pass finds the pair in O(n) time and O(n) space. contains_duplicate uses a set for O(1) average membership tests, which turns the O(n^2) pairwise check into O(n).
Key patterns
Seen-before set
When: Detect duplicates, check membership, or find the first repeat
How: Walk the input, check 'x in seen' then add x. O(n) instead of O(n^2) pairwise comparison.
Complement lookup (Two Sum)
When: Find a pair that satisfies a relation such as a + b = target
How: For each x, look up target - x in a map of earlier values to indices, then store x.
Group by a computed key
When: Group items that share a property (anagrams, same domain, same day)
How: Compute a canonical key (sorted letters, tuple of counts) and append the item to map[key].
Index map
When: You need the position of a value quickly
How: Build value -> index once, then answer each 'where is x?' in O(1).
Cache results (memoization)
When: The same expensive call repeats with the same arguments
How: Store argument -> result in a map and return the stored result on a repeat.
Real-world use
Python itself
Python uses dicts for module namespaces, object attributes (__dict__) and keyword arguments, so variable and attribute lookup is a hash lookup. CPython's dict uses open addressing and keeps insertion order since Python 3.7.
Redis and Memcached
Both are giant in-memory hash tables mapping string keys to values. Redis grows its main table with incremental rehashing, moving a few buckets on each operation so a resize never freezes the server.
Database hash joins
PostgreSQL, MySQL 8 and Spark often join two tables by building a hash table on the smaller one's join key, then streaming the larger table and probing it, which is O(n + m) instead of comparing every pair of rows.
Java HashMap under attack
Attackers once sent many keys with the same hash to web servers to force O(n) buckets (hash-flooding denial of service). Java 8 responded by turning long buckets into balanced trees, and Python randomises string hashes per process for the same reason.
In a project
An e-commerce checkout must reject duplicate order submissions (users double-clicking 'Pay') and look up products by SKU for 50,000 requests per second.
- Keep a hash set of idempotency keys seen in the last 24 hours; if an incoming key is already in the set, return the original result instead of charging again.
- Load the product catalog into a hash map from SKU to product record at startup, so each lookup is O(1) instead of scanning a list or hitting the database.
- Use immutable keys (SKU strings, idempotency key strings), never mutable objects, so hashes never change after insertion.
- Size the map up front for the known catalog size to avoid resize pauses, and move the idempotency set into Redis with a TTL when running several servers.
Impact: Duplicate charges drop to zero, catalog lookups take microseconds instead of a database round trip, and the service handles peak traffic on far fewer machines.
Trade-offs
Use it when
- You need fast lookup, insert or delete by key
- You are counting, grouping or detecting duplicates
- You can trade O(n) extra memory for a big speedup
Avoid it when
- You need keys in sorted order or range queries (smallest key above x): use a sorted structure or balanced tree
- Keys are small dense integers: a plain array indexed by key is faster and smaller
- Memory is very tight; hash tables keep spare capacity and per-entry overhead
Cost: Insert, delete, lookup: O(1) average, O(n) worst case when many keys collide. Resize O(n) but amortized O(1). Space O(n).
Common mistakes
- Saying lookup is always O(1): it is O(1) on average with a good hash function; the worst case is O(n).
- Using mutable objects such as lists as keys. Python refuses; in Java, mutating a key after insertion makes the entry unfindable. Convert to a tuple or string.
- In Two Sum, storing the value before checking, which can pair an element with itself.
- Assuming iteration order is sorted. Python dicts keep insertion order, Java HashMap has no defined order; neither sorts.
- Forgetting the O(n) extra space when stating the complexity of a hash-based solution.
Interview questions
Quick revision
- Insert, delete, lookup: O(1) average, O(n) worst case.
- bucket = hash(key) mod capacity; equal keys must have equal hashes.
- Collisions: separate chaining (Java) or open addressing (Python).
- Resize when load factor passes a threshold (Java 0.75); amortized O(1).
- Keys must be immutable: tuples and strings yes, lists no.
- Set = map without values; 'x in set' is O(1) average vs O(n) in a list.
- Two Sum pattern: check target - x first, then store x.
- Hash maps are unordered for sorting purposes; use a sorted structure for range queries.
Check yourself
1. What is the worst-case time for a lookup in a hash map with n entries?
2. Which Python value can be used as a dict key?
3. Why does a hash table resize when its load factor gets too high?
4. In the hash-map Two Sum, why do we check for target - x before storing x?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.