Hash Tables

In the sets lesson you saw that checking whether a value is in a set is fast, and that this has something to do with hashing. This lesson finds out exactly how that works. It starts with a problem where the speed of a lookup really matters.

Say two shops each have a list of the product codes they sell, and you want the products that both of them sell.

A small version first

The first shop sells 3, 26, 54, 32, 1 and 42, and the second sells 32, 7, 1 and 19. The function common_nested takes each code from the first list and compares it with every code in the second list. When two codes match, it keeps the code:

def common_nested(a, b):
    found = []
    for x in a:
        for y in b:
            if x == y:
                found.append(x)
    return found
common_nested([3, 26, 54, 32, 1, 42], [32, 7, 1, 19])

[32, 1]

So it gives 32 and 1, the two codes that appear in both lists.

Two realistic shops

Now make it realistic. The first shop has ten thousand product codes and the second has five thousand, picked at random from the numbers below one million, with a seed of 1 so that you get the same codes every time:

import random

r = random.Random(1)
shop_a = r.sample(range(1_000_000), 10_000)
shop_b = r.sample(range(1_000_000), 5_000)
len(shop_a), len(shop_b), shop_a[:3]

(10000, 5000, [140891, 596853, 888598])

O(n × m)

So if the first list has n codes and the second has m, that is n times m comparisons, and common_nested is O(n × m). The only extra space it uses is the list of matches, found, which is small next to the two inputs.

So can you find the same 53 codes without comparing every pair?

You can, with a set. The function common_set first builds a set from the second list. Then it goes through the first list, and keeps each code that is in that set:

def common_set(a, b):
    in_b = set(b)
    return [x for x in a if x in in_b]
common_set([3, 26, 54, 32, 1, 42], [32, 7, 1, 19])

[32, 1]

On the small lists it gives 32 and 1, the same as before. And on the two shops it gives exactly the same list as common_nested:

common_set(shop_a, shop_b) == common_nested(shop_a, shop_b)

True

How much work is that?

Count the steps the way you did in lesson 7.1:

• Building the set goes through the five thousand codes of shop_b once, so that is O(m).
• Checking whether a value is in a set is O(1) on average, and common_set does it once for each of the ten thousand codes in shop_a, so that is O(n).

Together, that is O(n + m): about fifteen thousand steps instead of fifty million.

len(shop_a) + len(shop_b)

15000

When it was timed, common_set took about 0.39 milliseconds, where common_nested took about 0.66 seconds.

The memory it costs

But the set uses memory. Not counting the result that both versions return, common_set uses O(m) extra space for the set of five thousand codes, where common_nested uses O(1). That is the trade-off from lesson 7.1, memory for time, and five thousand codes is very little memory to spend.

Dictionaries too

A dictionary gives you exactly the same lookups, because a Python dictionary is a hash table too, one that also stores a value with each key. So everything about hashing in this lesson applies to both.

But you still have not answered the question from the sets lesson: how does in, on a set, find a value without searching through it?

It starts with a hash functionKey termA function that turns a value into an int, the same int every time for the same value. Python's is hash().: a function that takes a value and returns an int computed from it, called the value's hash. Python has one built in, called hash().

For a nonnegative int that is not too large, the hash is the int itself, so hash(32) is 32. And the same value always gives the same hash within one run of Python, so calling hash(32) twice gives 32 both times:

hash(32), hash(32)

(32, 32)

Hashes of other values

For other values, the int looks random. The hash of the tuple (1, 2) is a large negative number:

hash((1, 2))

-3550055125485641917

A string's hash changes from one session to the next. That is why, in the sets lesson, the order a set of names printed in could change between sessions. So this lesson never prints the hash of a string: the number you got would not match the one here. But within one session, you get the same hash for "kettle" every time you call it:

hash("kettle") == hash("kettle")

True

Values with no hash

Some values have no hash at all. Here is what happens if you call hash() on the list [1, 2]:

hash([1, 2])

TypeError: unhashable type: 'list'

You get a TypeError: unhashable type 'list'. It is the same error the sets lesson showed when you tried to put a list in a set. You will see why a list has no hash later in this lesson.

Where you are so far

A set finds the common codes in O(n + m), by using O(m) extra memory. And it can do that because a hash function turns each value into an int, and it is the same int every time.

