Lesson 3 of 9

Hash Maps & Sets

A lets you look up a value by its key in O(1) time. You'll learn how it works and how it often turns slow nested- code into a single pass.

A hash map stores key–value pairs and finds any value by key in constant time. The trick: a hash converts the key into a number, and that number decides which slot of an internal holds the value. Lookup doesn't search — it recomputes the hash and jumps straight to the slot, the same way array indexing jumps. A is a hash map that only keeps keys; 'have I seen this before?' in O(1).


ages = {'ada': 36, 'linus': 55}

ages['ada']              # O(1) lookup
ages['grace'] = 85       # O(1) insert
'linus' in ages          # O(1) membership test
del ages['linus']        # O(1) delete

# Compare with a list of pairs — every operation is O(n) scanning.

# Common use 1: counting
def count_words(text):
    counts = {}
    for word in text.split():
        counts[word] = counts.get(word, 0) + 1
    return counts

# Common use 2: replacing nested loops.
# "Find two numbers that sum to target" — the classic.

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

def two_sum_fast(nums, target):      # O(n)
    seen = {}                        # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:       # O(1) instead of inner loop
            return (seen[target - x], i)
        seen[x] = i

Why does it work? The hash function keys evenly across slots. Occasionally two keys land in the same slot — a collision — and the map handles it by chaining a small in that slot or probing nearby ones. With a good hash function collisions stay rare, so lookups average O(1). This is also why keys must be (hashable): if a key could change after insertion, its hash would change, and the map would look in the wrong slot forever.


# Sets: hash maps without values. Perfect for membership + dedup.
visited = set()
visited.add('/home')
'/home' in visited        # O(1)

unique = set([3, 1, 3, 2, 1])     # {1, 2, 3} — dedup in O(n)

# Set algebra — each O(len) not O(len^2):
admins = {'ada', 'grace'}
online = {'grace', 'linus'}
admins & online     # {'grace'}          intersection
admins | online     # all three          union
admins - online     # {'ada'}            difference

Common question

Can a hash map find a key without looking at the other keys?

A hash map stores entries in an array of buckets and uses a hash of the key to pick the bucket. Because the position is calculated rather than searched for, inserting, looking up and deleting take about the same time whether the map holds ten items or ten million. Collisions, where two keys land in one bucket, are handled by probing or chaining, and the table grows when it fills up.

In practice: keys must be immutable and must hash consistently with how they compare for equality; order is not part of the structure, though Python's dict keeps insertion order; and whenever you catch yourself scanning a list for a matching item, a map can probably remove the loop entirely.

Source: The Python wiki's TimeComplexity page lists dict lookup as O(1) on average, whether the dictionary holds ten entries or ten million.

Common mix-ups

Each of these sounds reasonable. Think about why it is wrong, then open the explanation.

Any lookup has to compare against the stored keys, so a map can't be faster than a scan.
A hash map guarantees constant-time lookup.
Any object can be used as a key.

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.