Step 2 of 5

Load factor and rehashing

The table of the last step keeps the number of buckets it started with. Put 100,000 pairs into 8 buckets and each chain holds 12,500 of them: every get is a linear search again, and adding the 100,000 keys takes more than half a billion comparisons.

The load factor

The load factor is the number of pairs divided by the number of buckets, count / len(buckets): the average length of a chain. A hash table keeps it small by growing. When the load factor passes a limit, often 0.75, the table makes twice as many buckets and moves every pair into them. That's called rehashing.

Every pair has to move, because a key's bucket depends on the number of buckets. Four keys that share bucket 1 of 4 split up when there are 8:

In the Python interpreter

>>> keys = [5, 9, 13, 17]
>>> [key % 4 for key in keys]
[1, 1, 1, 1]
>>> [key % 8 for key in keys]
[5, 1, 5, 1]

So growing takes three moves:

Keep the old list of buckets in a variable.
Make a new list with twice as many empty buckets.
Go through every pair of every old bucket and append it to its bucket in the new list, worked out with the new number of buckets.

A common mistake is to append empty buckets to the old list and stop there. The table gets bigger, but the old pairs stay where the old size put them: key 13 sits in bucket 1, while get(13) now looks in bucket 5 and returns None, though the key is still in the table.

Why adding stays O(1)

A rebuild moves every pair, so the add that triggers it costs O(n). But rebuilds get rarer as the table grows: after one, the table has room for as many new pairs as it already holds. This program counts the pairs moved while n keys go into a table of 8 buckets that grows when the load factor passes 0.75, once by doubling and once by adding 8 buckets each time:

def moves_while_adding(n, double):
    buckets = 8
    moves = 0
    for count in range(1, n + 1):
        if count / buckets > 0.75:
            moves += count
            if double:
                buckets *= 2
            else:
                buckets += 8
    return moves


for n in [1000, 10_000, 100_000]:
    print(n, moves_while_adding(n, True), moves_while_adding(n, False))

Output

1000 1538 83332
10000 12293 8333332
100000 196617 833333332

With doubling, the moves never get much past twice the number of keys. The rebuilds move 7, 13, 25, 49 pairs and so on, each about twice the one before, so all of them together come to about twice the last one, and the last one is at most n. So n adds cost O(n) in all: O(1) amortized per add. Now and then one add is slow, but averaged over all of them each add is O(1), for the same reason that list.append is. Adding a fixed 8 buckets instead rebuilds every few adds, and the moves grow like n²: over 800 million for 100,000 keys.

Python's dict: open addressing

Python's dict and set grow the same way, but they don't keep chains. All the keys sit in one list of slots. When a key's slot is taken, the table tries another slot, and another, until it finds the key or an empty slot. That's open addressing. The simplest kind, linear probing, tries the next slot, and wraps around to the start after the last one:

slots = [None] * 8
for key in [3, 11, 19, 6]:
    i = key % 8
    while slots[i] is not None:
        i = (i + 1) % 8
    slots[i] = key
print(slots)

Output

[None, None, None, 3, 11, 19, 6, None]

3, 11 and 19 all start at slot 3, so 11 moves on to slot 4 and 19 to slot 5. A search for 19 starts at slot 3 and steps along until it finds it. A search for 27 steps from slot 3 over 3, 11, 19 and 6 to the empty slot 7: an empty slot means the key isn't there. So the table must never fill up, or a search for a missing key would never end, and long runs of taken slots make every search slow. Python's dict grows when about two-thirds of its slots are taken, and instead of the next slot it jumps around in a scrambled order, which keeps the runs short.

Your task

Challenge 1 of 3

Make HashMap grow. put already counts the new pairs in self.count. After it adds a new pair, when the load factor self.count / len(self.buckets) is more than 0.75, it should call _grow, which doubles the number of buckets and moves every pair to its new bucket. The table starts with 8 buckets, so the 7th pair makes it grow to 16. The hidden test puts 50,000 pairs in the table, which is only fast when the table doubles each time. This program:

table = HashMap()
for key in range(6):
    table.put(key, key * 10)
print(len(table.buckets))
table.put(6, 60)
print(len(table.buckets), table.get(3), table.get(6))

prints:

8
16 30 60

Challenge 2

What does this program print? It follows a table that starts with 4 buckets and doubles when its load factor is more than 0.75. Type each line it prints.

Challenge 3

Write a class OpenSet: a set that keeps its keys with open addressing and linear probing, as the last example of the lesson does. The keys sit in one list, self.slots, where None marks an empty slot (a key is never None), and self.count is the number of keys. The seed starts with 4 slots and a count of 0.

The search for a key starts at slot hash(key) % len(self.slots) and moves one slot to the right at a time, back to slot 0 after the last one, until it reaches the key or an empty slot.
add(key) returns False when the search reaches the key. Otherwise it stores the key in the empty slot the search reached, adds one to self.count, and returns True.
contains(key) returns whether the key is in the set.
Like Python's dict, the table grows when more than two-thirds of its slots are taken. After add stores a new key, if self.count * 3 > len(self.slots) * 2, the table makes twice as many empty slots and stores every key again: a key's first slot depends on the number of slots.

The hidden test adds 100,000 keys and looks up 100,000: key in self.slots would search the whole list every time.

For example, this program:

s = OpenSet()
print(s.add(7), s.add(15), s.add(7))
print(s.slots)
print(s.contains(15), s.contains(23))

prints (7 and 15 both start at slot 3, the last one, so 15 goes around to slot 0; a search for 23 starts at slot 3, goes on to slot 0 and stops at the empty slot 1):

True True False
[15, None, None, 7]
True False

Previous: Buckets and chaining Next: A map that works like dict