Hash Maps and Sets: The Default Structure

The hash map is the most leveraged data structure in all of software — it turns "find this thing" from O(n) scan into O(1) lookup. Internalize "use a hash map" as the default answer and half of algorithm problems get simpler.

The pattern

def two_sum(nums, target):
    seen = {}                    # value → index
    for i, x in enumerate(nums):
        if target - x in seen:   # O(1) — not a scan
            return [seen[target - x], i]
        seen[x] = i

Any "find a complement" problem — two-sum, pair-matching, grouping by key — is a hash map. The trick is recognizing that the inner for y loop is really "does X exist?" — and a hash map answers that in O(1).

Sets are hash maps with no values

Dedup, membership, intersection, difference — every "is this thing in the collection?" question:

seen = set()                # O(1) membership
common = set_a & set_b      # intersection
only_in_a = set_a - set_b   # difference

Real-world hash maps

• Caching — cache[key] is a hash map; TTL is bookkeeping on top.
• Indexing — index[user_id] maps to a list of rows; joins become O(1) instead of O(n).
• Counting — Counter(x) in Python, Map<*, int> everywhere else — counting frequencies without a sort.
• Dedup + preserve order — dict.fromkeys(list) in Python; an ordered set elsewhere.

Field notes

• The hash function is the secret — hash(x) distributes keys evenly; a bad hash function degrades to O(n) worst case. Use the language's built-in, don't roll your own.
• Hash maps have no order — dict in Python 3.7+ preserves insertion order, but that's a convenience, not a guarantee to rely on for correctness.
• The space cost is real — a hash map of n items is O(n) memory; it's "cheap" until it's not.