Build a Hash Table

You write ages["asha"] and the answer comes back at once, even when the dict holds a million pairs. It feels like magic, but it is a list plus a rule that says where each pair goes. In this lesson you write that rule, break it on purpose, repair it in two ways, and then see what Python does differently. It is part of the optional depth at the end of the track.

Learning Objectives

After this lesson, you will be able to:

Explain what a hash function is, and work out the slot for a key with index = hash % size
Say what a collision is, and why collisions cannot be avoided once keys outnumber slots
Build a hash table with separate chaining: put, get, delete and resize
Build a hash table with linear probing, and explain why delete must leave a tombstone
Show by counting why doubling the table gives amortized O(1) puts, and why growing by a fixed step does not
Show how a bad hash function turns O(1) into O(n)
Describe how CPython's dict differs, and choose between a dict, a set and a sorted list for a job

Prerequisites

Before You Start

Review

#A dict is a magic box, until you build one

Start with a guess about the claim that makes dicts famous.

What Do You Think?

A dict holds 1,000,000 pairs. You look up one key. About how many stored keys does Python compare with yours before it finds the right pair?

Now picture a coat check. You hand over a coat and get a ticket with a number. Later the clerk walks to that hook and never searches the other coats. A dict works like this, except that it makes up the ticket number from your key, using a fixed rule.

Here are the words for this lesson. A key is what you look things up by. A value is what you stored under it. Together they are a pair. The table is the list that holds the pairs, and each place in it is numbered. A hash function is the rule that turns a key into a whole number, called the hash. The index is the place number worked out from the hash.

Sometimes two different keys give the same index. That is a collision. We use two names for places. A place that holds a whole list of pairs is a bucket. A place that holds at most one pair is a slot.

Every code cell runs in order, so later cells reuse the names from earlier ones.

#From a key to a slot

The rule has two parts. A hash function makes a whole number from the key, and then we shrink that number to a place in the table. A good hash function follows three rules:

The same key always gives the same number. If it did not, a lookup could never find where the pair was stored.
Different keys should give very different numbers, so the pairs spread out.
It should be quick, because it runs on every lookup.

Here is a small one for text. It walks over the letters. For each letter it multiplies the running total by 31 and adds the letter's code number, which ord gives.

pythonrunnable cell

def simple_hash(text):
    """Turn text into a whole number. The same text always gives the same number."""
    total = 0
    for ch in text:
        total = total * 31 + ord(ch)
    return total


print(simple_hash("cat"), simple_hash("cat"))
print(simple_hash("act"))

Output:

98262 98262
96402

Trace "cat" by hand before trusting the code. The letter codes are 99 for c, 97 for a and 116 for t.

Letter	Code	Running total before	Running total after
c	99	0	0 x 31 + 99 = 99
a	97	99	99 x 31 + 97 = 3,166
t	116	3,166	3,166 x 31 + 116 = 98,262

The multiply by 31 makes the order of the letters matter, so "cat" and "act" get different numbers.

Python has its own hash(). For text, Python mixes in a random number each time it starts, as a safety measure, so its numbers change from run to run. Ours stays the same, which keeps this lesson's output steady. Whole numbers are simple: hash(35) is 35. Hashing text takes time in proportion to its length, so for very long keys the O(1) claims below hide that extra cost.

Now the second part. A hash like 98,262 is far too big for a table of 8 slots, so we take the remainder after dividing by the table size. In Python that is the % operator.

index = hash % size

The remainder is always from 0 to size - 1, so it is always a real place. For "cat": 98,262 = 8 x 12,282 + 6, so the index is 6. The cell does this for eight animal names.

pythonrunnable cell

words = ["cat", "dog", "emu", "owl", "fox", "bee", "ant", "hen"]
for word in words:
    h = simple_hash(word)
    print(word, h, h % 8)

Output:

cat 98262 6
dog 99644 4
emu 100557 5
owl 110468 4
fox 101583 7
bee 97410 2
ant 96743 7
hen 103185 1

What Do You Think?

The hash of the word dog is 99,644. The table has 16 slots. Which slot does dog go to?

#Collisions: two keys, one slot

In the output above, dog and owl both land on slot 4, and fox and ant both land on slot 7. A careless table would just write each word into its slot:

pythonrunnable cell

table = [None] * 8
for word in words:
    table[simple_hash(word) % 8] = word
print(table)
print(len([w for w in table if w]), "of", len(words), "words survived")

Output:

[None, 'hen', 'bee', None, 'owl', 'emu', 'cat', 'ant']
6 of 8 words survived

Two words were overwritten and lost. No hash function can avoid collisions for good, because there are far more possible keys than slots. Even five keys in 8 slots collide about four times in five. The chance that all five get different slots is 8 x 7 x 6 x 5 x 4 divided by 8^5, which is about 20 percent.

So every hash table needs a plan for collisions. There are two classic plans. Chaining lets a cell hold a list, so colliding keys share it. Open addressing lets a cell hold one pair, and a key that finds its cell taken tries another cell. You build chaining first, because it is easier to read.

#Fix one: separate chaining

With separate chaining, each place in the table is a bucket that holds a list of pairs. A new pair goes to the end of the list in its bucket. To look a key up, you work out its bucket and walk that one short list.

One word before the code. The load factor is the number of pairs divided by the number of buckets. It is also the average length of a chain. Trace five words into 8 buckets by hand.

Step	Key	Hash % 8	Bucket after the step
1	cat	6	bucket 6 holds cat
2	dog	4	bucket 4 holds dog
3	emu	5	bucket 5 holds emu
4	owl	4	bucket 4 holds dog, owl
5	fox	7	bucket 7 holds fox

After five pairs the load factor is 5 / 8 = 0.625, and one bucket has a chain of two. Now the class. It has put, get, delete and a private _resize that the next section explains. Two counters, steps and moves, let us count work without a stopwatch.

pythonrunnable cell

class ChainedMap:
    """Hash table that resolves collisions with separate chaining."""

    def __init__(self, size=4, hash_fn=simple_hash):
        self.buckets = [[] for _ in range(size)]   # each bucket is a list of (key, value) pairs
        self.count = 0
        self.hash_fn = hash_fn
        self.steps = 0                             # pairs examined, so we can count work
        self.moves = 0                             # pairs re-placed by resizes

    def _index(self, key):
        return self.hash_fn(key) % len(self.buckets)

    def put(self, key, value):
        """Add a pair, or update the value if the key is already there."""
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            self.steps += 1
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1
        if self.count / len(self.buckets) > 0.75:  # load factor too high
            self._resize()

    def get(self, key, default=None):
        """Return the value for key, or default."""
        for k, v in self.buckets[self._index(key)]:
            self.steps += 1
            if k == key:
                return v
        return default

    def delete(self, key):
        """Remove key. Return True if it was there."""
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            self.steps += 1
            if k == key:
                del bucket[i]
                self.count -= 1
                return True
        return False

    def _resize(self):
        """Double the number of buckets and place every pair again."""
        old = self.buckets
        self.buckets = [[] for _ in range(2 * len(old))]
        for bucket in old:
            for key, value in bucket:
                self.buckets[self._index(key)].append((key, value))
                self.moves += 1

    def __len__(self):
        return self.count

Use it on the five words from the trace. The values are 0 to 4.

pythonrunnable cell

m = ChainedMap(size=8)
for i, word in enumerate(["cat", "dog", "emu", "owl", "fox"]):
    m.put(word, i)
