DSData Structures & Algorithms · Lesson 3 of 9

Hash Maps & Sets

The hash map is the most useful data structure in programming: look anything up by key in O(1). Python's dict, JavaScript's object and Map, Java's HashMap — same idea everywhere, and the #1 tool for making slow code fast.

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

Python

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.

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

# Killer use case 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 spreads keys evenly across slots. Occasionally two keys land in the same slot — a collision — and the map handles it by chaining a small list 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 immutable (hashable): if a key could change after insertion, its hash would change, and the map would look in the wrong slot forever.

Python

# 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
✦ Tip
Rule of thumb for interviews and real code alike: if your solution is O(n²) because of a lookup inside a loop, a hash map or set almost always makes it O(n). It trades memory for speed — nearly always a great trade.