Hash maps and sets

Use a hash map to find a job by ID without scanning every job. Use a hash set when you only need membership.

Follow a key to its bucket

Suppose integer keys choose bucket key modulo 4. Insert 6, then 10, then 3:

bucket 0: []
bucket 1: []
bucket 2: [(6, "A"), (10, "B")]
bucket 3: [(3, "C")]

lookup 10 -> bucket 2 -> compare 6 -> compare 10 -> "B"
delete 6  -> bucket 2 becomes [(10, "B")]

A hash function turns a key into an integer. The table uses that integer to choose where to search. Different keys can collide: 6 and 10 share a bucket here. Equal hashes do not prove equal keys, so lookup must also check equality.

This representation uses separate chaining: each bucket holds a collection of entries. Open addressing is another representation. It keeps entries in table slots and probes more slots after a collision.

Preserve the key invariant

Equal keys must produce equal hashes. Each key appears at most once in a map. Inserting an equal key replaces its value; a set keeps only the key.

A stored key's hash and equality behavior must stay stable. Mutating a key so it belongs in another bucket can make an existing entry unreachable.

Deletion must preserve other searches. Chaining removes one bucket entry. Open addressing often needs a deleted marker or a repair of nearby entries. Clearing a slot as though it had never been occupied can stop a search too early.

Understand the expected cost

The load factor is entries divided by buckets. With well-distributed hashes and controlled load, lookup, insertion, and deletion take expected O(1) time. A resize may take O(n), so insertion is usually described as expected amortized O(1).

If every key collides, a simple chained table can take O(n) per operation. Hashing a key of length L can itself take O(L). Memory is O(n + b) for n entries and b buckets; growing b with n gives O(n).

Hashing does not provide sorted order, predecessor queries, or efficient key ranges. An implementation can separately preserve insertion order. Python's dict does; its set does not promise insertion order. Reading a map entry does not imply moving it to the end.

Choose a balanced search tree for sorted ranges and worst-case logarithmic operations. Choose a sorted array when updates are rare.

Predict and modify

1. Which bucket receives key 14? Which stored keys must lookup compare?
2. If bucket count doubles, can you copy each old bucket unchanged?
3. Add resizing when the load factor exceeds 1.

class BucketMap:
    def __init__(self):
        self.buckets = [[] for _ in range(4)]

    def put(self, key, value):
        bucket = self.buckets[key % len(self.buckets)]
        for index, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[index] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        for stored_key, value in self.buckets[key % len(self.buckets)]:
            if stored_key == key:
                return value
        raise KeyError(key)

    def delete(self, key):
        bucket = self.buckets[key % len(self.buckets)]
        for index, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                del bucket[index]
                return
        raise KeyError(key)


jobs = BucketMap()
jobs.put(6, "A")
jobs.put(10, "B")
jobs.put(3, "C")
assert jobs.get(10) == "B"
jobs.put(10, "updated")
assert jobs.get(10) == "updated"
jobs.delete(6)
assert jobs.get(10) == "updated"
try:
    jobs.get(6)
except KeyError:
    pass
else:
    raise AssertionError("deleted key was found")

Apply membership lookup in Two Sum.

Next: Trees and ordered maps.