Membership and frequency counting

When do you use a map, and when do you use a set?

Use a hash map when a key needs associated information: student ID → name, number → occurrence count, or number → earlier array position. Use a hash set when you only need to know whether a key exists. A set stores unique elements and has no separate user-supplied value.

Membership means “is this element present?” Frequency means “how many times does it occur?” A set answers membership but loses repeated occurrences. A frequency map stores a count as the value for each distinct element.

In Python, {} makes an empty dictionary; set() makes an empty set. The expression key in dictionary checks keys, not values. If the map is {10: "Maya"}, 10 in map is true, but "Maya" in map is false.

seen = set()
seen.add(3)
seen.add(3)
print(len(seen))  # 1: a set keeps one copy of each element.

counts = {}
for value in [1, 2, 1]:
    counts[value] = counts.get(value, 0) + 1
print(counts)  # {1: 2, 2: 1}: a map keeps the occurrence counts.

How does it work?

1. Define what information each key needs.

   For frequency counting, a key is a number and its value is the count seen so far. For Two Sum, a key is an earlier array value and its value is that value’s position.

2. Read the existing information before updating it.

   counts.get(value, 0) gives the old count, or 0 for a new key. Add 1 and store it. For Two Sum, check whether target − value was seen at an earlier position.

3. Keep the timing of the update consistent with the problem.

   Two Sum needs two different positions. Check for a partner first, then add the current value. Adding it first could incorrectly pair an element with itself.

Work through an example

Counting [1, 2, 1] begins with {}. Read 1: its old count is 0, so store {1: 1}. Read 2: store {1: 1, 2: 1}. Read the final 1: increase its existing count to 2, giving {1: 2, 2: 1}.

For Two Sum on [2, 7, 11, 15] with target 9, begin with an empty earlier-value map. At position 0, value 2 needs partner 7. It is absent, so store 2 → position 0. At position 1, value 7 needs partner 2. Key 2 exists with position 0, so return positions (0, 1).

For [3] with target 6, a single 3 cannot form a pair with itself. Querying before inserting correctly finds no earlier partner. For [3, 3], the first 3 is stored before the second arrives, so the second finds a valid earlier position.

Time and space complexity

Frequency counting and the hash-map Two Sum solution visit n input values. Each performs a constant number of expected O(1) table operations, so total expected time is O(n) under the usual hashing assumptions. With severe collisions, n operations can each cost up to O(n), making worst-case total time O(n²).

If there are d distinct values, a frequency map stores d counts: O(d) auxiliary space, at most O(n). A Two Sum map can store up to n earlier values, so its auxiliary space is O(n). A set of distinct values uses O(d) storage but cannot return their positions without additional information.

Why it works

At each lookup in Two Sum, the map contains only values from earlier positions. A match therefore uses two distinct positions. In frequency counting, each stored count equals the number of times that key has appeared in the processed part of the input.

Common mistakes

• A set does not count duplicates. Adding 3 twice still leaves one element.
• {} creates a dictionary, not an empty set.
• For Two Sum, inserting before querying can reuse the current position as its own partner.

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([]) == {}