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

Key
โ†’
Hash Function
โ†’
Index
โ†’
Value

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.

hash_demo.py Python

Visual: Keys hashing to bucket indices

"alice"
โ†’
hash()
โ†’
Bucket 3
"bob"
โ†’
hash()
โ†’
Bucket 7
"carol"
โ†’
hash()
โ†’
Bucket 3
COLLISION!

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:

dict_operations.py Python
Output
95 0 True ['alice', 'carol', 'dave'] [95, 92, 88] [('alice', 95), ('carol', 92), ('dave', 88)]
OperationSyntaxAverageWorst
Lookupd[key] / d.get(key)O(1)O(n)
Insertd[key] = valO(1)O(n)
Deletedel d[key]O(1)O(n)
Membershipkey in dO(1)O(n)
Iteratefor k in dO(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.

set_operations.py Python
Output
True {1, 2, 3, 4, 5, 6} {3, 4} {1, 2} {1, 2, 5, 6}

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.

๐Ÿ“Š
Interview pattern
Top K Frequent Elements โ€” O(n)

Given an integer array, return the k most frequent elements.

top_k_frequent.py Python
Output
[1, 2]

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.

๐ŸŽฏ
Classic interview problem
Two Sum โ€” from O(nยฒ) to O(n)

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).

two_sum.py Python
Output
[0, 1]

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.

group_anagrams.py Python
Output
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

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.

first_unique.py Python
Output
0 -1

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

๐Ÿงช
Interactive โ€” runs in your browser
Contains Duplicate

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

Hash Map Challenge: Longest Consecutive Sequence
The Problem

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?

Approach

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

Question 1 of 5
What is the average time complexity of looking up a key in a Python dict?
Question 2 of 5
In the Two Sum problem, what do we store in the hash map?
Question 3 of 5
What happens when two different keys hash to the same bucket index?
Question 4 of 5
Which Python data structure should you use when you only need to check if an element exists (no key-value pairs)?
Question 5 of 5
In the Group Anagrams problem, what do we use as the hash map key?
0
/5
Great work! You understand hash maps and sets.
Africa & India's Best AI Academy
๐Ÿค– AI-first ๐ŸŽ“ Placement Assistance

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 โ†’
Next lesson
Stacks & Queues โ†’
โ†’