Hashing

What is it?

A hash map or set answers "have I seen this?" and "how many times?" in expected constant time. Most quadratic scans exist because the algorithm keeps re-deriving information it already computed; storing that information once collapses the inner loop entirely.

The core idea

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

1def find_complement_pair(nums, target):2    """The canonical swap: a backwards search becomes a lookup."""3    seen = {}4    for index, value in enumerate(nums):5        if target - value in seen:6            return [seen[target - value], index]7        seen[value] = index8    return []9 10 11def frequency(items):12    counts = {}13    for item in items:14        counts[item] = counts.get(item, 0) + 115    return counts16 17 18def group_by_signature(words):19    """Group items sharing a derived key."""20    groups = {}21    for word in words:22        key = "".join(sorted(word))23        groups.setdefault(key, []).append(word)24    return list(groups.values())

Common mistakes

• Inserting the current element before checking for its complement, which lets an element pair with itself.
• Using a mutable value as a key in languages that forbid it, or relying on object identity when value equality was intended.
• Assuming iteration order. Only some languages guarantee insertion order.
• Counting distinct keys when the question asked for total occurrences.