What is a hash map
A hash map is a key-value store. You give it a key, it gives you a value โ in constant time. In Python, it's the built-in dict.
Why hash maps dominate interviews
Most brute-force solutions scan an array for every element, giving O(nยฒ). A hash map lets you store what you've seen and check it in O(1). That one trick solves dozens of interview problems: Two Sum, frequency counting, duplicate detection, grouping, caching.
Average complexity: O(1) lookup, O(1) insert, O(1) delete. No other data structure gives you all three.
How a hash map works
Under the hood, the hash function converts a key (like "alice") into an integer index. That index points directly to a slot in an internal array. No scanning, no searching โ just one jump.
How hashing works
A hash function takes any input and produces a fixed-size integer. Python uses hash() built-in. The hash map then computes hash(key) % table_size to find the bucket index.
Visual: Keys hashing to bucket indices
Collision handling: When two keys hash to the same bucket, Python uses open addressing (probing for the next empty slot). Other languages use chaining (a linked list at each bucket). Both maintain O(1) average time as long as the table isn't too full.
Python dict operations
Python's dict is the hash map you'll use in every interview. Here are the essential operations:
| Operation | Syntax | Average | Worst |
|---|---|---|---|
| Lookup | d[key] / d.get(key) | O(1) | O(n) |
| Insert | d[key] = val | O(1) | O(n) |
| Delete | del d[key] | O(1) | O(n) |
| Membership | key in d | O(1) | O(n) |
| Iterate | for k in d | O(n) | O(n) |
Interview tip: The "worst case O(n)" happens only with pathological hash collisions. In practice (and in interviews), always say O(1) average. Interviewers expect that.
Sets
A set is a hash map without values โ just keys. Unordered, unique elements, O(1) lookup. Use sets when you only care about membership, not key-value pairs.
When to use set vs dict: Need to check "have I seen this before?" โ use a set. Need to store extra info with each key (count, index, value) โ use a dict.
Pattern: Frequency counting
The most common hash map pattern in interviews. Count how many times each element appears. Python's Counter from collections does it in one line.
Given an integer array, return the k most frequent elements.
Why O(n)? Counter(nums) scans the array once โ O(n). most_common(k) uses a heap internally โ O(n log k). For small k, this is effectively linear. The brute-force approach (sorting) is O(n log n).
Problem: Two Sum (optimal with hash map)
The single most famous interview question. Given an array and a target, find two numbers that add up to the target. Return their indices.
Brute force: Check every pair โ O(nยฒ). Hash map: For each number, check if its complement exists in what you've already seen โ O(n).
Walk through it: We iterate once. At index 0, we see 2 and store {2: 0}. At index 1, we see 7 and check: is 9 - 7 = 2 in seen? Yes! Return [0, 1]. One pass, O(n) time, O(n) space.
Problem: Group Anagrams
Given a list of strings, group the anagrams together. Two strings are anagrams if they contain the same characters in any order.
Key insight: Anagrams have the same sorted characters. sorted("eat") and sorted("tea") both give ['a', 'e', 't']. We use that sorted tuple as a hash map key. defaultdict(list) automatically creates an empty list for new keys. Time: O(n * k log k) where k is max string length.
Problem: First non-repeating character
Given a string, find the first character that doesn't repeat. Return its index, or -1 if all characters repeat.
Two-pass pattern: First pass counts frequencies (O(n)). Second pass finds the first character with count 1 (O(n)). Total: O(n) time, O(1) space (at most 26 lowercase letters). This is a common pattern โ build a frequency map, then query it.
Try it yourself
Given an array of integers, return True if any value appears at least twice. Return False if every element is distinct. Use a set for O(n) time.
Challenge
Given an unsorted array of integers, find the length of the longest consecutive sequence. For example, given [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], so return 4.
Your solution must run in O(n) time. Sorting would be O(n log n) โ can you do better with a set?
1. Put all numbers in a set for O(1) lookup.
2. For each number, check if it's the start of a sequence (i.e., num - 1 is NOT in the set).
3. If it's a start, count how far the sequence goes: num + 1, num + 2, etc.
4. Track the maximum length.
Hint: The key insight is step 2 โ only start counting from sequence beginnings. Without that check, you'd recount subsequences and get O(nยฒ). With it, each number is visited at most twice, giving O(n).
def longest_consecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set:
length = 1
while num + length in num_set:
length += 1
longest = max(longest, length)
return longest
Test your knowledge
You've mastered hash maps.
Now ace the full interview.
Join the Best AI Programs โ three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses โ