for i, bucket in enumerate(m.buckets):
    print(i, bucket)
print(len(m), m.get("owl"), m.get("zebra", "missing"))
print(m.delete("dog"), m.delete("dog"), m.get("owl"), len(m))

Output:

0 []
1 []
2 []
3 []
4 [('dog', 1), ('owl', 3)]
5 [('emu', 2)]
6 [('cat', 0)]
7 [('fox', 4)]
5 3 missing
True False 3 4

The buckets match the hand trace: dog and owl share bucket 4. Deleting dog just removes one pair from a list, so chaining makes delete easy. The other plan does not.

put, get and delete each walk one chain. If the hash spreads keys evenly, the average chain length is the load factor, which the resize rule keeps below 0.75. So each is O(1) on average. In the worst case every key lands in one bucket and each operation is O(n). The table uses O(n) space: a pair for each key plus a list for each bucket.

Chaining: insert keys and watch where they landInteractive

Insert keys and watch each one become a hash, pick a bucket and join that bucket's chain. This lab has 8 buckets and never resizes, so its load factor can climb above 1. Our class above doubles the buckets before that happens.

Loading visualization...

#Load factor and resize: why doubling works

A table with 4 buckets and 100 pairs would have chains 25 long, and lookups would crawl. So when the load factor passes 0.75, put calls _resize. It makes a table with twice as many buckets and places every pair in it again.

It must place them again, not copy the buckets over. The index is hash % size, and the size just changed, so most pairs belong in a different bucket. Trace a table that starts with 4 buckets. Three pairs give 3 / 4 = 0.75, which is not above 0.75. The fourth gives 4 / 4 = 1.0, so the table doubles to 8 buckets and all four pairs are placed again.

pythonrunnable cell

m2 = ChainedMap(size=4)
for i, word in enumerate(words):
    m2.put(word, i)
    print(word, "pairs", m2.count, "buckets", len(m2.buckets), "moves so far", m2.moves)

Output:

cat pairs 1 buckets 4 moves so far 0
dog pairs 2 buckets 4 moves so far 0
emu pairs 3 buckets 4 moves so far 0
owl pairs 4 buckets 8 moves so far 4
fox pairs 5 buckets 8 moves so far 4
bee pairs 6 buckets 8 moves so far 4
ant pairs 7 buckets 16 moves so far 11
hen pairs 8 buckets 16 moves so far 11

One resize is O(n) time, and it needs O(n) extra space while the old and new tables both exist. But it happens rarely. The question is how rarely.

What Do You Think?

A map starts with 4 buckets and doubles whenever the load factor passes 0.75. You add 1,000 different keys one at a time. About how many pairs are moved by all the resizes together?

Count it instead of guessing. The function below builds no table. It only counts the pairs each resize moves, for two growth rules: double the size, or add 4 buckets.

pythonrunnable cell

def moves_for(n, grow):
    """Pairs moved by resizes while adding n keys; grow(size) gives the new size."""
    size, moves = 4, 0
    for count in range(1, n + 1):
        if count / size > 0.75:
            size = grow(size)
            moves += count
    return moves


for n in (1000, 4000, 16000):
    doubling = moves_for(n, lambda size: size * 2)
    adding = moves_for(n, lambda size: size + 4)
    print(n, "doubling:", doubling, round(doubling / n, 2), "per key", "| adding 4:", adding, round(adding / n), "per key")

real = ChainedMap()
for i in range(1000):
    real.put(f"key{i}", i)
print(real.moves, len(real.buckets))

Output:

1000 doubling: 1542 1.54 per key | adding 4: 167166 167 per key
4000 doubling: 6152 1.54 per key | adding 4: 2668666 667 per key
16000 doubling: 24586 1.54 per key | adding 4: 42674666 2667 per key
1542 2048

With doubling, the work per added key stays near 1.5 however large n gets. With a fixed step of 4, the work per key keeps growing, because a resize comes after every few keys and each one touches everything. The last line shows that the real class moved 1,542 pairs for 1,000 keys, the same as the counting function.

Here is why doubling wins. A resize happens when the table is three quarters full, and it moves every pair. So the moves go roughly 4, 7, 13, 25, 49, and each is about twice the one before. When every term is twice the last, the whole sum is less than twice the final term. The final term is no more than about n. So all the resizes together cost O(n), which is O(1) per put.

This kind of average is called amortized cost. One put in a thousand may be slow, but the average over a long run of puts is constant. So put is O(1) amortized, and get and delete are O(1) on average.

#Fix two: open addressing with linear probing

The other plan keeps everything in one flat table with no lists. In open addressing, a slot holds one pair or nothing, and a key whose home slot is taken goes to another slot. The simplest way to find one is linear probing: try the next slot, then the next, and wrap to slot 0 after the last. Each try is a probe.

To keep the trace short, use whole numbers as keys. A whole number is its own hash, so the home slot of key 11 in a table of 8 is 11 % 8 = 3. Put in the keys 3, 11, 19 and then 4. Keys 3, 11 and 19 all want slot 3.

Step	Key	Home slot	Slots tried	Lands in
1	3	3	3	slot 3
2	11	3	3, 4	slot 4
3	19	3	3, 4, 5	slot 5
4	4	4	4, 5, 6	slot 6

Key 4 has its own home slot, 4, but a stranger sits there. The three colliding keys formed a run of full slots, and key 4 ran into its edge. Long runs slow every key nearby. This is called clustering. Two small functions show the whole method.

pythonrunnable cell

def probe_put(slots, key, value):
    """Place a pair in the first free slot, starting at the key's home slot."""
    size = len(slots)
    i = key % size                  # the home slot
    while slots[i] is not None:     # taken: try the next slot
        i = (i + 1) % size          # % size wraps from the last slot to slot 0
    slots[i] = (key, value)
    return i


def probe_get(slots, key):
    """Return (value, slots looked at), or (None, slots looked at) if key is absent."""
    size = len(slots)
    i = key % size
    looked = 1
    while slots[i] is not None:     # an empty slot ends the search
        if slots[i][0] == key:
            return slots[i][1], looked
        i = (i + 1) % size
        looked += 1
    return None, looked


slots = [None] * 8
for key in (3, 11, 19, 4):
    print(key, "lands in slot", probe_put(slots, key, key * 10))
print(slots)
print(probe_get(slots, 19), probe_get(slots, 4), probe_get(slots, 27))

Output:

3 lands in slot 3
11 lands in slot 4
19 lands in slot 5
4 lands in slot 6
[None, None, None, (3, 30), (11, 110), (19, 190), (4, 40), None]
(190, 3) (40, 3) (None, 5)

These functions assume at least one slot is always empty. Without one the loop would never stop. The class below keeps that promise by resizing early.

Why can a lookup stop at an empty slot? When 19 was put in, it took the first free slot after its home. So if the walk reaches an empty slot before it finds 19, then 19 was never put in. The lookup for 27 shows this: it walks slots 3, 4, 5 and 6, finds slot 7 empty, and gives up after 5 looks.

Speed depends on how full the table is. For linear probing with a good hash, a known result says that at a load factor of 2/3, finding a key that is there takes about 2 probes on average and ruling out a missing one takes about 5. At a load factor of 0.9 a missing key takes about 50. So open addressing resizes earlier than chaining. The class below resizes at 2/3.

#Deleting with tombstones

Chaining made delete easy. Open addressing makes it tricky. Try the obvious thing, which is to delete key 11 by blanking its slot.

