Data Structures & Algorithms / Contracts, sequences, and search / Lesson 5

Hash maps, membership, and duplicates

Use hashing for identity and counting while preserving duplicate semantics and qualifying expected-time claims.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Choose the key by the actual equality contract
Count occurrences instead of discarding them
Check the complement before publishing the current item

Choose the key by the actual equality contract

A hash map associates a key with a value; a set records key membership. A key should represent the identity or equivalence relation the task needs. Case-sensitive labels and normalized labels produce different groups, so normalization must be deliberate. Python keys must be hashable, and equal hashable objects must have equal hashes. A collision between unequal keys does not mean the keys become identical; the container still resolves equality. Mutable identity fields can invalidate a custom key design. Prefer immutable primitive or tuple keys for simple synthetic tasks and document the meaning of every component.

Count occurrences instead of discarding them

The first program builds a frequency map. Before each iteration, counts records exactly how often each previously visited token occurred. Incrementing one entry preserves that invariant. Converting the input directly to a set would answer which tokens exist but lose how many times they appear. The final sorted presentation is separate from map construction and adds sorting cost for the distinct keys. Do not advertise the complete function as linear if a required ordered output includes O(k log k) sorting for k unique keys. The synthetic example uses ordinary short strings with bounded-cost comparisons.

python Self-contained Python3 algorithm example using synthetic local data.

def frequencies(tokens):
    counts = {}
    for token in tokens:
        counts[token] = counts.get(token, 0) + 1
    return counts

print(sorted(frequencies(["map", "river", "map"]).items()))
print(frequencies([]))

Expected output

[('map', 2), ('river', 1)]
{}

The map preserves multiplicity; sorting makes the displayed order explicit without depending on set iteration.

Check the complement before publishing the current item

The second program returns indices of one two-sum pair. The map contains only earlier positions when the complement is tested, so the same element cannot satisfy both sides. setdefault preserves the first occurrence for an existing value, making the selected earlier index deterministic. Duplicate values remain useful: two separate 3 values can sum to 6, while one 3 cannot. This algorithm returns the first pair discovered by the scan under its stated policy, not every pair or a lexicographically optimized result. Different result contracts require different bookkeeping.

python Self-contained Python3 algorithm example using synthetic local data.

def two_sum_indices(values, target):
    first = {}
    for index, value in enumerate(values):
        complement = target - value
        if complement in first:
            return first[complement], index
        first.setdefault(value, index)
    return None

print(two_sum_indices([3], 6))
print(two_sum_indices([3, 3], 6))
print(two_sum_indices([2, 4, 7, 9], 11))

Expected output

None
(0, 1)
(1, 2)

The current index is stored only after the lookup, enforcing distinct positions. The last fixture finds 4+7 before it reaches 9.

Expected constant time needs assumptions

Hash lookup and insertion are commonly analyzed as expected constant time under suitable hashing and load assumptions; worst-case behavior can be worse, and hashing a long key has its own cost. Python implementation details and custom equality functions affect practical behavior. An array of tiny integers and a collection of large nested keys are not identical workloads. Avoid promising universal constant latency for dictionary access. Also distinguish expected hashing behavior from amortized resizing costs: both may appear in one implementation but explain different sources of average-looking performance. State the model used for the whole algorithm.

Do not confuse order with identity

A dictionary’s insertion-order behavior in supported Python versions is useful, but it does not sort domain values or decide which duplicate should win. A set should not be used to produce a required deterministic visible order without an explicit ordering step. If records share a label but have distinct identifiers, a map keyed only by label may overwrite legitimate records. Choose a multimap-like list of values, a frequency, or a compound key according to the task. Silent overwrite is a semantic decision even when the dictionary operation itself is correct.

Verify multiplicity and distinct-position rules

Compare two_sum_indices against a brute-force reference on tiny arrays with negatives, zeros, duplicates, empty input, and no solution. Validate returned positions are different, in bounds, and sum to target rather than requiring one arbitrary pair when several are valid. If a specific discovery policy is promised, test that separately. For frequency maps, sum all counts and confirm it equals input length. These conservation and validity properties expose accidental overwrites or deduplication. No randomized collision attack, external service, or load test is required for these safe local correctness checks.

Common errors and fixes

One value pairs with itself

Why it happens: The current value was inserted before checking its complement.
How to fix it: Lookup among earlier positions before insertion.
Prevent it next time: Test [3] and [3,3] with target6 separately.

A set loses required counts

Why it happens: Membership was substituted for multiplicity.
How to fix it: Use frequencies or retained occurrence lists.
Prevent it next time: Check total counts against input length.

Hash access is promised worst-case constant time

Why it happens: Expected-time assumptions and key cost were omitted.
How to fix it: Qualify the analysis and include hashing/equality costs.
Prevent it next time: Document key representation and workload.

Check your understanding

1. Why does the last two-sum fixture return (1,2), not (0,3)?

Show worked solution

The scan reaches 7 at index2 and finds its complement4 already at index1, so it returns before visiting9. Both pairs are valid for a find-any contract. If lexicographically smallest indices are required, the algorithm and proof must change.

2. What should be used when two records have the same title but both must remain?