Time and space complexity

Why is a hash map usually fast?

Let n be the number of stored key–value pairs and m the number of buckets. A chained lookup calculates one bucket and scans only that bucket’s pairs. If the keys are spread evenly, the average bucket contains about n / m pairs. Keeping m proportional to n keeps that average small as the table grows.

This explains expected O(1) lookup. It does not mean zero comparisons or exactly one instruction. It means the expected number of operations does not grow in proportion to all n entries. The bound assumes useful hash distribution and bounded-cost key operations.

Worst case means an input arrangement that causes the most work. If all n keys collide in one bucket, lookup may inspect every key in that bucket, taking O(n). Our fixed eight-bucket teaching table does not automatically maintain the growth policy: as it fills, its average chains can grow. Production dictionaries handle growth internally.

Work through an example

In the eight-bucket example, keys 10 and 18 share bucket 2. Finding 18 needs two key comparisons. Adding a well-distributed key to a different bucket does not add another comparison to this lookup.

Now insert keys 2, 10, 18, 26, and 34 using key % 8. Every key chooses bucket 2. Finding 34 in insertion order needs five comparisons. With n such colliding keys, it can need n comparisons. This is the concrete reason for the O(n) worst case.

To compare whole algorithms, repeatedly scanning all earlier values for Two Sum can check roughly n(n − 1) / 2 pairs: O(n²) time and O(1) auxiliary space. A map remembers earlier values and uses expected O(n) total time with O(n) space. You spend memory to avoid repeated searches.

Time and space complexity

Expected lookup, membership, update, and deletion: O(1), given well-spread hashes, controlled load, and bounded-cost keys. Expected amortized insertion: O(1) with a suitable geometric growth policy. A single growth-triggering insertion can take O(n).

Worst-case lookup, update, insertion, or deletion in the simple chained table: O(n) when collisions force a long scan, assuming bounded key costs and capacity proportional to n. The guarantees of specialized implementations can differ. Hashing a new string of length k may add O(k) work.

Space for the chained table: O(n + m). With bucket capacity proportional to the number of entries, this is O(n). One lookup uses O(1) auxiliary space. Resizing can require O(n) temporary space under that capacity assumption. Iterate all stored pairs when you need all values: that is linear work, not a constant-time lookup.

Why it works

Analyze the complete algorithm, not just one dictionary expression. Include the number of table operations, key construction and comparison costs, occasional resizing, and all stored state. An expected bound describes a distribution-dependent expectation; an amortized bound spreads occasional large costs across a sequence of operations.

Common mistakes

• Always qualify the expected O(1) bound; it is not an unconditional worst-case promise.
• O(1) extra space for one lookup does not mean the whole table occupies O(1) space.
• Python dictionary insertion order is not sorted-key order. Exact lookup does not automatically provide efficient predecessor or range queries.

Chapter lab · Python implementation

The code below builds the same teaching table shown above: eight buckets, integer keys, and a list of pairs in each bucket. make_table creates the buckets; put inserts or updates; get finds a value; remove deletes one pair; resize moves pairs into a new table. This is separate chaining, one possible hash-table implementation. Its simple key % capacity rule makes collisions visible; Python’s real dict uses its own hashing and storage rules. This small table does not resize automatically. Run the assertions to see that two colliding keys stay separate and that updates do not create duplicates. The final two functions apply Python dictionaries to Two Sum and frequency counting.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def make_table(capacity=8):
    if capacity <= 0:
        raise ValueError("capacity must be positive")
    return [[] for _ in range(capacity)]


def put(table, key, value):
    bucket = table[key % len(table)]
    for position, (stored_key, stored_value) in enumerate(bucket):
        if stored_key == key:
            bucket[position] = (key, value)  # Update this key.
            return
    bucket.append((key, value))  # A new key, even if its bucket is used.


def get(table, key):
    bucket = table[key % len(table)]
    for stored_key, value in bucket:
        if stored_key == key:
            return value
    raise KeyError(key)  # No matching key in this bucket.


def remove(table, key):
    bucket = table[key % len(table)]
    for position, (stored_key, value) in enumerate(bucket):
        if stored_key == key:
            bucket.pop(position)
            return value
    raise KeyError(key)


def resize(table, capacity):
    new_table = make_table(capacity)
    for bucket in table:
        for key, value in bucket:
            # Existing keys are unique, so no duplicate-key scan is needed.
            new_table[key % capacity].append((key, value))
    return new_table


def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        needed = target - value
        if needed in seen:
            return seen[needed], index
        seen[value] = index
    return None


def count_values(values):
    counts = {}
    for value in values:
        counts[value] = counts.get(value, 0) + 1
    return counts

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

table = make_table()
put(table, 10, "Maya")
put(table, 18, "Ravi")
assert table[2] == [(10, "Maya"), (18, "Ravi")]
assert get(table, 10) == "Maya"
assert get(table, 18) == "Ravi"

put(table, 18, "Ravi Kumar")
assert get(table, 18) == "Ravi Kumar"
assert sum(len(bucket) for bucket in table) == 2

larger = resize(table, 16)
assert larger[10] == [(10, "Maya")]
assert larger[2] == [(18, "Ravi Kumar")]
assert get(larger, 10) == "Maya"
assert get(larger, 18) == "Ravi Kumar"
assert remove(table, 10) == "Maya"
assert get(table, 18) == "Ravi Kumar"
assert table[2] == [(18, "Ravi Kumar")]

try:
    get(table, 26)  # Same bucket, but this key was never inserted.
    raise AssertionError("missing keys must not return another value")
except KeyError:
    pass

try:
    remove(table, 10)  # Already removed.
    raise AssertionError("a missing key cannot be removed")
except KeyError:
    pass

try:
    make_table(0)
    raise AssertionError("zero buckets cannot hold a table")
except ValueError:
    pass

assert two_sum([2, 7, 11, 15], 9) == (0, 1)
assert two_sum([3, 3], 6) == (0, 1)
assert two_sum([3], 6) is None
assert count_values([1, 2, 1]) == {1: 2, 2: 1}
assert count_values([]) == {}