Hash Maps and Sets

A hash map (a "dictionary" in Python, a "map" in C++/Java) stores key–value pairs and lets you look up the value for a key almost instantly, on average in $O(1)$ time no matter how many pairs it holds. A set is the same machine without the values: it just answers "is this thing in the collection?" Both are the reason so many interview problems that look like they need two nested loops collapse to a single pass.

The idea behind the speed is a hash function: it turns a key (a string, a number, a tuple) into an integer, and that integer picks a slot in an internal array. So instead of scanning the whole collection to find a key, you compute where it must be and jump straight there. Reading, writing, and deleting all become one array access plus a hash computation, independent of size.

Two keys can hash to the same slot, a collision. Real implementations handle this by keeping a short list in each slot (chaining) or probing nearby slots (open addressing), and by growing the array when it gets too full so the average chain stays short. That growth is amortised: an occasional expensive resize, spread over many cheap operations, still averages out to $O(1)$ per operation.

How it compares to the alternatives

Operation	Unsorted array	Sorted array	Hash map / set	Balanced BST
Look up a key	$O(n)$	$O(\log n)$	$O(1)$ avg	$O(\log n)$
Insert	$O(1)$	$O(n)$	$O(1)$ avg	$O(\log n)$
Delete	$O(n)$	$O(n)$	$O(1)$ avg	$O(\log n)$
Visit keys in order	$O(n\log n)$	$O(n)$	not supported	$O(n)$

The hash map wins every single-key operation but gives up order: you cannot ask "what is the smallest key" or iterate sorted without extra work. When you need ordering or range queries, reach for a sorted array with binary search or a balanced tree instead.

Worked example: two-sum, unsorted, in one pass

Given a = [8, 3, 11, 7, 2] and target T = 10, find two entries that sum to T. The brute force checks every pair, $O(n^2)$. With a hash map you check each number's complement as you go:

def two_sum(a, T):            # O(n) time, O(n) space
    seen = {}                 # value -> index
    for i, x in enumerate(a):
        if T - x in seen:     # complement already passed?
            return (seen[T - x], i)
        seen[x] = i
    return None

Walk it: at 8, is 10 - 8 = 2 in seen? No, store 8. At 3, is 7 in seen? No, store 3. At 11, is -1? No. At 7, is 10 - 7 = 3 in seen? Yes, at index 1, so return (1, 3). One pass, each lookup $O(1)$, total $O(n)$ time and $O(n)$ space. Notice this needs no sorting, unlike the two-pointer version, which is the classic trade-off: the hash map spends memory to avoid the $O(n\log n)$ sort.

The set as a "seen" filter and the map as a counter

Two idioms cover a huge share of interview questions. A set tracks what you have already encountered, for detecting duplicates, cycles, or visited graph nodes:

seen = set()
for x in stream:
    if x in seen: ...        # duplicate!
    seen.add(x)

A map used as a counter tallies frequencies in one pass, the backbone of anagram grouping, majority-element, and most sliding-window problems:

from collections import Counter
freq = Counter(words)        # word -> count, all in O(n)

Where it bites

• Worst case is $O(n)$, not $O(1)$. If many keys collide (a poor hash, or an adversary feeding pathological inputs), operations degrade to a linear scan. Interviewers like to hear you say "$O(1)$ average, $O(n)$ worst case."
• No ordering. Do not expect keys to come back sorted, or even in insertion order in every language. Need order? Use a different structure.
• Keys must be hashable and stable. Mutable keys (a list in Python) either fail or, worse, silently misbehave if mutated after insertion. Custom objects need a sensible hash and equality.
• Memory is the price. A hash map storing n items is $O(n)$ space, which can lose to an in-place method under a tight memory budget.

In quant-dev interviews the hash map is the default tool for de-duplication, frequency counting, memoising recursive calls, complement lookups, and grouping. It is also the core of the LRU Cache Design question (a hash map plus a doubly linked list) and pairs constantly with Prefix Sums to count subarrays with a given sum.