What Do You Think?

The table holds 3, 11, 19 and 4 as in the trace. You delete key 11 by setting its slot back to None. What does probe_get(slots, 19) return?

pythonrunnable cell

broken = list(slots)                       # a copy of the table from the last cell
broken[broken.index((11, 110))] = None     # "delete" key 11 by blanking its slot
print(broken)
print(probe_get(broken, 19))

Output:

[None, None, None, (3, 30), None, (19, 190), (4, 40), None]
(None, 2)

Key 19 is still in slot 5, but nothing can find it. The empty slot broke the run. The fix is to leave a marker. A tombstone is a special value that means "a pair was here and was deleted". It changes four rules:

A lookup walks past a tombstone and keeps going, because the key may be further along.
A put may reuse the first tombstone it passes, but only after the walk shows the key is not already stored.
A tombstone counts as a used slot when we decide to resize, because it still lengthens runs.
A resize drops tombstones, because only live pairs are placed again.

Here is the full class with all four rules. It has the same methods as ChainedMap.

pythonrunnable cell

TOMBSTONE = "<deleted>"


class ProbingMap:
    """Hash table with open addressing and linear probing."""

    def __init__(self, size=8, hash_fn=simple_hash):
        self.slots = [None] * size          # None = never used, TOMBSTONE = deleted
        self.count = 0                      # live pairs
        self.filled = 0                     # live pairs plus tombstones
        self.hash_fn = hash_fn
        self.steps = 0

    def _start(self, key):
        return self.hash_fn(key) % len(self.slots)

    def _find(self, key):
        """Return the slot number holding key, or None."""
        size = len(self.slots)
        for step in range(size):
            i = (self._start(key) + step) % size
            slot = self.slots[i]
            self.steps += 1
            if slot is None:                # a never-used slot ends the search
                return None
            if slot is not TOMBSTONE and slot[0] == key:
                return i
        return None

    def put(self, key, value):
        """Add a pair, or update the value if the key is already there."""
        size = len(self.slots)
        first_free = None                   # the first tombstone we walk past
        for step in range(size):
            i = (self._start(key) + step) % size
            slot = self.slots[i]
            self.steps += 1
            if slot is None:
                if first_free is None:
                    first_free = i
                    self.filled += 1        # a never-used slot is now used
                break
            if slot is TOMBSTONE:
                if first_free is None:
                    first_free = i          # remember it, but keep looking for the key
            elif slot[0] == key:
                self.slots[i] = (key, value)
                return
        self.slots[first_free] = (key, value)
        self.count += 1
        if self.filled / size > 2 / 3:
            self._resize()

    def get(self, key, default=None):
        """Return the value for key, or default."""
        i = self._find(key)
        return default if i is None else self.slots[i][1]

    def delete(self, key):
        """Remove key by leaving a tombstone. Return True if it was there."""
        i = self._find(key)
        if i is None:
            return False
        self.slots[i] = TOMBSTONE
        self.count -= 1
        return True

    def _resize(self):
        """Rebuild the table. Tombstones are dropped, so the new table is clean."""
        old = self.slots
        grow = self.count * 3 >= len(old)   # mostly tombstones? rebuild at the same size
        self.slots = [None] * (len(old) * 2 if grow else len(old))
        self.count = 0
        self.filled = 0
        for slot in old:
            if slot is not None and slot is not TOMBSTONE:
                self.put(*slot)

    def __len__(self):
        return self.count

Run the same four keys through it, delete 11, and look at the table.

pythonrunnable cell

t = ProbingMap(hash_fn=hash)              # whole numbers hash to themselves
for key in (3, 11, 19, 4):
    t.put(key, key * 10)
print(t.slots)
print(t.delete(11), t.slots)
print(t.get(19), t.get(4), len(t))
t.put(27, 270)                            # 27 starts at slot 3 and reuses the tombstone
print(t.slots, len(t))

Output:

[None, None, None, (3, 30), (11, 110), (19, 190), (4, 40), None]
True [None, None, None, (3, 30), '<deleted>', (19, 190), (4, 40), None]
190 40 3
[None, None, None, (3, 30), (27, 270), (19, 190), (4, 40), None] 4

Now 19 is found, because the lookup walks past the tombstone. Putting 27 then reuses the tombstone's slot. One more test: add and delete a thousand keys one at a time, so there is never more than one live pair.

pythonrunnable cell

churn = ProbingMap(hash_fn=hash)
for i in range(1000):
    churn.put(i, i)
    churn.delete(i)
print(len(churn.slots), len(churn))

Output:

8 0

The table stayed at 8 slots. Tombstones piled up, the fill count passed 2/3, and _resize rebuilt the table at the same size, because few pairs were live. Without that rule the table would double again and again for nothing.

The costs match chaining. put, get and delete are O(1) on average while the load factor stays below 2/3, and O(n) in the worst case, when one run of full slots covers the table. A resize is O(n) time. The table uses O(n) space, because its slots stay within a small multiple of its pairs. Since resizes double the table, put is O(1) amortized by the same argument as before.

#Bad hash functions and the O(n) worst case

Everything above assumed the hash function spreads keys out. Break that and see what happens. The cell builds a chained map with three hash functions and counts how many pairs it looks at to find all n keys. The first is our simple_hash. The second uses only the length of the text. The third gives every key the hash 0.

pythonrunnable cell

def constant_hash(key):
    return 0


def lookup_cost(hash_fn, n):
    """Pairs examined to look up every one of n keys."""
    m = ChainedMap(hash_fn=hash_fn)
    for i in range(n):
        m.put(f"key{i}", i)
    m.steps = 0
    for i in range(n):
        m.get(f"key{i}")
    return m.steps


print("n, simple_hash, length only, constant")
for n in (100, 200, 400):
    print(n, lookup_cost(simple_hash, n), lookup_cost(len, n), lookup_cost(constant_hash, n))

Output:

n, simple_hash, length only, constant
100 107 4150 5050
200 222 9200 20100
400 597 49300 80200

With simple_hash, a lookup looks at only a pair or two. With the length-only hash, the keys fall into just three buckets (their lengths are 4, 5 and 6), so every chain is long. With the constant hash the table is one long list, and doubling n multiplies the cost by 4: 5,050, then 20,100, then 80,200. That is O(n) for each lookup and O(n²) to look up all n keys.

So O(1) is only an average, and it rests on the hash spreading keys out. Python gives the hashes of str and bytes keys a random starting value on each run, so nobody can plan text keys that all collide. Whole-number keys are not randomized. On a 64-bit build, hash(1) and hash(2**61) are both 1, so a program that accepts whole-number keys from strangers can be slowed on purpose.

#What CPython does differently

A real Python dict follows the same idea with three differences.

It does not probe linearly, because that grows runs. It keeps a number called perturb, which starts as the full hash. Each probe shifts perturb right by 5 bits and moves to slot (5 * slot + perturb + 1) % size. Two keys with the same home slot soon follow different paths. This cell gives the paths for four hashes that share home slot 3 in a table of 8.

pythonrunnable cell

def cpython_probe_order(hash_value, size, how_many):
    """The slots CPython tries for one hash, in order (for small positive hashes)."""
    mask = size - 1
    perturb = hash_value
    i = hash_value & mask                  # same as hash_value % size when size is a power of two
    order = [i]
    while len(order) < how_many:
        perturb >>= 5
        i = (i * 5 + perturb + 1) & mask
        order.append(i)
    return order