So use that int to build a table of your own. A hash tableKey termA list of buckets, where a value's hash decides its bucket, so a lookup compares only with the keys in one bucket. Every Python set and dict is one. is a list of slots called buckets, and a value's hash determines which bucket it goes in.

The table below has three functions:

• make_table builds a list of empty lists, one for each bucket, so make_table(8) gives you eight of them.
• add computes which bucket a key goes in with hash(key) % len(table): the hash of the key, modulo the length of the table. Modulo gives the remainder after dividing, so with eight buckets the result is between 0 and 7, which is a valid bucket number every time. Then add appends the key to that bucket, if it is not there already.
• contains checks whether a key is in the table. You will come back to it in a moment.

Adding five keys

Add five keys: 32, 46, 31, 22 and 28. These are small ints, so each one's hash is the int itself, and its bucket is the same in every session.

The table after five keys

Here are the three functions, and the five keys added to a table of eight buckets:

def make_table(size):
    return [[] for _ in range(size)]

def add(table, key):
    bucket = table[hash(key) % len(table)]
    if key not in bucket:
        bucket.append(key)

def contains(table, key):
    bucket = table[hash(key) % len(table)]
    comparisons = 0
    for stored in bucket:
        comparisons += 1
        if stored == key:
            return True, comparisons
    return False, comparisons
table = make_table(8)
for key in [32, 46, 31, 22, 28]:
    add(table, key)
table

[[32], [], [], [], [28], [], [46, 22], [31]]

So the table has 32 in bucket 0, 28 in bucket 4, 46 and 22 in bucket 6, and 31 in bucket 7. You can check each bucket number directly:

[hash(key) % 8 for key in [32, 46, 31, 22, 28]]

[0, 6, 7, 6, 4]

contains

Now for contains, which is where the speed comes from. It computes the bucket the same way, with the hash of the key modulo 8, and compares the key only with the keys in that one bucket. It counts its comparisons, like the functions in the previous two lessons did, and returns whether it found the key along with that count.

So contains(table, 22) checks bucket 6, and finds 22 after two comparisons, not five:

contains(table, 22)

(True, 2)

contains(table, 31) checks bucket 7, and finds it after one:

contains(table, 31)

(True, 1)

And 30 is not in the table. contains(table, 30) checks bucket 6, because 30 modulo 8 is 6, and returns False after two comparisons:

contains(table, 30), hash(30) % 8

((False, 2), 6)

So the number of comparisons does not depend on how many keys the table holds. It depends only on how many keys are in one bucket.

So what happens when you add a lot of keys to only eight buckets? Add the numbers from 0 to 999 to a new table called small:

small = make_table(8)
for key in range(1_000):
    add(small, key)
[len(bucket) for bucket in small], contains(small, 999)

([125, 125, 125, 125, 125, 125, 125, 125], (True, 125))

Each bucket ends up with 125 keys. So contains(small, 999) has to compare with 125 keys in its bucket, which is a linear search again, just on a shorter list.

But put the same thousand keys in 2,048 buckets, and no bucket holds more than one key. contains(big, 999) makes one comparison:

big = make_table(2_048)
for key in range(1_000):
    add(big, key)
max(len(bucket) for bucket in big), contains(big, 999)

(1, (True, 1))

Load factor

What matters is how many keys each bucket holds on average, which is the number of keys divided by the number of buckets. That number is called the load factorKey termThe number of keys divided by the number of buckets. A lookup's work grows with it.. With 8 buckets it is 125, and with 2,048 it is under a half:

1_000 / 8, 1_000 / 2_048

(125.0, 0.48828125)

The higher the load factor, the more keys each lookup has to compare with. So a hash table adds buckets as it fills up, and moves every key to its new bucket, to keep the load factor low. That is called resizing.

Watching a dictionary resize

You can watch Python do that. sys.getsizeof() returns the size of an object in bytes. This cell adds the keys 0 to 29 to a dictionary one at a time, and records the number of keys every time the size changes:

import sys
d = {}
sizes = [(0, sys.getsizeof(d))]
for i in range(30):
    d[i] = i
    if sys.getsizeof(d) != sizes[-1][1]:
        sizes.append((len(d), sys.getsizeof(d)))
sizes

[(0, 64), (1, 224), (6, 352), (11, 632), (22, 1168)]

