Hash Maps

O(1) lookups that power everything from databases to frequency counting

Say you want to remember every friend's favourite snack. You could write them all in a list. But then, to find Meera's snack, you would read down the list one by one until you reached her. With a thousand friends, that is a thousand things to check.
A hash map (in Python it is called a dict) does something cleverer. It keeps a wall of numbered lockers. A little machine turns a name into a locker number, and the same name always comes out as the same number. So it stores Meera's snack in her locker, and later walks *straight* to that same locker to get it back. It never checks the others.
That is why a dict feels instant, no matter how much is inside. Try it.

The little machine has a real name: a hash function. All it does is turn a key (like a name) into a number that says where to look. Because the same key always makes the same number, storing and finding both jump straight to the right spot.
In big-O terms, that straight jump is O(1): the time to find something does not grow as you add more. A plain list is O(n): the more you store, the longer the search. That one difference is why hash maps are everywhere, from the contacts on your phone to the biggest databases in the world.

The classic: two sum with a hash mappython

def two_sum(nums, target):
    """Find two indices that sum to target. O(n) time, O(n) space."""
    seen = {}  # value → index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:          # O(1) lookup
            return [seen[complement], i]
        seen[num] = i                   # Store for future lookups

    return []

print(two_sum([2, 7, 11, 15], 9))  # → [0, 1]

Nested loops: O(n²)⚠ Works but messy

# O(n²) brute force
def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Hash map: O(n)✓ Pythonic

# O(n) with hash map
def two_sum_fast(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        comp = target - num
        if comp in seen:
            return [seen[comp], i]
        seen[num] = i

💡

Trading O(n) space for O(n) time improvement, hash maps make this trade constantly

🤔Quick Check

What is the worst-case time complexity of a hash map lookup?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Group Anagrams

Group strings that are anagrams of each other.
Expected output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next