Data Structure

Hash Maps

A hash map is like having a super-powered address book. Instead of flipping through pages to find someone's number, you instantly know exactly where to look. That's the magic of O(1) lookup.

The Core Idea

A hash map stores key-value pairs. You give it a key (like a name), and it gives you back the value (like a phone number). The beautiful part? It does this in constant time, no matter how many items you have.

Under the hood, it uses a hash function to convert your key into an array index. Think of it as a translator that turns "alice" into "go to slot 42."

The Key Insight

When you need to check "have I seen this before?" or "what's the value associated with X?" - that's your cue to reach for a hash map.

Time Complexity

Operation	Average	Worst
Lookup	`O(1)`	`O(n)`
Insert	`O(1)`	`O(n)`
Delete	`O(1)`	`O(n)`

The worst case happens when there are lots of hash collisions (multiple keys mapping to the same slot). In practice, with a good hash function, you almost always get O(1).

The Classic Pattern

Here's the pattern you'll use again and again. It's so common it should be muscle memory:

# Build a map while iterating
seen = {}
for item in items:
    if item in seen:
        # Found it! Do something
        return seen[item]
    seen[item] = some_value

Real Example: Two Sum

The famous Two Sum problem is the perfect showcase. Given an array of numbers and a target, find two numbers that add up to the target.

The brute force approach checks every pair - that's O(n²). But with a hash map, we can do it in one pass:

def twoSum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

For each number, we ask: "Have I seen its complement?" The hash map answers instantly.

When to Use a Hash Map

Counting frequencies - How many times does each element appear?
Finding pairs - Two Sum, finding complements
Grouping elements - Group anagrams, categorize items
Caching results - Memoization in dynamic programming
Quick lookups - Any time you need O(1) access by key

Pro Tip

In Python, use defaultdict or Counter from the collections module. They handle missing keys gracefully and save you from writing boilerplate.

Common Pitfalls

Mutable keys - In Python, you can't use lists as keys (use tuples instead)
Forgetting to update - Make sure you're storing the right value at the right time
Overcomplicating - Sometimes a simple array works better (like counting characters a-z)

Hash Map vs Hash Set

A hash set is just a hash map without values. Use a set when you only care about "is this element present?" and don't need to store additional data.

Hash Maps

The Core Idea

Time Complexity

The Classic Pattern

Real Example: Two Sum

When to Use a Hash Map

Common Pitfalls

Hash Map vs Hash Set

Practice Makes Perfect