taken = {}
for h in (3, 35, 67, 99):                  # all four have home slot 3 in a table of 8
    order = cpython_probe_order(h, 8, 6)
    print(h, order)
    for slot in order:
        if slot not in taken:
            taken[slot] = h
            break
print(sorted(taken.items()))

Output:

3 [3, 0, 1, 6, 7, 4]
35 [3, 1, 6, 7, 4, 5]
67 [3, 2, 3, 0, 1, 6]
99 [3, 3, 0, 1, 6, 7]
[(0, 99), (1, 35), (2, 67), (3, 3)]

The keys end up in slots 3, 1, 2 and 0, all different, and these placements match a real CPython 3.12 dict. Linear probing would have packed them into slots 3, 4, 5 and 6.

It stores pairs in a compact way. Since Python 3.6 (a language rule since 3.7), a dict keeps two arrays. The first is a table of small numbers. Each is either empty or the position of a pair in the second array. The second array holds the pairs in the order they were added, each with its stored hash. For {3: "a", 35: "b", 67: "c", 99: "d"} the real arrays on CPython 3.12 are:

indices: [3, 1, 2, 0, -1, -1, -1, -1]      (-1 means empty)
entries: [(3, "a"), (35, "b"), (67, "c"), (99, "d")]

Slot 0 points to entry 3, which is key 99, and so on. Empty slots cost only a small number, which saves memory, and the entries array is why a dict remembers insertion order. The stored hash also means a resize never calls __hash__ again. Deleting leaves a marker in the indices, the same idea as a tombstone.

It resizes when about two thirds of the slots are used, and it picks the smallest power of two that is at least three times the number of pairs. The cell finds the sizes at which a growing dict gets a bigger table.

pythonrunnable cell

import sys

d = {}
previous = sys.getsizeof(d)
grew_at = []
for i in range(1, 51):
    d[i] = i
    size = sys.getsizeof(d)
    if size != previous:
        grew_at.append(i)
        previous = size
print(grew_at)

Output:

[1, 6, 11, 22, 43]

The first jump, at insert 1, is the first table. The next jumps come at the 6th, 11th, 22nd and 43rd keys: an 8-slot table holds 5 pairs, then 16 slots hold 10, 32 hold 21, and 64 hold 42. The animation below uses the same probe and the 2/3 rule. Choose preset B, Collisions, and step through it. Then choose preset C and watch the table double when the 6th key arrives.

CPython-style probing: collisions and resize at 2/3 fullInteractive

Each key hashes to a first slot. When that slot is taken, the key probes onward using the perturbation rule above. When the table passes 2/3 full, it doubles and every entry is placed again.

Loading visualization...

Sets use the same ideas without values, in their own code with their own thresholds. A set costs the same as a dict: O(1) on average, O(n) in the worst case, and O(1) amortized to add. The picture you built, a hash, a slot, a probe and a resize, is the real one.

#Your own class as a key

A dict key needs a hash, and two keys that are equal must have the same hash. Python's numbers, strings and tuples of them already follow this. For your own class, you write __eq__ and __hash__ yourself.

pythonrunnable cell

