Hashing Field Notes

0Why hashing exists

You already know two ways to store key-value pairs. An array gives O(1) access by index but O(n) search by value. A TreeMap (a balanced binary search tree) gives O(log n) for everything and keeps keys sorted. A hash map gives O(1) insert, remove and search on average, by turning each key into an array index with a hash function. The price: keys are stored in no useful order.

NeetCode's rule of thumb, which you should memorize: when a problem says "unique", "count", or "frequency", a hash map or hash set is almost certainly the tool.

1Hash usage: sets, maps, counting

Lesson 26 is about using hash sets and hash maps; lesson 27 is about building one. NeetCode says knowing the usage matters more than knowing the implementation, and interviewers agree: you will use a dict in hundreds of problems and implement one in almost none.

Set = keys only. Map = key-value pairs.

A hash set stores keys and answers one question: "is this key here?". A hash map stores key-value pairs and answers "what value belongs to this key?". Both refuse duplicate keys. In Python a hash set is set and a hash map is dict. Earlier in the course you saw the same two interfaces built on a tree (TreeSet, TreeMap). Same interface, different engine, different trade-offs.

The trade-off table (memorize it)

The HashMap column is the average case: what happens with a good hash function and few collisions. The worst case is O(n). It is widely accepted, including in interviews, to say "O(1)" for hash map operations. Say "O(1) average" if you want to be exact.

The one thing a tree map does better: order

A hash map is not ordered. You cannot walk its keys from smallest to largest. If you need the keys in sorted order you must sort them first, which costs O(n log n). A tree map gives you sorted order for O(n) with an inorder traversal. So: need sorted keys or "the next larger key"? Tree map. Need fast insert, remove, and lookup? Hash map. In interviews the second case is far more common.

Counting frequency: the phonebook example

Because a map cannot hold a key twice, and each key carries a value, a map can count. The lesson's example: a list of names, some repeated. Map each name to how many times it appears. For each name: if the key already exists, add 1 to its value; otherwise insert it with value 1.

names = ["alice", "brad", "collin", "brad", "dylan", "kim"]

countMap = {}
for name in names:
    # If countMap does not contain name
    if name not in countMap:
        countMap[name] = 1
    else:
        countMap[name] += 1

# countMap == {"alice": 1, "brad": 2, "collin": 1, "dylan": 1, "kim": 1}

Time and space of counting

The loop touches each of the n names once and every map operation is O(1), so counting is O(n). With a tree map each insert costs O(log n), so the same loop costs O(n log n). Space is O(n) in the worst case, more precisely proportional to the number of unique keys: five rows here, not six.

The same count, the Python way

NeetCode's if / else is the clearest version. In real code, Python gives you three shorter tools. All four produce the same dictionary; the check script proves it.

from collections import Counter, defaultdict

# 1. dict.get with a default: "current count, or 0 if missing, plus 1"
count = {}
for name in names:
    count[name] = count.get(name, 0) + 1

# 2. defaultdict(int): a missing key is created as 0 the first time you touch it
count = defaultdict(int)
for name in names:
    count[name] += 1

# 3. Counter: the whole loop in one call
count = Counter(names)
count["brad"]          # 2
count["nobody"]        # 0, no KeyError (a plain dict would raise)
count.most_common(1)   # [("brad", 2)]

# set: keys only. "how many unique names?"
len(set(names))        # 5
"brad" in set(names)   # True, O(1)

What can be a key?

A key must be hashable: Python must be able to turn it into a fixed number, and that number must never change. So the key must be immutable. str, int, float, bool, tuple and frozenset are hashable. list, dict and set are not, because you could change them after inserting and the stored hash would be wrong.

d = {}
d["alice"] = 1      # str   ok
d[42] = 2           # int   ok
d[(1, 2)] = 3       # tuple ok  (this is how you key by a pair, a grid cell, a sorted word)
d[[1, 2]] = 4       # TypeError: unhashable type: 'list'

hash("Alice") == hash("Alice")   # True: same key, same number, always

2Under the hood: hash function, resize, collisions

You are unlikely to be asked to implement a hash map from scratch, but the ideas show up in many algorithms and in system design (distributed caches, load balancing, sharding all use hashing). Hash maps are most commonly built on arrays. An empty hash map has size zero, but the underlying array does not start at size zero; NeetCode's starts at capacity 2.

The example pairs for the whole lesson:

hashmap["Alice"]  = "NYC"
hashmap["Brad"]   = "Chicago"
hashmap["Collin"] = "Seattle"

The hash function: string in, index out

