Hash Tables

1. What It Is and Why It Exists

A hash table stores key→value pairs in an array of "buckets," using a hash function to map each key to a bucket index. Lookup, insert, and delete become "compute the hash, jump to that bucket" — average O(1) — instead of the O(n) scan a list or O(log n) walk a tree would need. It exists to answer "have I seen this?" / "what's associated with this?" in constant time, which is the single most common optimization in interviews: replace a nested-loop scan with one hash-map pass and an O(n^2) solution collapses to O(n).

The "why it works" intuition: hashing trades space for time — you allocate more buckets than entries so collisions stay rare, and a good hash spreads keys uniformly so each bucket holds O(1) elements on average. Collisions are resolved by chaining (a list per bucket) or open addressing (probe to the next slot). The catch every interviewer probes: this is average O(1); the worst case is O(n) when many keys collide into one bucket, and keys must be hashable: their hash must stay stable, and equal keys must have equal hashes. Python lists and dictionaries are not hashable; a tuple is hashable only when all of its elements are hashable.

2. Operations and Complexity

Space is O(n). The most-probed points: (1) average vs worst — say "average O(1), worst O(n) under adversarial collisions"; (2) keys must be hashable, with a stable hash and equality behavior; (3) a hash set is just a hash table without values — use it for membership/dedup. Note dict/set give no sorted order; if you need ordering, that is a tree's job, not a hash table's.

3. Implementation

The example implements insertion/update and lookup with a list of entries per bucket. A collision means multiple keys map to the same bucket; the load factor is the number of entries divided by the number of buckets. Capacity must be positive. Deletion is listed above as a standard hash-table operation but is not implemented in this example.

The table gives the usual hash-table bounds when resizing moves each existing entry directly to its new bucket. To reuse code, this example reinserts through put, which scans for duplicate keys. If all keys collide, those scans make its resize—and an insertion that triggers it—O(n^2). Its expected resize cost remains O(n) with well-distributed hashes. Appending existing entries directly to their new buckets avoids the redundant duplicate checks.

class HashMap:
    def __init__(self, capacity=8):
        self._buckets = [[] for _ in range(capacity)]   # chaining: list per bucket
        self._n = 0
        self._cap = capacity

    def _index(self, key):
        return hash(key) % self._cap        # hash -> bucket; needs a hashable key

    def put(self, key, value):
        bucket = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket): # collision scan: O(1) avg, O(n) worst
            if k == key:
                bucket[i] = (key, value)    # update existing
                return
        bucket.append((key, value))
        self._n += 1
        if self._n > self._cap:             # load factor > 1 -> grow
            self._resize()                  # expected O(n); collisions can cost more

    def get(self, key):
        for k, v in self._buckets[self._index(key)]:
            if k == key:
                return v
        raise KeyError(key)

    def _resize(self):
        old = [pair for b in self._buckets for pair in b]
        self._cap *= 2                      # geometric growth limits resize frequency
        self._buckets = [[] for _ in range(self._cap)]
        self._n = 0
        for k, v in old:
            self.put(k, v)

In a real interview, use Python's built-in dict and set — never hand-roll this unless explicitly asked (e.g., LeetCode 706 "Design HashMap"). dict for key→value, set for membership/dedup, collections.Counter for frequency counts, collections.defaultdict(list) for grouping.

4. When to Reach for It

• You need O(1) membership / "have I seen this?" → set.
• You need fast key→value lookup (two-sum complement, caching, memoization, index-of) → dict.
• You are computing frequencies / counts / grouping → Counter / defaultdict.
• A brute-force solution does a nested scan to find a matching element → trade the inner loop for a hash map and go from O(n^2) to O(n).
• Do not use a hash table when you need sorted order or range queries — use a balanced BST or another ordered collection. A heap is useful for repeated min/max extraction, not general range queries.

5. Common Pitfalls

• Unhashable key: using a list (or set/dict) as a key raises TypeError. Convert to tuple (or frozenset) only if the contained elements are also hashable.
• Claiming guaranteed O(1): it's average O(1); worst case is O(n). Say "average" or the interviewer will correct you.
• Mutating a key after insertion: if a key object's hash changes, you can never find it again. Keys must be effectively immutable.
• Relying on dict for ordering semantics: insertion order is preserved in modern Python, but it is not sorted order — don't confuse the two.
• KeyError on missing key: use d.get(k, default) or defaultdict/Counter instead of bare d[k].
• Adding or removing dict/set entries while iterating it: can raise RuntimeError or skip entries (updating an existing key's value is fine). Iterate over list(d) or collect changes first.

6. Interview Cheat Sheet

• "Hash table is average O(1) insert/lookup/delete by trading space for time; worst case is O(n) under collisions."
• "I use a set for membership, a dict for key→value, and Counter/defaultdict for frequencies — turning many O(n^2) scans into O(n)."
• "Keys need a stable hash and equality behavior; a tuple of hashable elements works, while a list does not."
• "If I need sorted order or range queries, a hash table is the wrong tool — use an ordered structure such as a balanced BST. A heap serves repeated min/max extraction."

Follow-ups:

• "How are collisions handled?" — Chaining (a list per bucket) or open addressing (linear/quadratic probing). Either keeps average O(1) with a low load factor; resize (double + rehash) keeps inserts amortized O(1).
• "When is it O(n)?" — When many keys hash to the same bucket (bad hash or adversarial input); the bucket degenerates to a linear scan.
• "Hash set vs hash map?" — A set is a hash table storing only keys (membership/dedup); a map stores key→value. Same complexity.