class Point:
    """A point on a grid. We promise not to change x or y after creation."""

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        if not isinstance(other, Point):
            return NotImplemented
        return (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        return hash((self.x, self.y))      # hash the same fields that __eq__ compares

    def __repr__(self):
        return f"Point({self.x}, {self.y})"


visited = {Point(2, 3): "start"}
print(visited[Point(2, 3)])                # a different object with the same data
print(Point(2, 3) == Point(2, 3), Point(2, 3) is Point(2, 3))


class NoHash:
    def __init__(self, n):
        self.n = n

    def __eq__(self, other):
        return self.n == other.n


try:
    {NoHash(1): "x"}
except TypeError as error:
    print(error)

Output:

start
True False
unhashable type: 'NoHash'

A lookup works out a place from the hash and then compares keys with ==. If two equal keys had different hashes, the lookup would go to the wrong place and miss. When you define __eq__ and not __hash__, Python removes the hash on purpose, so the class cannot be a key by mistake.

#Sets are dicts without values

A set holds keys and no values. You can build one from the chained map by storing True for each key and ignoring it.

pythonrunnable cell

class HashSet:
    """A set: a hash map that keeps the keys and ignores the values."""

    def __init__(self, items=()):
        self._map = ChainedMap()
        for item in items:
            self.add(item)

    def add(self, item):
        self._map.put(item, True)

    def discard(self, item):
        self._map.delete(item)

    def __contains__(self, item):
        return self._map.get(item, False)

    def __len__(self):
        return len(self._map)


animals = ["cat", "dog", "cat", "emu", "dog", "cat"]
s = HashSet(animals)
print(len(s), "cat" in s, "owl" in s)
s.discard("cat")
print(len(s), "cat" in s)
print(len(set(animals)))

Output:

3 True False
2 False
3

Adding a key that is already there changes nothing, so duplicates disappear. That is why set(items) removes duplicates in O(n) time: each item costs one O(1) average add. Membership x in s is O(1) on average, where x in a_list is O(n). The set takes O(n) space. It keeps no order and no values.

#Dict, set or sorted list?

Choose by the question you will ask most often.

You need to	dict	set	sorted list with bisect
Find the value for a key	O(1) average	not offered	O(log n) to find the position
Ask "is x there?"	O(1) average	O(1) average	O(log n)
Add one item	O(1) amortized	O(1) amortized	O(n), later items shift
Get the smallest or largest	O(n)	O(n)	O(1) at the two ends
List everything between two keys	O(n)	O(n)	O(log n + k) for k results
Memory	high, spare slots	high, spare slots	low

A hash table cannot answer "what comes next after this key?", because hashing throws the order away. A sorted list can. This cell finds every name from "d" up to but not including "h", then adds one more.

pythonrunnable cell

from bisect import bisect_left, insort

names = sorted(["pear", "fig", "apple", "kiwi", "date", "grape", "cherry"])
low, high = bisect_left(names, "d"), bisect_left(names, "h")
print(names[low:high])
insort(names, "banana")
print(names)
print(names[0], names[-1])

Output:

['date', 'fig', 'grape']
['apple', 'banana', 'cherry', 'date', 'fig', 'grape', 'kiwi', 'pear']
apple pear

bisect_left finds a position in O(log n) steps, and slicing out the results costs one step per result. insort finds the spot in O(log n) but then shifts later items to make room, which is O(n).

A hash table is the wrong choice when you need order or ranges, when you need the smallest item, when the keys cannot be hashed (a list cannot be a key, so use a tuple), and when n is tiny. For ten items, a plain list scan is as fast and simpler.

#Where hashing shows up in ML

A word-count Counter, a vocabulary that maps each word to a number, and a cache of finished results are all dicts. Machine learning adds one more use, the hashing trick. A model needs a number for each word, but a vocabulary of every word ever seen is huge. Instead, hash each word to a slot in a fixed-size vector and count there. Collisions are accepted.

pythonrunnable cell

def hash_features(tokens, n_features=8):
    """Count tokens into a fixed-size vector, with no vocabulary to store."""
    counts = [0] * n_features
    for token in tokens:
        counts[simple_hash(token) % n_features] += 1
    return counts


print(hash_features(words))

Output:

[0, 1, 1, 0, 2, 1, 1, 2]

Eight words fell into 8 slots, and slots 4 and 7 each caught two words. This is the collision table again, used on purpose. It trades a little accuracy for no stored vocabulary and a fixed size.

#Common mistakes

Watch Out

Mutating a key after it is stored

Fix: Use keys that cannot change: numbers, strings, tuples, or a class you promise not to modify. If the data must change, remove the pair first and put it back.

pythonrunnable cell

class Cell:
    def __init__(self, row, col):
        self.row = row
        self.col = col


def cell_hash(cell):
    return cell.row * 10 + cell.col


m3 = ChainedMap(hash_fn=cell_hash)
c = Cell(2, 3)
m3.put(c, "start")                 # stored by hash 23, in bucket 23 % 4 = 3
c.row = 9                          # the key changes: hash 93, bucket 93 % 4 = 1
print(m3.get(c), len(m3))
print([i for i, bucket in enumerate(m3.buckets) if bucket])

Output:

None 1
[3]

A key's place comes from its hash when it was stored. The pair is still in bucket 3, but the changed key now asks bucket 1. The length is 1, yet get returns None.

Watch Out

Resizing without placing every pair again

Fix: After the table grows, work out the index for every pair again. The index depends on the size, so a pair from old bucket 3 may belong in new bucket 11.

pythonrunnable cell

class LazyResizeMap(ChainedMap):
    def _resize(self):
        # BUG: add empty buckets, but leave every pair where it was
        self.buckets = self.buckets + [[] for _ in range(len(self.buckets))]


lazy = LazyResizeMap()
for i, word in enumerate(["cat", "dog", "emu", "owl"]):
    lazy.put(word, i)
print(len(lazy.buckets), [lazy.get(w, "lost") for w in ["cat", "dog", "emu", "owl"]])

Output:

8 ['lost', 'lost', 'lost', 'lost']

The table has 8 buckets, but the four pairs were placed when the size was 4. Every lookup now uses the new size, looks in a bucket where its pair is not, and misses.

#Try it

Five problems, easiest first. The starter has working helper code and five stubs. Do them in order, because each rung uses ideas from the one before. Run the cell after each rung and compare with the Expected lines. The rungs are: the slot for a word, counting collisions, finishing delete for a chained table, fixing a lookup that loses keys, and making a slow pair search fast.

pythonplayground.py · Pyodide

def simple_hash(text):
  total = 0
  for ch in text:
      total = total * 31 + ord(ch)
  return total

words = ["cat", "dog", "emu", "owl", "fox", "bee", "ant", "hen"]

# Rung 1: the slot number for a word in a table with size slots.
def index_for(word, size):
  # TODO: return the hash of the word, reduced to a slot number
  pass

# Rung 2: how many words land in a slot that an earlier word already took?
def count_collisions(words, size):
  # TODO: go through the words in order and count the collisions
  pass

# Rung 3: finish delete for this chained table.
class MiniChained:
  def __init__(self, size=8):
      self.buckets = [[] for _ in range(size)]

def put(self, key, value):
      bucket = self.buckets[simple_hash(key) % len(self.buckets)]
      for i, (k, _) in enumerate(bucket):
          if k == key:
              bucket[i] = (key, value)
              return
      bucket.append((key, value))

def get(self, key):
      for k, v in self.buckets[simple_hash(key) % len(self.buckets)]:
          if k == key:
              return v
      return None

def delete(self, key):
      # TODO: find key in its bucket, remove the pair and return True,
      # or return False if the key is not there
      pass

# Rung 4: this linear-probing table loses keys after a delete. Fix _find.
TOMBSTONE = "<deleted>"

class MiniProbing:
  def __init__(self, size=8):
      self.slots = [None] * size

def _find(self, key):
      size = len(self.slots)
      start = simple_hash(key) % size
      for step in range(size):
          i = (start + step) % size
          slot = self.slots[i]
          if slot is None or slot is TOMBSTONE:  # BUG: find it and fix it
              return None
          if slot is not TOMBSTONE and slot[0] == key:
              return i
      return None

def put(self, key, value):
      i = self._find(key)
      if i is not None:
          self.slots[i] = (key, value)
          return
      size = len(self.slots)
      start = simple_hash(key) % size
      for step in range(size):
          i = (start + step) % size
          if self.slots[i] is None or self.slots[i] is TOMBSTONE:
              self.slots[i] = (key, value)
              return

def get(self, key):
      i = self._find(key)
      return None if i is None else self.slots[i][1]

def delete(self, key):
      i = self._find(key)
      if i is not None:
          self.slots[i] = TOMBSTONE

# Rung 5: find two numbers that add up to the target, and return their positions.
# two_sum_slow works but tries every pair. Write two_sum so that it does one pass.
def two_sum_slow(nums, target):
  """O(n²) time, O(1) space: try every pair."""
  for i in range(len(nums)):
      for j in range(i + 1, len(nums)):
          if nums[i] + nums[j] == target:
              return [i, j]
  return None

def two_sum(nums, target):
  """Same answer as two_sum_slow, but in one pass over nums."""
  # TODO: one pass, using a dict. Then fix the docstring if you change your mind.
  pass

# Run after each rung. Compare with the Expected lines.
print([index_for(w, 8) for w in words])
# Expected: [6, 4, 5, 4, 7, 2, 7, 1]
print(count_collisions(words, 8), count_collisions(words, 16), count_collisions(words, 64))
# Expected: 2 0 0

t = MiniChained()
for key, value in (("dog", 1), ("owl", 2), ("cat", 3)):
  t.put(key, value)
print(t.delete("dog"), t.delete("dog"), t.get("owl"), t.get("dog"))
# Expected: True False 2 None

q = MiniProbing()
for key in ("dog", "owl", "emu"):
  q.put(key, key.upper())
q.delete("owl")
print(q.get("emu"), q.get("owl"))
# Expected: EMU None

print(two_sum([2, 7, 11, 15], 9), two_sum([3, 2, 4], 6), two_sum([3, 3], 6), two_sum([1, 2], 10))
# Expected: [0, 1] [1, 2] [0, 1] None

Tests · Rung 1 prints [6, 4, 5, 4, 7, 2, 7, 1]. Rung 2 prints 2 0 0. Rung 3 prints True False 2 None. Rung 4 prints EMU None. Rung 5 prints [0, 1] [1, 2] [0, 1] None and does one pass over the numbers.

Hints: in rung 4, ask what a lookup should do on a tombstone that it must not do on an empty slot. In rung 5, for each number work out which partner would finish the sum, and keep the numbers already seen in a dict. The slow version is O(n²) time and O(1) space. The dict version is O(n) time and O(n) space, because it trades memory for speed.

#Recap

A hash table is a list plus a rule. A hash function turns a key into a whole number, the same number every time, and index = hash % size turns it into a place. Two keys can land on one place, which is a collision.

Chaining keeps a list in each bucket, so delete is easy. Open addressing keeps one pair in each slot and probes on, so delete must leave a tombstone, or a lookup stops too early.

Both are O(1) on average and O(n) in the worst case. Doubling the table when its load factor passes a limit gives O(1) amortized puts, because the resizes add up to less than twice n. A fixed step does not. A bad hash, such as a constant, makes every operation O(n).

CPython uses open addressing with a perturbed probe, a compact pair of arrays and a 2/3 limit. A set is a dict without values. Use a dict for key to value, a set for membership, and a sorted list when order or ranges matter.

Quick Check1 / 6

A key hashes to 101,583. Which bucket does it use in a table of 8 buckets, and which in a table of 16?

Recap

Key Takeaways

A hash function turns a key into a whole number, the same number every time, and index = hash % size turns it into a place in the table
Two keys can share a place, which is a collision, and no hash function can prevent them once keys outnumber slots
Separate chaining keeps a list in each bucket, so delete just removes a pair from a list
Open addressing keeps one pair per slot and probes on, so delete must leave a tombstone or lookups stop too early
Doubling the table when it fills gives O(1) amortized puts, because the resizes add up to less than twice n
A bad hash function, such as a constant, makes every operation O(n), so O(1) is only an average
CPython's dict uses open addressing with a perturbed probe and a 2/3 limit, and a set is a dict without values

Build a Hash Table

Learning Objectives

After this lesson, you will be able to:

Explain what a hash function is, and work out the slot for a key with index = hash % size
Say what a collision is, and why collisions cannot be avoided once keys outnumber slots
Build a hash table with separate chaining: put, get, delete and resize
Build a hash table with linear probing, and explain why delete must leave a tombstone
Show by counting why doubling the table gives amortized O(1) puts, and why growing by a fixed step does not
Show how a bad hash function turns O(1) into O(n)
Describe how CPython's dict differs, and choose between a dict, a set and a sorted list for a job

Prerequisites

Before You Start

Review

#A dict is a magic box, until you build one

Start with a guess about the claim that makes dicts famous.

What Do You Think?

A dict holds 1,000,000 pairs. You look up one key. About how many stored keys does Python compare with yours before it finds the right pair?

Every code cell runs in order, so later cells reuse the names from earlier ones.

#From a key to a slot

The rule has two parts. A hash function makes a whole number from the key, and then we shrink that number to a place in the table. A good hash function follows three rules:

The same key always gives the same number. If it did not, a lookup could never find where the pair was stored.
Different keys should give very different numbers, so the pairs spread out.
It should be quick, because it runs on every lookup.

Here is a small one for text. It walks over the letters. For each letter it multiplies the running total by 31 and adds the letter's code number, which ord gives.

pythonrunnable cell

def simple_hash(text):
    """Turn text into a whole number. The same text always gives the same number."""
    total = 0
    for ch in text:
        total = total * 31 + ord(ch)
    return total


print(simple_hash("cat"), simple_hash("cat"))
print(simple_hash("act"))

Output:

98262 98262
96402

Trace "cat" by hand before trusting the code. The letter codes are 99 for c, 97 for a and 116 for t.

Letter	Code	Running total before	Running total after
c	99	0	0 x 31 + 99 = 99
a	97	99	99 x 31 + 97 = 3,166
t	116	3,166	3,166 x 31 + 116 = 98,262

The multiply by 31 makes the order of the letters matter, so "cat" and "act" get different numbers.

Now the second part. A hash like 98,262 is far too big for a table of 8 slots, so we take the remainder after dividing by the table size. In Python that is the % operator.

index = hash % size

The remainder is always from 0 to size - 1, so it is always a real place. For "cat": 98,262 = 8 x 12,282 + 6, so the index is 6. The cell does this for eight animal names.

pythonrunnable cell

words = ["cat", "dog", "emu", "owl", "fox", "bee", "ant", "hen"]
for word in words:
    h = simple_hash(word)
    print(word, h, h % 8)

Output:

cat 98262 6
dog 99644 4
emu 100557 5
owl 110468 4
fox 101583 7
bee 97410 2
ant 96743 7
hen 103185 1

What Do You Think?

The hash of the word dog is 99,644. The table has 16 slots. Which slot does dog go to?

#Collisions: two keys, one slot

In the output above, dog and owl both land on slot 4, and fox and ant both land on slot 7. A careless table would just write each word into its slot:

pythonrunnable cell

table = [None] * 8
for word in words:
    table[simple_hash(word) % 8] = word
print(table)
print(len([w for w in table if w]), "of", len(words), "words survived")

Output:

[None, 'hen', 'bee', None, 'owl', 'emu', 'cat', 'ant']
6 of 8 words survived

#Fix one: separate chaining

One word before the code. The load factor is the number of pairs divided by the number of buckets. It is also the average length of a chain. Trace five words into 8 buckets by hand.

Step	Key	Hash % 8	Bucket after the step
1	cat	6	bucket 6 holds cat
2	dog	4	bucket 4 holds dog
3	emu	5	bucket 5 holds emu
4	owl	4	bucket 4 holds dog, owl
5	fox	7	bucket 7 holds fox

pythonrunnable cell

class ChainedMap:
    """Hash table that resolves collisions with separate chaining."""

    def __init__(self, size=4, hash_fn=simple_hash):
        self.buckets = [[] for _ in range(size)]   # each bucket is a list of (key, value) pairs
        self.count = 0
        self.hash_fn = hash_fn
        self.steps = 0                             # pairs examined, so we can count work
        self.moves = 0                             # pairs re-placed by resizes

    def _index(self, key):
        return self.hash_fn(key) % len(self.buckets)

    def put(self, key, value):
        """Add a pair, or update the value if the key is already there."""
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            self.steps += 1
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.count += 1
        if self.count / len(self.buckets) > 0.75:  # load factor too high
            self._resize()

    def get(self, key, default=None):
        """Return the value for key, or default."""
        for k, v in self.buckets[self._index(key)]:
            self.steps += 1
            if k == key:
                return v
        return default

    def delete(self, key):
        """Remove key. Return True if it was there."""
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            self.steps += 1
            if k == key:
                del bucket[i]
                self.count -= 1
                return True
        return False

    def _resize(self):
        """Double the number of buckets and place every pair again."""
        old = self.buckets
        self.buckets = [[] for _ in range(2 * len(old))]
        for bucket in old:
            for key, value in bucket:
                self.buckets[self._index(key)].append((key, value))
                self.moves += 1

    def __len__(self):
        return self.count

Use it on the five words from the trace. The values are 0 to 4.

pythonrunnable cell

m = ChainedMap(size=8)
for i, word in enumerate(["cat", "dog", "emu", "owl", "fox"]):
    m.put(word, i)
for i, bucket in enumerate(m.buckets):
    print(i, bucket)
print(len(m), m.get("owl"), m.get("zebra", "missing"))
print(m.delete("dog"), m.delete("dog"), m.get("owl"), len(m))

Output:

0 []
1 []
2 []
3 []
4 [('dog', 1), ('owl', 3)]
5 [('emu', 2)]
6 [('cat', 0)]
7 [('fox', 4)]
5 3 missing
True False 3 4

The buckets match the hand trace: dog and owl share bucket 4. Deleting dog just removes one pair from a list, so chaining makes delete easy. The other plan does not.

Chaining: insert keys and watch where they landInteractive

Loading visualization...

#Load factor and resize: why doubling works

pythonrunnable cell

m2 = ChainedMap(size=4)
for i, word in enumerate(words):
    m2.put(word, i)
    print(word, "pairs", m2.count, "buckets", len(m2.buckets), "moves so far", m2.moves)

Output:

cat pairs 1 buckets 4 moves so far 0
dog pairs 2 buckets 4 moves so far 0
emu pairs 3 buckets 4 moves so far 0
owl pairs 4 buckets 8 moves so far 4
fox pairs 5 buckets 8 moves so far 4
bee pairs 6 buckets 8 moves so far 4
ant pairs 7 buckets 16 moves so far 11
hen pairs 8 buckets 16 moves so far 11

One resize is O(n) time, and it needs O(n) extra space while the old and new tables both exist. But it happens rarely. The question is how rarely.

What Do You Think?

A map starts with 4 buckets and doubles whenever the load factor passes 0.75. You add 1,000 different keys one at a time. About how many pairs are moved by all the resizes together?

Count it instead of guessing. The function below builds no table. It only counts the pairs each resize moves, for two growth rules: double the size, or add 4 buckets.

pythonrunnable cell

def moves_for(n, grow):
    """Pairs moved by resizes while adding n keys; grow(size) gives the new size."""
    size, moves = 4, 0
    for count in range(1, n + 1):
        if count / size > 0.75:
            size = grow(size)
            moves += count
    return moves


for n in (1000, 4000, 16000):
    doubling = moves_for(n, lambda size: size * 2)
    adding = moves_for(n, lambda size: size + 4)
    print(n, "doubling:", doubling, round(doubling / n, 2), "per key", "| adding 4:", adding, round(adding / n), "per key")

real = ChainedMap()
for i in range(1000):
    real.put(f"key{i}", i)
print(real.moves, len(real.buckets))

Output:

1000 doubling: 1542 1.54 per key | adding 4: 167166 167 per key
4000 doubling: 6152 1.54 per key | adding 4: 2668666 667 per key
16000 doubling: 24586 1.54 per key | adding 4: 42674666 2667 per key
1542 2048

#Fix two: open addressing with linear probing

Step	Key	Home slot	Slots tried	Lands in
1	3	3	3	slot 3
2	11	3	3, 4	slot 4
3	19	3	3, 4, 5	slot 5
4	4	4	4, 5, 6	slot 6

pythonrunnable cell

def probe_put(slots, key, value):
    """Place a pair in the first free slot, starting at the key's home slot."""
    size = len(slots)
    i = key % size                  # the home slot
    while slots[i] is not None:     # taken: try the next slot
        i = (i + 1) % size          # % size wraps from the last slot to slot 0
    slots[i] = (key, value)
    return i


def probe_get(slots, key):
    """Return (value, slots looked at), or (None, slots looked at) if key is absent."""
    size = len(slots)
    i = key % size
    looked = 1
    while slots[i] is not None:     # an empty slot ends the search
        if slots[i][0] == key:
            return slots[i][1], looked
        i = (i + 1) % size
        looked += 1
    return None, looked


slots = [None] * 8
for key in (3, 11, 19, 4):
    print(key, "lands in slot", probe_put(slots, key, key * 10))
print(slots)
print(probe_get(slots, 19), probe_get(slots, 4), probe_get(slots, 27))

Output:

3 lands in slot 3
11 lands in slot 4
19 lands in slot 5
4 lands in slot 6
[None, None, None, (3, 30), (11, 110), (19, 190), (4, 40), None]
(190, 3) (40, 3) (None, 5)

These functions assume at least one slot is always empty. Without one the loop would never stop. The class below keeps that promise by resizing early.

#Deleting with tombstones

Chaining made delete easy. Open addressing makes it tricky. Try the obvious thing, which is to delete key 11 by blanking its slot.

What Do You Think?

The table holds 3, 11, 19 and 4 as in the trace. You delete key 11 by setting its slot back to None. What does probe_get(slots, 19) return?

pythonrunnable cell

broken = list(slots)                       # a copy of the table from the last cell
broken[broken.index((11, 110))] = None     # "delete" key 11 by blanking its slot
print(broken)
print(probe_get(broken, 19))

Output:

[None, None, None, (3, 30), None, (19, 190), (4, 40), None]
(None, 2)

A lookup walks past a tombstone and keeps going, because the key may be further along.
A put may reuse the first tombstone it passes, but only after the walk shows the key is not already stored.
A tombstone counts as a used slot when we decide to resize, because it still lengthens runs.
A resize drops tombstones, because only live pairs are placed again.

Here is the full class with all four rules. It has the same methods as ChainedMap.

pythonrunnable cell

TOMBSTONE = "<deleted>"


class ProbingMap:
    """Hash table with open addressing and linear probing."""

    def __init__(self, size=8, hash_fn=simple_hash):
        self.slots = [None] * size          # None = never used, TOMBSTONE = deleted
        self.count = 0                      # live pairs
        self.filled = 0                     # live pairs plus tombstones
        self.hash_fn = hash_fn
        self.steps = 0

    def _start(self, key):
        return self.hash_fn(key) % len(self.slots)

    def _find(self, key):
        """Return the slot number holding key, or None."""
        size = len(self.slots)
        for step in range(size):
            i = (self._start(key) + step) % size
            slot = self.slots[i]
            self.steps += 1
            if slot is None:                # a never-used slot ends the search
                return None
            if slot is not TOMBSTONE and slot[0] == key:
                return i
        return None

    def put(self, key, value):
        """Add a pair, or update the value if the key is already there."""
        size = len(self.slots)
        first_free = None                   # the first tombstone we walk past
        for step in range(size):
            i = (self._start(key) + step) % size
            slot = self.slots[i]
            self.steps += 1
            if slot is None:
                if first_free is None:
                    first_free = i
                    self.filled += 1        # a never-used slot is now used
                break
            if slot is TOMBSTONE:
                if first_free is None:
                    first_free = i          # remember it, but keep looking for the key
            elif slot[0] == key:
                self.slots[i] = (key, value)
                return
        self.slots[first_free] = (key, value)
        self.count += 1
        if self.filled / size > 2 / 3:
            self._resize()

    def get(self, key, default=None):
        """Return the value for key, or default."""
        i = self._find(key)
        return default if i is None else self.slots[i][1]

    def delete(self, key):
        """Remove key by leaving a tombstone. Return True if it was there."""
        i = self._find(key)
        if i is None:
            return False
        self.slots[i] = TOMBSTONE
        self.count -= 1
        return True

    def _resize(self):
        """Rebuild the table. Tombstones are dropped, so the new table is clean."""
        old = self.slots
        grow = self.count * 3 >= len(old)   # mostly tombstones? rebuild at the same size
        self.slots = [None] * (len(old) * 2 if grow else len(old))
        self.count = 0
        self.filled = 0
        for slot in old:
            if slot is not None and slot is not TOMBSTONE:
                self.put(*slot)

    def __len__(self):
        return self.count

Run the same four keys through it, delete 11, and look at the table.

pythonrunnable cell

t = ProbingMap(hash_fn=hash)              # whole numbers hash to themselves
for key in (3, 11, 19, 4):
    t.put(key, key * 10)
print(t.slots)
print(t.delete(11), t.slots)
print(t.get(19), t.get(4), len(t))
t.put(27, 270)                            # 27 starts at slot 3 and reuses the tombstone
print(t.slots, len(t))

Output:

[None, None, None, (3, 30), (11, 110), (19, 190), (4, 40), None]
True [None, None, None, (3, 30), '<deleted>', (19, 190), (4, 40), None]
190 40 3
[None, None, None, (3, 30), (27, 270), (19, 190), (4, 40), None] 4

pythonrunnable cell

churn = ProbingMap(hash_fn=hash)
for i in range(1000):
    churn.put(i, i)
    churn.delete(i)
print(len(churn.slots), len(churn))

Output:

8 0

#Bad hash functions and the O(n) worst case

pythonrunnable cell

def constant_hash(key):
    return 0


def lookup_cost(hash_fn, n):
    """Pairs examined to look up every one of n keys."""
    m = ChainedMap(hash_fn=hash_fn)
    for i in range(n):
        m.put(f"key{i}", i)
    m.steps = 0
    for i in range(n):
        m.get(f"key{i}")
    return m.steps


print("n, simple_hash, length only, constant")
for n in (100, 200, 400):
    print(n, lookup_cost(simple_hash, n), lookup_cost(len, n), lookup_cost(constant_hash, n))

Output:

n, simple_hash, length only, constant
100 107 4150 5050
200 222 9200 20100
400 597 49300 80200

#What CPython does differently

A real Python dict follows the same idea with three differences.

pythonrunnable cell

def cpython_probe_order(hash_value, size, how_many):
    """The slots CPython tries for one hash, in order (for small positive hashes)."""
    mask = size - 1
    perturb = hash_value
    i = hash_value & mask                  # same as hash_value % size when size is a power of two
    order = [i]
    while len(order) < how_many:
        perturb >>= 5
        i = (i * 5 + perturb + 1) & mask
        order.append(i)
    return order


taken = {}
for h in (3, 35, 67, 99):                  # all four have home slot 3 in a table of 8
    order = cpython_probe_order(h, 8, 6)
    print(h, order)
    for slot in order:
        if slot not in taken:
            taken[slot] = h
            break
print(sorted(taken.items()))

Output:

3 [3, 0, 1, 6, 7, 4]
35 [3, 1, 6, 7, 4, 5]
67 [3, 2, 3, 0, 1, 6]
99 [3, 3, 0, 1, 6, 7]
[(0, 99), (1, 35), (2, 67), (3, 3)]

The keys end up in slots 3, 1, 2 and 0, all different, and these placements match a real CPython 3.12 dict. Linear probing would have packed them into slots 3, 4, 5 and 6.

indices: [3, 1, 2, 0, -1, -1, -1, -1]      (-1 means empty)
entries: [(3, "a"), (35, "b"), (67, "c"), (99, "d")]

pythonrunnable cell

import sys

d = {}
previous = sys.getsizeof(d)
grew_at = []
for i in range(1, 51):
    d[i] = i
    size = sys.getsizeof(d)
    if size != previous:
        grew_at.append(i)
        previous = size
print(grew_at)

Output:

[1, 6, 11, 22, 43]

CPython-style probing: collisions and resize at 2/3 fullInteractive

Each key hashes to a first slot. When that slot is taken, the key probes onward using the perturbation rule above. When the table passes 2/3 full, it doubles and every entry is placed again.

Loading visualization...

#Your own class as a key

pythonrunnable cell

class Point:
    """A point on a grid. We promise not to change x or y after creation."""

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        if not isinstance(other, Point):
            return NotImplemented
        return (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        return hash((self.x, self.y))      # hash the same fields that __eq__ compares

    def __repr__(self):
        return f"Point({self.x}, {self.y})"


visited = {Point(2, 3): "start"}
print(visited[Point(2, 3)])                # a different object with the same data
print(Point(2, 3) == Point(2, 3), Point(2, 3) is Point(2, 3))


class NoHash:
    def __init__(self, n):
        self.n = n

    def __eq__(self, other):
        return self.n == other.n


try:
    {NoHash(1): "x"}
except TypeError as error:
    print(error)

Output:

start
True False
unhashable type: 'NoHash'

#Sets are dicts without values

A set holds keys and no values. You can build one from the chained map by storing True for each key and ignoring it.

pythonrunnable cell

class HashSet:
    """A set: a hash map that keeps the keys and ignores the values."""

    def __init__(self, items=()):
        self._map = ChainedMap()
        for item in items:
            self.add(item)

    def add(self, item):
        self._map.put(item, True)

    def discard(self, item):
        self._map.delete(item)

    def __contains__(self, item):
        return self._map.get(item, False)

    def __len__(self):
        return len(self._map)


animals = ["cat", "dog", "cat", "emu", "dog", "cat"]
s = HashSet(animals)
print(len(s), "cat" in s, "owl" in s)
s.discard("cat")
print(len(s), "cat" in s)
print(len(set(animals)))

Output:

3 True False
2 False
3

#Dict, set or sorted list?

Choose by the question you will ask most often.

You need to	dict	set	sorted list with bisect
Find the value for a key	O(1) average	not offered	O(log n) to find the position
Ask "is x there?"	O(1) average	O(1) average	O(log n)
Add one item	O(1) amortized	O(1) amortized	O(n), later items shift
Get the smallest or largest	O(n)	O(n)	O(1) at the two ends
List everything between two keys	O(n)	O(n)	O(log n + k) for k results
Memory	high, spare slots	high, spare slots	low

pythonrunnable cell

from bisect import bisect_left, insort

names = sorted(["pear", "fig", "apple", "kiwi", "date", "grape", "cherry"])
low, high = bisect_left(names, "d"), bisect_left(names, "h")
print(names[low:high])
insort(names, "banana")
print(names)
print(names[0], names[-1])

Output:

['date', 'fig', 'grape']
['apple', 'banana', 'cherry', 'date', 'fig', 'grape', 'kiwi', 'pear']
apple pear

bisect_left finds a position in O(log n) steps, and slicing out the results costs one step per result. insort finds the spot in O(log n) but then shifts later items to make room, which is O(n).

#Where hashing shows up in ML

pythonrunnable cell

def hash_features(tokens, n_features=8):
    """Count tokens into a fixed-size vector, with no vocabulary to store."""
    counts = [0] * n_features
    for token in tokens:
        counts[simple_hash(token) % n_features] += 1
    return counts


print(hash_features(words))

Output:

[0, 1, 1, 0, 2, 1, 1, 2]

Eight words fell into 8 slots, and slots 4 and 7 each caught two words. This is the collision table again, used on purpose. It trades a little accuracy for no stored vocabulary and a fixed size.

#Common mistakes

Watch Out

Mutating a key after it is stored

Fix: Use keys that cannot change: numbers, strings, tuples, or a class you promise not to modify. If the data must change, remove the pair first and put it back.

pythonrunnable cell

class Cell:
    def __init__(self, row, col):
        self.row = row
        self.col = col


def cell_hash(cell):
    return cell.row * 10 + cell.col


m3 = ChainedMap(hash_fn=cell_hash)
c = Cell(2, 3)
m3.put(c, "start")                 # stored by hash 23, in bucket 23 % 4 = 3
c.row = 9                          # the key changes: hash 93, bucket 93 % 4 = 1
print(m3.get(c), len(m3))
print([i for i, bucket in enumerate(m3.buckets) if bucket])

Output:

None 1
[3]

A key's place comes from its hash when it was stored. The pair is still in bucket 3, but the changed key now asks bucket 1. The length is 1, yet get returns None.

Watch Out

Resizing without placing every pair again

Fix: After the table grows, work out the index for every pair again. The index depends on the size, so a pair from old bucket 3 may belong in new bucket 11.

pythonrunnable cell

class LazyResizeMap(ChainedMap):
    def _resize(self):
        # BUG: add empty buckets, but leave every pair where it was
        self.buckets = self.buckets + [[] for _ in range(len(self.buckets))]


lazy = LazyResizeMap()
for i, word in enumerate(["cat", "dog", "emu", "owl"]):
    lazy.put(word, i)
print(len(lazy.buckets), [lazy.get(w, "lost") for w in ["cat", "dog", "emu", "owl"]])

Output:

8 ['lost', 'lost', 'lost', 'lost']