Hash tables

Hashing functions, collisions, rehashing by probing, chaining and load factor: finding markers fast.

A3.5Data structuresA level20 min

BugBot sees a marker and needs to know where on the mat that marker is. With 1,000 markers in a list, a linear search could take 1,000 comparisons; a binary search on a sorted list takes about 10. A hash table usually takes one. It works out where a record should be from the key itself, and goes straight there.

The idea

A hash table is an array of slots. A hashing function (or hash function) turns a record's key into a slot index, called its hash. To store a record, hash its key and put the record in that slot. To find it again, hash the key again and look in the same slot. No searching: the key tells you where to look.

The simplest hashing function for a whole number key is the remainder after dividing by the table size:

slot = key MOD size

With 11 slots, marker 14 goes in slot 3 (14 MOD 11 = 3) and marker 9 goes in slot 9.

Good hashing functions

A good hashing function:

• is quick to calculate, or the table loses its speed advantage;
• is deterministic: the same key always gives the same slot, or records could never be found again;
• spreads keys evenly across the slots, so few keys share a slot;
• always gives a valid index for the table.

Common methods:

Tables whose size is a prime number tend to spread keys better with the MOD method, because keys that share a factor with the size do not all bunch into the same few slots.

Collisions

Two different keys can hash to the same slot: that is a collision. With 11 slots, 14 and 25 both give 3. Since there are far more possible keys than slots, collisions cannot be avoided, only handled.

Open addressing: rehashing to the next free slot

When the home slot is taken, apply a rehash: work out another slot and try that. The simplest rehash is linear probing: try the next slot, (slot + 1) MOD size, wrapping from the end back to the start, until a free slot is found.

Searching must follow exactly the same path. Hash the key and look in the home slot; if the slot holds a different key, probe the next slot, and so on. The search ends when it finds the key, when it reaches an empty slot (the key would have been put there, so it is not in the table), or when it has looked at every slot.

SIZE = 7
table = [None] * SIZE

def put(key):
    slot = key % SIZE
    home = slot
    while table[slot] is not None:
        slot = (slot + 1) % SIZE          # linear probing: try the next slot, wrapping round
    table[slot] = key
    print(key, "hashes to", home, "and is stored in", slot)

def find(key):
    slot = key % SIZE
    for probes in range(1, SIZE + 1):
        if table[slot] is None:
            return "not found after " + str(probes) + " probes"
        if table[slot] == key:
            return "found in slot " + str(slot) + " after " + str(probes) + " probes"
        slot = (slot + 1) % SIZE
    return "not found: the table is full"

for key in [12, 19, 8, 26, 33]:
    put(key)
print(table)
print(26, find(26))
print(40, find(40))

Run this in the simulator

Four of the five keys hash to 5, so they fill slots 5, 6, 0 and then 2, stepping over 8 in slot 1. A run of occupied slots like this is a cluster: every key that lands anywhere in it has to probe to the end, so the cluster grows and slows the table down. Probing in bigger steps, or in steps that grow (1, 4, 9 slots on), spreads the keys out more.

Deleting is awkward with open addressing. If 19 is removed from slot 6 by emptying it, a search for 26 stops at the empty slot 6 and wrongly reports that 26 is not there. So a deleted slot is marked deleted rather than empty: a search carries on past it, and a new record may be stored in it.

Chaining

Instead of probing, each slot can hold a linked list (a chain) of every record that hashed to it. A collision just adds another node to the chain. The table never fills up, deletion is a normal linked-list delete, and a search looks along one short chain.

SIZE = 11

def hash_name(name):
    total = 0
    for ch in name:
        total = total + ord(ch)
    return total % SIZE

buckets = [[] for i in range(SIZE)]      # chaining: each slot holds a list
for name in ["ramp", "dock", "gate", "pram", "bin", "nib"]:
    buckets[hash_name(name)].append(name)

for slot in range(SIZE):
    if buckets[slot]:
        print(slot, buckets[slot])

Run this in the simulator

Six names, three collisions. Adding character codes ignores their order, so "ramp" and "pram", and "bin" and "nib", always collide; "dock" and "gate" happen to add up to the same total. A better function for text weights each character by its position.

Load factor and resizing

The load factor is the number of records divided by the number of slots. As it rises, collisions become more common and searches slower; with open addressing a full table cannot take any more at all. So when the load factor passes a threshold (0.7 is a common choice), a new, larger table is made and every record is rehashed into it, because each key's slot depends on the table size. This is slow while it happens, but rare.

Hash tables are used for dictionaries (lesson A3.6), database indexes, caches, the symbol table a compiler keeps of every variable name, and files with direct access by hashing (lesson A3.8).

Task: markers in a hash table

MARKERS lists six markers as (id, x, y): the marker's id and where it is, in cm from the robot's start. table is a list of 11 slots, each None until used. Build the hash table yourself, without a Python dictionary.

1. Write put(key, x, y): the home slot is key % SIZE. If that slot is taken, probe the next slot, wrapping from 10 back to 0, until one is empty. Store the tuple (key, x, y) there and print put <key> in slot <slot>.
2. Write get(key): follow the same path. Count every slot you look at as one probe, including an empty slot that ends the search. If you find the key, print found <key> at slot <slot> after <probes> probes and return its tuple. If you reach an empty slot, print <key> not found after <probes> probes and return None.
3. Put the six markers in the order listed. Then call get(42), which is not in the table.
4. Call get(31), and drive to marker 31: right by its x, then forward by its y.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

SIZE = 11
# (marker id, x, y): where each marker is, in cm from the start
MARKERS = [(14, 20, 40), (25, 60, 20), (47, 40, 60), (9, 0, 50), (20, 10, 30), (31, 30, 45)]

table = [None] * SIZE

def put(key, x, y):
    pass

def get(key):
    pass

Challenges

1. Before running your program, work out on paper which slot each marker goes in. Which markers collided, and how many probes did each need?
2. Change put to probe 3 slots on each time instead of 1. Does every key still find a slot? What if the size were 12 instead of 11?
3. Rewrite the table with chaining. How many probes does get(31) take now?