Buckets and chaining

You have used dicts and sets since early in the course, and the module on complexity relied on them: x in seen takes O(1) on average, however big the set is. In this module you build that data structure yourself, a hash table, so you know why it's fast, what it costs, and when it isn't fast at all.

Buckets

A hash table keeps its items in a list of buckets. To decide which bucket a key goes in, a hash function turns the key into a whole number, and the remainder after dividing by the number of buckets picks one: hash(key) % len(buckets). To find the key later, you work out the same bucket and look only there, never in the rest of the table.

For a whole number such as 12, Python's hash gives the number itself, so with 5 buckets the key 12 goes in bucket 12 % 5, which is 2:

buckets = [[] for i in range(5)]
for key in [12, 7, 30, 21, 5, 18, 44]:
    buckets[key % 5].append(key)

for i in range(len(buckets)):
    print(i, buckets[i])

0 [30, 5]
1 [21]
2 [12, 7]
3 [18]
4 [44]

Two keys in one bucket, like 12 and 7, is a collision. Collisions can't be avoided, since there are far more possible keys than buckets, so each bucket here is a list that holds every key that lands in it. That's called separate chaining, and each bucket's list is a chain. Python's % never gives a negative remainder when the number of buckets is positive, so a negative key gets a real bucket too: -7 % 5 is 3.

Each bucket must be a list of its own. [[]] * 5 looks the same, but it's five references to one and the same list, so a key added to one bucket shows up in all of them:

buckets = [[]] * 5
buckets[12 % 5].append(12)
print(buckets)

[[12], [12], [12], [12], [12]]

Hashing strings

hash works on strings too, but the number it gives for a string changes every time Python starts: Python mixes a random value into it, so that nobody can pick keys that all collide on purpose and slow a web server down. To see where words go, write a hash function of your own. This one starts from 0 and, for each character, multiplies the number so far by 37 and adds the character's code, ord(char). The last column is the bucket in a table of 13:

def word_hash(word):
    h = 0
    for char in word:
        h = h * 37 + ord(char)
    return h


for fruit in ["mango", "lemon", "melon", "grape", "peach", "apple"]:
    print(fruit, word_hash(fruit), word_hash(fruit) % 13)

mango 209351402 0
lemon 207678779 9
melon 209551571 8
grape 198950063 0
peach 215158545 4
apple 187624178 1

Mango and grape collide in bucket 0. A hash function may follow any rule, with one condition: a key gets the same number every time it's hashed. Otherwise a lookup would look in another bucket than the one the key went into. Past that, the more evenly a function scatters keys over the buckets, the shorter the chains. Multiplying by 37 before each addition makes the position of a character matter, so "lemon" and "melon", which have the same letters, land in different buckets.

Keys and values

A dict keeps a value with each key, so the buckets of a map hold pairs. Each pair here is a small list, [key, value], so that its value can be changed:

class HashMap:
    def __init__(self, size):
        self.buckets = [[] for i in range(size)]

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

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                return pair[1]
        return None


rooms = HashMap(4)
rooms.put(101, "Ada")
rooms.put(205, "Ben")
rooms.put(101, "Cleo")
print(rooms.get(101), rooms.get(205), rooms.get(310))
print(rooms.buckets)

Cleo Ben None
[[], [[101, 'Cleo'], [205, 'Ben']], [], []]

put searches the key's bucket first: a key that's already there gets its new value, and only a new key is appended. Without that search, the bucket would hold two pairs for room 101, and get would find the old one. The keys are compared with == because a bucket can hold other keys too: 101 and 205 share bucket 1.

What it costs

Working out the bucket is O(1). After that, get and put go through one chain. With n pairs in m buckets, a chain holds n / m pairs on average, so as long as there are about as many buckets as pairs, each operation takes O(1) on average. The worst case is O(n): if every key lands in the same bucket, the table is one long list. With 8 buckets, the keys 0, 8, 16, 24 and so on all go to bucket 0. Python's dict and set have the same worst case, and their hash functions make it rare. The memory is O(n + m): a pair for each key and a list for each bucket.