To store "Alice" in O(1) we need a hash function: it takes the key and converts it into an integer, and that integer is the array index where the pair lives. Three requirements: the result must be a valid index; the same string must always produce the same integer; and ideally two different keys should not produce the same index. NeetCode's function is the simplest possible one:

1. Take the ASCII code of each character (ord(c) in Python).
2. Add them up. This sum can be big, larger than the array.
3. Take sum % capacity so the result is between 0 and capacity - 1.

Step 1-2 (turning the key into some big integer) is sometimes called pre-hashing; step 3 squeezes it into the array.

With an array of size 2 there are only two possible indexes, so a second key will very often land on the same one. Two keys mapping to the same index is a collision. Collisions are very common; they can be minimized but never fully avoided. Two things fight collisions: keeping the array roomy (resize) and having a plan for when they happen anyway (chaining or open addressing).

Resizing: double when half full

The map tracks two numbers. capacity is the length of the underlying array. size is how many pairs are stored. When space runs low, create a new array with 2 * capacity, exactly like the dynamic array chapter. The difference from a dynamic array: to keep collisions rare, we resize when the array is half full, not completely full. With capacity 2, inserting "Alice" makes size 1, which is half of 2, so the array doubles to 4 right away. The resize happens the moment the array becomes half full, not when the next pair arrives.

Rehashing: every key moves

After resizing, the pairs cannot simply be copied to the same indexes. The index was sum % capacity and capacity just changed, so the index changes too. Rehashing means: run every existing pair through the hash function again with the new capacity and re-insert it. In the video, Alice's made-up sum 25 gives 25 % 2 = 1 and then 25 % 4 = 1: she happens to stay at index 1. If the new value were 2 she would move to 2. Brad's 27 gives 27 % 4 = 3, index 3. Then the array is half full again (2 of 4), so it doubles to 8.

The three puts, traced

Two tables, same code, same three calls. The first uses the video's made-up sums so you can follow along with NeetCode. The second uses the real sums you will see when you run the check script. In both, notice when the resize happens: inside the put that made the array half full.

Both traces end with capacity 8, size 3, and a collision on index 1 that was solved by moving one step right. Only the names in the slots differ.

Collisions: two keys, one index

In the video, "Collin" hashes to 33, and 33 % 8 = 1: the same index as Alice. Two ideas that do not work: overwrite the slot (Alice is lost), or keep growing the array until the two keys separate (may never happen, and wastes huge memory). Two strategies that do work:

1. Chaining. Each slot holds a linked list. Alice and Collin both live at index 1, chained together. To look up Collin: hash to 1, walk the short chain. Worst case, if every key lands on one index, search and insert become O(n); on average the chains are tiny and it is O(1).

2. Open addressing. No slot may hold more than one pair. If index 1 is taken, try 2, then 3, and so on until an empty slot appears. Lookup does the same walk: start at the hashed index and keep checking the following slots until you find the key or hit an empty slot. This is the version NeetCode codes. It is more efficient than chaining when collisions are rare, but it has a hard limit (you can never store more pairs than the capacity) and it is trickier to get right. NeetCode's advice: stick with chaining unless you have a specific reason.

Why a prime capacity helps

NeetCode mentions that it is mathematically better to choose a prime number (divisible only by 1 and itself) for the capacity. The reason in one example: suppose your keys happen to be multiples of 4 (4, 8, 12, 16). With capacity 8, the indexes are 4, 0, 4, 0: two collisions, because 4 and 8 share a factor. With capacity 7, the indexes are 4, 1, 5, 2: all different. A prime shares no factor with any key pattern, so patterns in the keys do not turn into patterns in the slots. NeetCode uses 2, 4, 8 in the lesson for simplicity; real implementations either use primes or use a much better hash function so that the doubling does not matter.

3The code: open addressing, line by line

The lesson's implementation stores a list of Pair objects. size is the number of pairs in the map; capacity is the length of the underlying array. This is NeetCode's code exactly; the check script runs it on the three names and asserts every state in the trace tables above.

class Pair:
    def __init__(self, key, val):
        self.key = key
        self.val = val


