Hashing Foundations

8 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

Why Searching a List Is Slow

A list is a row of boxes. In Python you write it with square brackets: names = ['Asha', 'Ben', 'Chen', 'Dia', 'Esha']. Each box has a position number called its index. The first box is index 0, so names[0] is 'Asha', and names[-1] is the last box, 'Esha'. len(names) counts the boxes: 5. names.append('Fay') adds a new box at the end. Now a question: is 'Esha' in the list? Python has no shortcut. The words 'Esha' in names open the boxes one by one from the left: Asha, Ben, Chen, Dia, Esha. That is 5 looks, and we call each look a step. For a name that is not there, like 'Zed', Python must open all 5 boxes before it can say no. With 1,000 names, one search can take up to 1,000 steps. Programmers write that as O(n), said 'order n'. It only means: the steps grow in step with n, the number of items. Ask the question for every one of 1,000 names and you do up to 1,000 x 1,000 = 1,000,000 steps. A list is a fine way to keep things in order. It is a slow way to answer 'is this in here?'.

The intuition

The trouble is not that the computer is slow. The trouble is that nothing tells it where to look, so it must open every box until it gets lucky. Now imagine every name had its own labelled spot. You would walk straight to that spot and look once. It would take 1 step for 5 names and 1 step for 5,000 names. We write that as O(1), said 'order one': the steps do not grow with n. Everything in this lesson is about building such a table, so that 'is it here?' costs one look instead of a scan.

A real-world analogy

Picture a bookshelf where the books stand in the order they arrived, with no labels. To check whether you own one book, you run a finger along the shelf and read every spine until you find it or reach the end. The shelf is the list, each spine you read is one step, and a shelf of 1,000 books can mean 1,000 reads. Now picture a library where every title has a numbered slot: you go straight to the slot and see at once if the book is there. That is the lookup table.

names = ["Asha", "Ben", "Chen", "Dia", "Esha"]   # a list: boxes in a row
print(names[0], names[-1])        # Asha Esha (index 0 is the first box, -1 the last)
def find(names, target):          # def defines a function: a named recipe
    steps = 0
    for name in names:            # open the boxes one by one
        steps += 1                # add 1 to steps: one look = one step
        if name == target:        # == asks: are these two equal?
            return steps          # return hands the answer back and stops
    return steps                  # not found: we opened every box
print(find(names, "Esha"))        # 5
print(find(names, "Zed"))         # 5
names.append("Fay")               # add a box at the end
print(len(names), "Zed" in names) # 6 False

The Dictionary: Labels and Values

A dictionary (dict for short) stores pairs: a label and the thing that goes with it. The label is called the key, and the thing is called the value. Think of a canteen price board: the key is the item, the value is its price. In Python: prices = {'tea': 10, 'samosa': 15}. To read a value, give the key in square brackets: prices['tea'] is 10. To add a pair, assign to a new key: prices['juice'] = 20. To change a price, assign to a key that is already there: prices['tea'] = 12 replaces the 10. Keys are unique, so a dictionary never holds two 'tea' keys. The words 'samosa' in prices ask whether a key exists: True. Reading a key that does not exist, like prices['cake'], stops the program with a KeyError. The safe way is prices.get('cake', 0), which returns a default you choose (here 0) instead of an error. del prices['samosa'] removes a pair. To walk through every pair, write for item, price in prices.items(). The pairs come out in the order they were added.

The intuition

Why not keep a list of pairs? Because finding 'tea' in a list of pairs means opening pair after pair: a scan. A dictionary skips the scan. You hand it the key and it takes you straight to the value. The keys also carry the meaning: prices['tea'] reads like a sentence, while prices[3] on a list makes you remember which item sits at index 3. Whenever you catch yourself thinking 'for this thing, remember that thing', reach for a dictionary.

A real-world analogy

A coat-check desk hands you a numbered tag when you leave your coat. Later you show the tag and the attendant fetches your coat at once, without looking through every coat. The tag is the key, the coat is the value, and the desk is the dictionary. Two coats never share a tag, just as two pairs never share a key. If you hand in a new coat under the same tag, it replaces the old one.

prices = {"tea": 10, "samosa": 15}   # key -> value
print(prices["tea"])                 # 10
prices["juice"] = 20                 # add a new pair
prices["tea"] = 12                   # same key: the value is replaced
print("samosa" in prices)            # True (in checks the keys)
print(prices.get("cake", 0))         # 0: a default, not an error
del prices["samosa"]                 # remove a pair
for item, price in prices.items():   # walk through the pairs
    print(item, price)               # tea 12, then juice 20
