Dict & Set

The last lesson ended on a slightly unusual note for Python: no built-in balanced BST, giving up O(log n) sorted-order guarantees unless you reach for a third-party package. Hashing gives up ordering entirely in exchange for something better for pure key lookups — O(1) on average. This lesson covers how hashing works, what's actually happening inside Python's dict, and a classic interview problem (two-sum) that hashing solves far better than brute force.

The Hashing Concept

A hash function takes a key and produces an integer (the hash code), which is then reduced to a slot index within a fixed-size internal array — conceptually index = hash(key) % table_size. To look up a key, you don't scan anything: you compute its hash, jump straight to that slot, and (ideally) find your value right there.

key "apple"  -> hash() -> 93029210 -> % 8 slots -> slot 2
key "banana" -> hash() -> 93020956 -> % 8 slots -> slot 4
key "cherry" -> hash() -> 93006589 -> % 8 slots -> slot 5

Every Python object has a __hash__ method (built-in types like str, int, and tuple already implement it sensibly). This is also why dict keys must be hashable — a plain list can't be a dict key because lists are mutable and don't define __hash__, but a tuple of hashable items can be.

Python's Dict Internals: Open Addressing, Not Chaining

Here's a genuine implementation difference worth knowing: Java's HashMap handles a collision (two keys hashing to the same slot) by storing a small linked list (or a tree, once a bucket gets large) at that bucket. CPython's dict uses open addressing instead — there is no list per slot. When a computed slot is already occupied by a different key, the dict probes a different slot (following a pseudo-random but deterministic probing sequence derived from the hash) until it finds an empty one, and stores the entry there instead.

slot 4: "banana" -> 3                (original owner of slot 4)
slot 4 is taken -> "grape" wants slot 4 too -> probe to slot 6 instead
slot 6: "grape"  -> 7                (probed here after a collision)

Lookup follows the exact same probing sequence: compute the hash, check that slot, and if the key there doesn't match, keep probing the same sequence until either the key is found or an empty slot is hit (meaning "not present"). The table itself resizes (grows and rehashes every entry) once it gets too full, keeping the average probe sequence short.

prices = {}
prices["apple"] = 5
prices["banana"] = 3
prices["grape"] = 7   # might probe past banana's slot on a collision

# dict.get() hashes the key, jumps to its slot, and follows the
# probe sequence only as far as needed to find a match.
print(prices.get("grape"))  # 7

Time complexity: O(1) average for get/set — a good hash spreads keys evenly so the average probe chain stays very short. Worst case is O(n) if many keys collide into a small run of slots (rare with Python's hash spreading, but possible with adversarial input or a poor custom __hash__). Space complexity: O(n) to store n entries plus the underlying slot table, which is kept sparser than full to keep probing cheap.

Set: A Dict With Only Keys

A set is implemented the same way as a dict — same hash table, same open-addressing slots — except each entry only stores a key, with no value attached. That's why a set gives you the exact same O(1)-average add/contains/remove behavior as a dict's key operations, just without anything to retrieve.

seen = set()
seen.add("apple")
seen.add("banana")

print("apple" in seen)   # True -- one hash lookup, no scanning
print("cherry" in seen)  # False

Time complexity: O(1) average for add/contains (the in operator)/remove — identical reasoning to dict, since a set's membership test is just a dict-style lookup with no value. Space complexity: O(n) for n stored elements.

Worked Problem: Two-Sum

Given a list of integers and a target, find the indices of two numbers that add up to the target. The brute-force approach checks every pair:

# Brute force: check every pair
def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    raise ValueError("No solution")

Time complexity: O(n²) — every element is compared against every other element. Space complexity: O(1) — no extra data structure beyond the result list.

A dict gets this down to a single pass. For each number, first check whether its complement (target - num) was already seen; if not, record the current number and its index for future lookups:

# One pass with a dict: value -> index
def two_sum(nums, target):
    seen_at = {}

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen_at:
            return [seen_at[complement], i]
        seen_at[num] = i  # remember this value for later lookups

    raise ValueError("No solution")

# nums = [2, 7, 11, 15], target = 9
# i=0: complement=7, not seen yet -> remember 2 at index 0
# i=1: complement=2, seen at index 0 -> return [0, 1]

Time complexity: O(n) — a single pass through the list, with each dict membership check/lookup/insert being O(1) average. Space complexity: O(n) — in the worst case (solution found at the last element) the dict holds almost every value seen so far.