Equality and key design

What makes a good key?

A key must represent the identity you want to look up. Two students with the same name may need different ID keys. If a problem treats two things as the same, their keys must compare equal. If it treats them as different, your key design must preserve that difference.

A hashable key has a hash that stays consistent while it is stored, and equal keys must have equal hashes. Python integers and strings are common keys. A tuple can be a key when all its elements are hashable. A list is not a dictionary key because its contents can change.

The value does not have the same restriction: a dictionary value can be a list or another dictionary. Hashing selects a candidate location; key equality identifies the entry. Different keys can produce the same hash number or the same bucket index, so a collision is not an equality test.

visits = {}
visits[(1, 23)] = "first point"
visits[(12, 3)] = "second point"
print(visits[(1, 23)])  # first point: the two keys stay separate.

# A string key can map to a list value.
subjects = {"Maya": ["Math", "Physics"]}

Work through an example

Suppose you store grid positions as keys. Concatenating numbers without a separator turns both row 1, column 23 and row 12, column 3 into the text "123". You have accidentally made two distinct points into one key. Tuple keys (1, 23) and (12, 3) keep the boundaries and remain different.

For grouping anagrams, the identity is different: "eat" and "tea" should share a group. Sorting each word’s letters produces the same signature "aet". Use that signature as the key and a list of original words as the value. A character-count tuple is another valid signature when you have a defined alphabet.

If username matching should ignore letter case, normalize it before insertion and lookup, using the same agreed rule. For example, casefold() can produce a key for case-insensitive Unicode matching. Normalizing only during insertion would make later lookups inconsistent.

Time and space complexity

Key preparation is part of the algorithm’s time. Sorting a word of k characters for an anagram signature costs O(k log k) time and O(k) space for the new representation. Building a count signature for an alphabet of size a costs O(k + a) time and O(a) extra space.

An expected O(1) table lookup counts table operations under bounded-cost key hashing and equality. A new long string may need O(k) work to hash, and comparing equal long strings can inspect O(k) characters. Storing long keys also takes memory for those keys; the number of entries alone does not describe all object storage.

Why it works

The key expresses the problem’s definition of sameness, and both insertion and lookup build it in the same way. Equal keys must have equal hashes. A key’s hash and equality behavior must remain consistent while it is in the table.

Common mistakes

• Do not merge different logical identities by creating an ambiguous key such as concatenated numbers without boundaries.
• Do not use a Python list as a dictionary key. A tuple is usable only when its elements are hashable too.
• Never assume equal hash numbers prove equal keys.

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