print(len(prices))                   # 2

How a Hash Map Finds Things Fast

Here is the trick inside a dictionary. Picture a wall of 5 lockers numbered 0 to 4. We need a rule that turns any key into a locker number. Such a rule is called a hash function, and the number it gives is the key's hash. Our toy rule: take a roll number and keep the remainder after dividing by 5. The symbol for the remainder is %, so 12 % 5 is 2 (12 = 2 x 5 + 2). Roll 12 goes into locker 2, roll 23 into locker 3 (23 % 5 = 3), roll 41 into locker 1 (41 % 5 = 1). To find roll 23 later, apply the same rule, 23 % 5 = 3, and open only locker 3. No scanning. Sometimes two keys get the same locker: 17 % 5 is 2 too. That is a collision. The locker just keeps a short list, 12 and 17, and we look through that tiny list. A table like this is called a hash map, and Python's dict is one. Python uses its own, more mixed-up rule, and builds a bigger wall when the lockers get crowded, so the lists stay short. Adding, finding and deleting take about 1 step on average: O(1) on average.

The intuition

Why does the lookup not slow down as the wall grows? Because the rule does the finding, not you. With 5 keys or 5 million, you do one calculation and open one locker. Only collisions cost anything, and a good rule spreads keys out so each locker holds one or two. This also explains the key rule: the rule must give the same locker every time. A tuple such as (1, 2), a fixed row that never changes, is a fine key. A list can change after it is stored, its locker would change with it, and Python refuses it with an error.

A real-world analogy

Think of an old library card catalogue where cards are filed in drawers by the first letter of the title. To find 'Atlas' you open drawer A and flick through a few cards, not the whole catalogue. 'Atlas' and 'Anatomy' share drawer A, which is a collision, and you simply check the few cards inside. The title is the key, 'first letter' is the hash function, and the drawer is the locker.

lockers = [[] for _ in range(5)]      # range(5) gives 5 turns: 5 separate empty lists
def locker_of(key):
    return key % 5                    # the rule: remainder after dividing by 5
for roll in [12, 17, 23, 41]:
    lockers[locker_of(roll)].append(roll)   # put each roll in its locker
print(lockers)                        # [[], [41], [12, 17], [23], []]
print(locker_of(23))                  # 3
print(23 in lockers[locker_of(23)])   # True (we opened only locker 3)
print(30 in lockers[locker_of(30)])   # False (locker 0 is empty)
seats = {(1, 2): "Asha"}              # a tuple (a fixed row) as a key
print(seats[(1, 2)])                  # Asha

Sets and the 'Have I Seen It?' Check

Sometimes you do not need a value at all. You only want to know: is this thing here? That is a set. A set is a hash map that keeps keys and no values, so asking x in s is the same one-locker look, O(1) on average. Make an empty set with set(), add with s.add(x), and test with x in s. Careful: {} alone makes an empty dictionary, not a set. A set never holds a thing twice; adding a repeat changes nothing. Take raffle tickets [100, 4, 200, 1, 3, 2, 4]. That is seven tickets, but 4 appears twice, so the set holds six different numbers. This gives the 'have I seen it?' check: walk through the tickets and, before adding one, ask whether it is already in the set. The first 4 is new. The second 4 is found: a repeat. The same set answers 'is the next number there?' in one look. Starting at 1, ask: is 2 in the set? 3? 4? 5? A while loop repeats as long as its question is True, so it can climb 1, 2, 3, 4 and stop when 5 is missing.

The intuition

A list answers 'is it here?' by scanning. A set answers it with one look. And because a set throws away repeats, it also tells you how many different things you have: len(set(tickets)) is 6 even though there are 7 tickets. Use a set when the only question is 'seen it or not?'. Use a dictionary when you must also remember something about each thing, like how many times it came or where it was.

A real-world analogy

A guard at a hall door holds a guest list and only checks whether your name is on it. He writes nothing next to it. The list is the set, each guest's name is a key, and 'is the name on the list?' is the in test. If a name is written twice by mistake, it is still one guest, just as adding a repeat to a set changes nothing. When someone arrives, he finds the name in one look, not by reading every line.

tickets = [100, 4, 200, 1, 3, 2, 4]
seen = set()                    # an empty set (note: {} would be a dict)
for t in tickets:
    if t in seen:               # one look, not a scan
        print("repeat:", t)     # prints: repeat: 4
    seen.add(t)                 # add it (adding a repeat changes nothing)