class HashMap:
    def __init__(self):
        self.size = 0              # pairs stored
        self.capacity = 2          # length of the array
        self.map = [None, None]

    def hash(self, key):
        index = 0
        for c in key:
            index += ord(c)        # sum the ASCII codes
        return index % self.capacity

    def get(self, key):
        index = self.hash(key)

        while self.map[index] != None:       # stop at the first empty slot
            if self.map[index].key == key:
                return self.map[index].val
            index += 1                       # open addressing: look in the next slot
            index = index % self.capacity    # wrap around at the end
        return None

    def put(self, key, val):
        index = self.hash(key)

        while True:
            if self.map[index] == None:                  # 1. vacant: store here
                self.map[index] = Pair(key, val)
                self.size += 1
                if self.size >= self.capacity // 2:      #    half full → grow now
                    self.rehash()
                return
            elif self.map[index].key == key:            # 2. same key: update the value
                self.map[index].val = val
                return
                                                        # 3. different key: try the next slot
            index += 1
            index = index % self.capacity

    def remove(self, key):
        if not self.get(key):
            return

        index = self.hash(key)
        while True:
            if self.map[index].key == key:
                # Removing an element using open-addressing actually causes a bug,
                # because we may create a hole in the list, and our get() may
                # stop searching early when it reaches this hole.
                self.map[index] = None
                self.size -= 1
                return
            index += 1
            index = index % self.capacity

    def rehash(self):
        self.capacity = 2 * self.capacity
        newMap = []
        for i in range(self.capacity):
            newMap.append(None)

        oldMap = self.map
        self.map = newMap
        self.size = 0                  # put() will count the pairs again
        for pair in oldMap:
            if pair:
                self.put(pair.key, pair.val)   # re-insert with the NEW capacity

    def print(self):
        for pair in self.map:
            if pair:
                print(pair.key, pair.val)

What each method does

• hash: sum the ASCII codes (ord) of the characters, then % capacity.
• get: compute the index. While the slot is not empty: if the key matches, return its value; otherwise move to the next slot, wrapping with %. If you reach an empty slot the key is not here: return None.
• put: compute the index. Three scenarios. Slot vacant: store the pair, size += 1, and if size >= capacity // 2 call rehash. Slot holds the same key: update the value. Slot holds a different key: move to the next slot and check again.
• remove: if the key is absent, return. Otherwise find the slot holding the key and set it to None. This creates the hole described next.
• rehash: double capacity, build a new empty array, reset size to 0, and put every existing pair again. The re-puts cannot trigger another rehash: the old pair count was half of the old capacity, which is a quarter of the new one.

hm = HashMap()
hm.put("Alice", "NYC")        # capacity 2 → 4
hm.put("Brad", "Chicago")     # capacity 4 → 8
hm.put("Collin", "Seattle")   # collision on 1, stored at 2
hm.get("Collin")              # "Seattle"
hm.get("Dylan")               # None
hm.capacity, hm.size          # (8, 3)

The removal hole: why this remove() is buggy

The comment in remove is the most important line in the lesson. Open addressing relies on one invariant: "if I walk from a key's home index and hit an empty slot, the key is not in the map". Removing by writing None breaks that promise. Concrete case from the video: Collin's home index is 1, but he sits at 2 because Alice was at 1. Remove Alice, and slot 1 becomes a hole. Now get("Collin") starts at 1, sees None, and the while loop ends before it ever looks at slot 2. Collin is still in the array, but unreachable.

# the concrete case, video numbers (Alice 25, Brad 27, Collin 33)
lm.put("Alice", "NYC"); lm.put("Brad", "Chicago"); lm.put("Collin", "Seattle")
# slots: {1: Alice, 2: Collin, 3: Brad}
lm.remove("Alice")            # slot 1 becomes None
lm.map[2].key                 # "Collin"  (still there)
lm.get("Collin")              # None      (BUG: stopped at the hole)

# one fix: after clearing the slot, re-put everything that follows in the cluster
class HashMapFixed(HashMap):
    def remove(self, key):
        index = self.hash(key)
        while self.map[index] is not None:
            if self.map[index].key == key:
                self.map[index] = None
                self.size -= 1
                index = (index + 1) % self.capacity
                while self.map[index] is not None:      # everyone after the hole...
                    pair = self.map[index]
                    self.map[index] = None
                    self.size -= 1
                    self.put(pair.key, pair.val)          # ...is inserted again, so Collin slides into 1
                    index = (index + 1) % self.capacity
                return
            index = (index + 1) % self.capacity

Chaining in code (for comparison)

The lesson describes chaining in words only. Here it is in Python so you can see why it is simpler: every slot is a small list, and remove has no hole problem because deleting from one chain never hides another key.

