Hash maps and hash sets

Why hashing

Many problems ask the same small question again and again: "have I seen this before?" or "what do I know about this key?". With a list, each check scans the list, O(n), so checking every item costs O(n²). A hash map answers in O(1) on average, which turns many O(n²) solutions into O(n). That one swap is the most common speed-up in coding interviews.

A hash map stores key → value pairs, like roll number → student name. A hash set stores only keys and answers one question: is this key present? Both are built the same way, on a structure called a hash table.

The hash function, in plain words

A hash function turns a key into a whole number, called its hash. It must always give the same number for the same key, and it should spread different keys over many different numbers. The table keeps an array of slots called buckets, and a key goes to bucket hash(key) % number_of_buckets. Finding a key means: compute its hash, jump to that bucket, and look only there.

class TinyHashMap:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # key already there: update
                return
        bucket.append([key, value])

    def get(self, key):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return None

m = TinyHashMap()
m.put(3, "three")
m.put(11, "eleven")     # 11 % 8 == 3: same bucket as 3, a collision
print(m.buckets[3])     # Output: [[3, 'three'], [11, 'eleven']]
print(m.get(11))        # Output: eleven

Equal keys always have equal hashes. String hashes in Python are randomised each time the program starts (a protection against attacks), so never store hash("abc") and expect the same number in the next run.

Collisions: chaining and open addressing

A collision is two different keys landing in the same bucket. It cannot be avoided, because there are far more possible keys than buckets. There are two main fixes:

• Chaining: each bucket holds a small list of (key, value) pairs, as in the toy above; a lookup scans only that short list. Java's HashMap works this way (and turns very long chains into small trees).
• Open addressing: each slot holds at most one pair. If the slot is taken, the table probes other slots in a fixed order until it finds the key or an empty slot. Python's dict and set use open addressing.

To keep chains and probe sequences short, the table grows when it gets too full; the ratio of items to slots is called the load factor. Growing means making a bigger array and re-inserting every key, O(n) once, but it happens rarely, so inserting is O(1) amortised, like list.append in Module 1.

Average O(1), worst O(n)

The worst case happens when many keys collide, for example with a deliberately bad hash function. With built-in types it is very rare, and interviewers expect you to say "O(1) on average". The space cost of a map or set with n keys is O(n).

Which keys are allowed

A key must be hashable: its hash must never change while it sits in the table. Immutable built-ins are hashable: int, float, str, bool, and tuples whose items are all hashable. Lists, dicts and sets can change, so they are not: d[[1, 2]] = "x" raises a TypeError that says unhashable type: 'list'. To use a list or a pair of coordinates as a key, turn it into a tuple.

visited = set()
visited.add((2, 3))            # a grid cell (row, col) as a tuple
print((2, 3) in visited)       # Output: True

counts = {}
key = tuple([1, 2])
counts[key] = counts.get(key, 0) + 1
print(counts)                  # Output: {(1, 2): 1}

In JavaScript use Map and Set. A plain object turns every key into a string, so o[1] and o["1"] are the same key. Map keeps keys as they are, but arrays and objects are compared by identity: two separate [1, 2] arrays are two different keys. Use a string such as "1,2" as the key instead.

const seen = new Map();
seen.set('UPI', 3);
console.log(seen.get('UPI'), seen.has('card'), seen.size);  // 3 false 1

const o = {};
o[1] = 'a';
o['1'] = 'b';
console.log(Object.keys(o));   // [ '1' ]  (one key: 1 became "1")

Two-sum with a map

Given nums and a target, find two different positions whose values add up to the target. Brute force tries every pair, O(n²). With a map from value to index, walk once: for each x the partner you need is target − x. If the partner is already in the map, you are done; otherwise store x with its index. Check BEFORE storing, so an item is never paired with itself. O(n) time and O(n) extra space.

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))   # Output: [0, 1]
print(two_sum([3, 3], 6))           # Output: [0, 1]

Common mistakes

• Using a list for "seen" checks: x in a_list is O(n), so the loop becomes O(n²). Fix: use a set or a dict.
• Storing x before looking for target − x, so [3] with target 6 pairs the 3 with itself. Fix: check first, then store.
• Using a list or a set as a key. Fix: convert it to a tuple (or a frozenset when order does not matter).
• Reading d[key] for a missing key, which raises KeyError. Fix: d.get(key, default), check key in d first, or use collections.defaultdict.
• Adding or deleting keys while looping over the same dict (RuntimeError: dictionary changed size during iteration). Fix: loop over list(d) or build a new dict.
• Saying "O(1) always". Fix: say "O(1) on average, O(n) in the worst case".