An empty dictionary is 64 bytes, and it becomes 224 when you add the first key. Then it grows at 6 keys, at 11, and at 22, each time to a bigger table.

How Python's own tables differ

Python's own dictionary and set do not keep a list in each bucket, the way your table does. When a key's slot is already taken, they try another slot in the table instead. But the idea is the same: the hash determines which slot is checked first, and a collision means an extra comparison.

Average case, not a guarantee

That is why a set's O(1) is the average case, not a guarantee. It depends on a hash that spreads the keys across the buckets. In the worst case, with every key in one bucket, a lookup is O(n).

A real set

A real set does not have this problem with multiples of 8. It is not limited to eight slots, because it grows as it fills. And when two keys map to the same slot, it uses the rest of the hash to choose the next slot to try. So this pattern does not slow down a real set.

Here are two real sets of a million numbers each: the multiples of 8 below eight million, and the first million numbers:

native_eights = set(range(0, 8_000_000, 8))
native_plain = set(range(1_000_000))
((len(native_eights), len(native_plain)), (7_999_992 in native_eights, 999_999 in native_plain))

((1000000, 1000000), (True, True))

When they were timed, checking for 7,999,992 in the set of multiples of 8 took about 28 nanoseconds, and checking for 999,999 in the set of the first million numbers took about 24.

So why is a list unhashable? Say you stored the list [32, 46] as a key, and then appended 3 to it. Tuples can stand in for the list's contents before and after, since a tuple of numbers has a hash:

hash((32, 46)) % 8, hash((32, 46, 3)) % 8

(6, 5)

As a tuple, 32 and 46 goes in bucket 6, but 32, 46 and 3 goes in bucket 5. So after the append, contains would compute bucket 5 and check there, while the key is still stored in bucket 6, so it would never find the key.

That is why a key's hash must never change while it is stored. A tuple of numbers cannot change, so Python accepts it as a key:

(32, 46) in {(32, 46): True}

True

But a list can change, so Python does not accept a list as a key. And a tuple that holds a list is not accepted either, because the list inside it could still change:

hash((1, [2, 3]))

TypeError: unhashable type: 'list'

When a set is the right choice

There is one more thing to keep in mind when you choose a set. Building a set goes through every value once, so it is O(n). That means a set built for a single check still takes linear time overall, and can take longer than one linear search. In the sets lesson's example, building a set of a million numbers took about 33 milliseconds, where scanning the list for its last number took about 6.

So a set is the right choice when you check many values against the same collection, the way common_set checked ten thousand codes against one set.

You wanted to know how a set finds a value without searching, and you answered it by building a hash table yourself. A hash function turns a value into an int, the same int every time. The table takes that int, modulo its number of buckets, to determine which bucket a key goes in, so a lookup only compares with the keys in that one bucket.

Two keys in the same bucket is a collision, and the load factor is the number of keys per bucket, which is why a table adds buckets as it fills. That is what keeps a lookup O(1) on average, though it is O(n) in the worst case, with every key in one bucket. And because a key's hash must never change while it is stored, a list cannot be a key.

Across the module, a linear search is O(n), binary search is O(log n) on sorted data, and a hash table is O(1) on average. And a set turned a nested loop that was O(n × m) into O(n + m), with O(m) extra memory. Hash tables are used in every Python dictionary and set, in database indexes, in caches, and in machine learning, to find similar items quickly.

Your challenge

You have ten thousand reviews, each with the name of the product it is about, and a list of five hundred products that have been recalled. Count how many of the reviews are about a recalled product.

1. Do it first with a loop inside a loop, and then with a set.
2. Write down the time and space complexity of each version.
3. Time both.

The end of the Python track

That is the end of this module, and of the Python track. You started with one print statement in a notebook. Then you learned variables, types and operators, and how a program makes choices and repeats code with loops. You stored data in lists, tuples, sets, dictionaries and strings, and wrote functions to reuse your code. Then you put that code in modules and a project of its own, read and wrote files, handled errors, and used tests and tools to check it. And now you can work out how the time and memory a program uses grow as its data grows.

That last part matters for everything that comes next. In the machine learning course, you will measure the time and space complexity of every model, both to train it and to predict with it, on real applications. And it is one of the factors in choosing a model, along with how well it predicts.