class ChainedHashMap:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]   # each slot: a list of [key, val]

    def hash(self, key):
        return sum(ord(c) for c in key) % self.capacity

    def get(self, key):
        for k, v in self.buckets[self.hash(key)]:   # walk one short chain
            if k == key:
                return v
        return None

    def put(self, key, val):
        bucket = self.buckets[self.hash(key)]
        for item in bucket:
            if item[0] == key:
                item[1] = val                          # update
                return
        bucket.append([key, val])                       # append to the chain
        self.size += 1

    def remove(self, key):
        bucket = self.buckets[self.hash(key)]
        for i, item in enumerate(bucket):
            if item[0] == key:
                bucket.pop(i)
                self.size -= 1
                return

Time complexity of the implementation

All three are O(1) on average, assuming a good hash function and few collisions. The worst case, when everything collides into one chain or one long run of slots, is O(n). Amortized means "averaged over many operations": one rehash costs O(n), but it happens only every n/2 inserts, so each insert pays O(1) on average, exactly as with dynamic arrays.

4Five moves that solve most hashing problems

The lessons teach counting. Interviews use the dict and set in five recurring ways. Each template below is tested in the check script.

Move 1: Frequency map

When: the problem says count, frequency, most common, anagram, or "same letters". Count one thing, then compare or consume the counts.

def is_anagram(s, t):                    # LC 242
    if len(s) != len(t):
        return False
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1    # build
    for ch in t:
        if count.get(ch, 0) == 0:
            return False
        count[ch] -= 1                      # consume
    return True

# one-liners, same idea:
Counter(s) == Counter(t)
[x for x, _ in Counter(nums).most_common(k)]    # LC 347 Top K Frequent

Move 2: Seen-set

When: duplicates, "unique", "have I met this before", visited cells in a grid. Membership test is O(1), so the whole pass is O(n).

def contains_duplicate(nums):            # LC 217
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False
# or: len(set(nums)) != len(nums)

def longest_consecutive(nums):           # LC 128: the set answers "is x-1 here?" in O(1)
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:                 # x is the START of a run; only starts do work
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best                          # [100,4,200,1,3,2] → 4

Move 3: Complement lookup

When: "find two things that combine to a target". Instead of checking every pair (O(n²)), remember what you have seen and ask the map for the partner you need. Check before you insert, so an element cannot pair with itself.

def two_sum(nums, target):               # LC 1
    seen = {}                            # value → index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:                    # partner already seen?
            return [seen[need], i]
        seen[x] = i                      # insert AFTER the check
    return []

Move 4: Group by a canonical key

When: "group the items that are the same under some rule" (anagrams, rotations, same digit-sum). Compute one canonical key (a standard form that all members share) and use it as the dict key. For anagrams, either the sorted string or a 26-letter count tuple.

def group_anagrams(strs):                # LC 49
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))           # "eat","tea","ate" → ('a','e','t');  O(k log k) per word
        groups[key].append(s)
    return list(groups.values())

def group_anagrams_count(strs):          # same, with an O(k) key
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(s)   # tuple, because a list cannot be a key
    return list(groups.values())
# ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Move 5: Prefix sum + hashmap

When: "how many subarrays sum to k" or "longest subarray with sum k". A subarray sum is the difference of two prefix sums: sum(i..j) = prefix[j] - prefix[i-1]. So at each position ask the map: "how many earlier prefixes equal prefix - k?". Seed the map with {0: 1} for subarrays that start at index 0.

def subarray_sum(nums, k):               # LC 560
    count = 0
    prefix = 0
    seen = {0: 1}                        # prefix sum → how many times it appeared
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0) # each earlier prefix of (prefix - k) closes one subarray
        seen[prefix] = seen.get(prefix, 0) + 1
    return count                         # [1,1,1], k=2 → 2

Trace of [1, 1, 1], k = 2. The two subarrays are [1,1] at 0..1 (prefix 2 - prefix 0) and [1,1] at 1..2 (prefix 3 - prefix 1).

5Big-O summary

The three structures side by side, drawn. Say the HashMap column with the word "average" and the interviewer will trust you.

The asterisk: O(1) is the average with a good hash function and few collisions; the worst case is O(n). Insert is also amortized: one insert in every n/2 triggers an O(n) rehash, which averages out to O(1) per insert. Interviewers accept "O(1)" for hash map operations; saying "O(1) average, O(n) worst" shows you understand why.

6Mistakes to watch for

7Practice, in this order

Do these on LeetCode with the notes closed. For each one, say the move out loud before you type ("seen-set", "complement lookup") and then write it.

Your next step today: LeetCode 1, Two Sum. Write it from memory with the check-then-insert order, run it on [3, 2, 4], target 6, and confirm you get [1, 2], not [0, 0].

8Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.