print(len(seen))                # 6
last = 1                        # a run starts at 1 (0 is not in the set)
while (last + 1) in seen:       # while repeats as long as this is True
    last = last + 1             # 2, 3, 4 are there; 5 is not
print(last)                     # 4 (the run is 1, 2, 3, 4)

Counting Things with a Dictionary

Counting is the most common job for a dictionary. The key is the thing, and the value is how many times we have seen it. Take the word 'banana'. A string is a row of characters, and for ch in word hands them over one at a time: b, a, n, a, n, a. For each letter we want to add 1 to its count. The first time we meet a letter it has no count yet, and reading a missing key would crash. So we use counts.get(ch, 0), which means 'the count so far, or 0 if there is none', and add 1: counts[ch] = counts.get(ch, 0) + 1. After six letters the dictionary holds b: 1, a: 3, n: 2. The counts add up to 6, the length of the word. Two dictionaries are equal when they hold the same pairs, in any order. 'banana' and 'nanaba' give equal counts: they have the same letters, so one is a rearrangement of the other, which is called an anagram. 'bananas' has an extra s, so its counts differ. A letter is also a number: ord('a') is 97 and ord('b') is 98, so ord(ch) - ord('a') is 0 for 'a' and 1 for 'b'.

The intuition

Counting is 'remember one number per thing', and a dictionary is made for it. One pass over n items does n small updates and nothing is searched. The dictionary has only as many keys as there are different things, however long the input is. And once you have counts, you can compare two collections without caring about order: equal counts means the same contents. The 26 numbers from ord are a bonus: when the keys are the 26 small letters, a list of 26 counters works just like the dictionary.

A real-world analogy

At a school election, a volunteer keeps a tally sheet. Each candidate has a line, and every vote is one more stroke on that line. A candidate with no line yet gets a fresh line the first time a vote arrives, which is what get(ch, 0) does. The candidates are the keys, the stroke totals are the values, and the sheet is the dictionary. Two ballot boxes with the same totals for each candidate gave the same result, whatever order the votes came out in.

def count_letters(word):
    counts = {}
    for ch in word:                          # one letter at a time
        counts[ch] = counts.get(ch, 0) + 1   # 0 if new, then add 1
    return counts
a = count_letters("banana")
print(a)                                     # {'b': 1, 'a': 3, 'n': 2}
print(a == count_letters("nanaba"))          # True (same counts, any order)
print(a == count_letters("bananas"))         # False (an extra s)
print(ord("a"), ord("b"), ord("n") - ord("a"))   # 97 98 13

Grouping Things by a Key

Sometimes the value we keep for a key is not a number but a whole list: a group. Take the words stop, pots, car, tops, arc, sun. We want anagrams together. The word itself cannot be the key, because 'stop' and 'pots' look different. But if we sort the letters, rearrangements look the same: sorted('stop') gives the list ['o', 'p', 's', 't']. The call ''.join(that_list) glues the pieces together with nothing between them: 'opst'. 'pots' and 'tops' give 'opst' too. Call this the signature, and use it as the key. Then file each word in the list kept under its signature: groups[key].append(word). The first time a signature shows up there is no list yet, so we would need an if to create it. defaultdict(list), from Python's collections module, does this for us: reading a missing key first creates an empty list there. At the end, groups.values() holds the groups. Keys must be things that never change: a string works, and so does a tuple. A list does not.

The intuition

The whole idea is to choose a key that is the same for the things you want together and different for everything else. Then the dictionary does the grouping for you, with no comparing of pairs. Comparing every pair of 6 words takes 6 x 5 / 2 = 15 comparisons. Signatures look at each word once: 6 steps. For 1,000 words, that is 499,500 pairs against 1,000 steps. The hard part is only inventing a good key.

A real-world analogy

Sorting laundry: you pick up each item and drop it into the basket for its colour. You never compare one sock with every other sock. The colour is the key, each basket is a list, and the whole row of baskets is the dictionary. An item tells you its basket by itself, and a new colour just needs a new basket, which is what defaultdict does automatically.

from collections import defaultdict
words = ["stop", "pots", "car", "tops", "arc", "sun"]
print("".join(sorted("stop")))        # opst (the signature)
groups = defaultdict(list)            # a missing key starts as an empty list
for word in words:
    key = "".join(sorted(word))       # stop -> opst, car -> acr
    groups[key].append(word)          # file the word under its signature
print(dict(groups))
# {'opst': ['stop', 'pots', 'tops'], 'acr': ['car', 'arc'], 'nsu': ['sun']}
print(list(groups.values()))          # the groups, without their keys

Asking for the Partner: Complement and Running Total

Many questions have the shape 'find two things that fit together'. Take the tokens [3, 5, 2, 6] and the target 8: which two add up to 8? Checking every pair means 4 x 3 / 2 = 6 pairs, and 499,500 pairs for 1,000 tokens. Better: when you stand on a token x, you know exactly which partner you need, target - x. That partner is called the complement. Instead of searching for it in the list, ask a dictionary that remembers every token passed so far, with its position. enumerate(nums) hands over the position and the token together: 0 and 3, then 1 and 5, and so on. At 3, the complement is 8 - 3 = 5. It is not in seen, so we store 3 with position 0. At 5, the complement is 3. It is in seen, at position 0. Answer: positions 0 and 1. Look in the dictionary before storing the current token, otherwise a token could pair with itself: with [4] and target 8, the 4 would find itself.

The intuition

You do not hunt for the partner. You work it out with one subtraction and ask the table. So the whole pass over n tokens is about n steps. The same move works on running totals. The total so far after each token of [3, 5, 2, 6] is 3, 8, 10, 16. Tokens in a row add up to the difference of two totals: 10 - 3 = 7, which is 5 + 2. So to find a stretch that adds up to 7, at total 10 the partner you need is 10 - 7 = 3, a total you may already have stored.

A real-world analogy

At a dance class everyone must find a partner whose badge number plus their own makes 8. Each arriving dancer works out the badge number they need, 8 minus their own, and checks the board where the earlier dancers wrote their badge number and where they are standing. If the number is on the board, they walk over. If not, they write their own badge on the board and wait. The board is the dictionary, the needed badge is the complement.

def find_pair(nums, target):
    seen = {}                          # token -> position
    for pos, x in enumerate(nums):     # position and token together
        need = target - x              # the partner we are looking for
        if need in seen:               # ask BEFORE storing x
            return seen[need], pos
        seen[x] = pos                  # remember x for later tokens
    return None                        # no pair found
print(find_pair([3, 5, 2, 6], 8))      # (0, 1)
print(find_pair([4], 8))               # None means "nothing found"
total = 0                              # the running total so far
for x in [3, 5, 2, 6]:
    total = total + x                  # add the next token
    print(total)                       # 3, then 8, then 10, then 16

Using the List Itself as the Table

Sometimes the keys are small whole numbers, like 1 to n. Then you need no hash map: a list already has numbered boxes, so the box number is the key. Take nums = [3, 1, 3, 2]: n = 4 values, every one between 1 and 4. Value v belongs in slot v - 1, because slots start at 0, so 3 belongs in slot 2. Now the list can be its own notebook. To remember 'I have seen v', flip the number in slot v - 1 to negative with nums[slot] = -nums[slot]. Later, if that slot is already negative, v was seen before: a repeat. A number we read may already be flipped, so take abs(...), its size without the minus sign: abs(-3) is 3. Another way is to put every value home, into its own slot, by swapping two boxes with a, b = b, a. Then the first slot holding the wrong number shows the smallest missing positive whole number. Python assigns the left side one part at a time, so write home = nums[i] - 1 first, and then nums[i], nums[home] = nums[home], nums[i].

The intuition

A hash map has to work out a locker for every key. But when the keys already are 0, 1, 2 ... n, the key itself is the locker number and nothing needs working out. Better still, the notebook costs no extra memory: it is written on the list we were given, so the extra space is O(1). The price: you change the list as you work. And it only works when every value is a legal slot number. A value that is 0, negative or bigger than n has no slot, so check the range before you use it as an index.

A real-world analogy

A row of numbered parcel trays, 1 to 4, where parcel number v belongs in tray v. Instead of keeping a separate register of which parcels have arrived, you put a red sticker on the tray when its parcel is seen. If you reach a tray that already has the sticker, that parcel came twice. The trays are the list's slots, the tray number is the key, and the sticker is the minus sign.

nums = [3, 1, 3, 2]
dups = []
for i in range(len(nums)):         # i = 0, 1, 2, 3
    value = abs(nums[i])           # may already be flipped negative
    slot = value - 1               # value 3 -> slot 2
    if nums[slot] < 0:             # flipped before: we saw this value
        dups.append(value)
    else:
        nums[slot] = -nums[slot]   # flip it to mark "seen"
print(dups)                        # [3]
print(nums)                        # [-3, -1, -3, 2]

All DSA learning paths