Hash tables explained
How a hash function turns a key into a slot, why look-up is about O(1), what a collision is and what the load factor costs. Programs in your browser fill a table on the mat, count every slot a look-up looks at, and measure how the cost climbs as the table fills.
A hash table finds things without searching. Every other way of finding an item in a collection involves looking at items until you find the right one: a linear search looks at each in turn, a binary search halves the list each time. A hash table works out where the item ought to be from the item itself, goes there, and finds it. That is why a dictionary in Python, a table of variable names in a compiler and the map from a marker's number to where it is on the mat are all hash tables underneath.
On this page a robot's program builds small hash tables, draws their slots along the mat, and counts what every look-up costs. Each demo below is a real program you can change and run.
The idea in one line
slot = hash(key)
The table is an array of slots. The key is the thing you know (a marker number, a name, a word). The hash function turns the key into the index of a slot, and that index is where the item is kept. Store it there, and later, to find it again, work out the same index and look.
The commonest hash function for a whole number key is the remainder after dividing by the size of the table:
slot = key MOD size
With 11 slots, marker 23 goes in slot 1, because 23 MOD 11 is 1. Nothing else has to be looked at, and it makes no difference whether the table holds 9 markers or 9 million.
Filling a table
This demo puts nine marker numbers into a table of 11 slots and draws the table across the mat, one square per slot. Yellow squares are empty slots, blue ones are full, and the green square is the slot the key just went into.
The program
from bugbot import *
connect()
# change the keys or the size and press Run
SIZE = 11
KEYS = [23, 7, 36, 12, 19, 44, 5, 31, 30]
table = [None] * SIZE
def hash_of(key):
return key % SIZE # the hash function
def slot_x(i):
# where slot i is drawn, in cm across the mat
return 5 + 9 * i
def show(home, slot):
empty = [(slot_x(i), 55) for i in range(SIZE) if table[i] is None]
full = [(slot_x(i), 55) for i in range(SIZE) if table[i] is not None]
draw("empty slots", empty, "yellow", "squares", 8)
draw("full slots", full, "blue", "squares", 8)
draw("home slot", [(slot_x(home), 55)], "red", "squares", 8)
draw("where it went", [(slot_x(slot), 55)], "green", "squares", 8)
wait(0.6)
for key in KEYS:
home = hash_of(key)
slot = home
probes = 1 # slots looked at
while table[slot] is not None:
slot = (slot + 1) % SIZE # try the next one, wrapping round
probes = probes + 1
table[slot] = key
plot("slots looked at", probes)
show(home, slot)
print("key", key, "| hash", home, "| stored in", slot, "| probes", probes)
print("table:", table)
Seven of the nine keys land in an empty slot at the first try. The chart is flat at 1 for those, and the red square and the green square are the same square.
Two keys do not. 12 MOD 11 is 1, and slot 1 already holds 23, so the program looks at slot 2 and puts it there. 30 MOD 11 is 8, and slots 8 and 9 are taken, so it ends up in slot 10 after looking at three slots. The red square shows where the key wanted to go, and the green square shows where it went.
Why look-up is about O(1)
Finding a key again means doing exactly what putting it in did: hash the key, go to that slot, and if the key there is not the one you want, look at the next slot, and the next, until you find it or reach an empty slot. An empty slot means the key is not in the table, because it would have been put there.
This demo looks up each of the nine keys twice: once in the hash table, and once by searching a plain list of the same nine keys from the start.
The program
from bugbot import *
connect()
# change the keys or the size and press Run
SIZE = 11
KEYS = [23, 7, 36, 12, 19, 44, 5, 31, 30]
table = [None] * SIZE
for key in KEYS:
slot = key % SIZE
while table[slot] is not None:
slot = (slot + 1) % SIZE
table[slot] = key
def find_in_table(key):
slot = key % SIZE
probes = 1
while table[slot] is not None:
if table[slot] == key:
return probes
slot = (slot + 1) % SIZE
probes = probes + 1
return probes # an empty slot: it is not here
def find_in_list(key):
checks = 0
for item in KEYS:
checks = checks + 1
if item == key:
return checks
return checks
hash_total = 0
list_total = 0
for key in KEYS:
a = find_in_table(key)
b = find_in_list(key)
hash_total = hash_total + a
list_total = list_total + b
plot("hash probes", a)
plot("list comparisons", b)
print("find", key, "| hash table", a, "| list", b)
wait(0.3)
print("average slots looked at:", round(hash_total / len(KEYS), 2))
print("average list comparisons:", round(list_total / len(KEYS), 2))
The list search takes longer for every key after the first, and it would take longer still with more keys: for a list of a thousand it would average about 500 comparisons. The hash table's line stays where it is. The work does not depend on how many keys are in the table, only on how crowded the table is, and that is what O(1) means: constant time, whatever the size.
It is "about" O(1) rather than exactly O(1) because of the probing. The worst case for a hash table is dreadful: if every key lands in the same slot, finding one means looking at every other one first, which is O(n). Real programs live at the average, and the average is what the next two demos are about.
Collisions
Two different keys giving the same slot is a collision. Collisions are not a sign of a bad hash function or a bad table. There are far more possible keys than there are slots, so collisions are certain; a hash table is a plan for dealing with them.
Open addressing is what the demos above use: when the home slot is taken, work out another slot and try that. The simplest version is linear probing, (slot + 1) MOD size, wrapping from the last slot back to slot 0. It is easy to write and it keeps everything in one array. Its weakness is clustering: a run of full slots makes it likelier that the next key lands in the run and makes it longer. Key 30 above walked into a cluster.
Chaining is the other way. Each slot holds a list, and every key whose hash is that slot joins that list. Nothing ever has to move, the table can hold more keys than it has slots, and deleting is easy. The cost is a list to follow at each slot, and the memory those lists take.
Deleting from an open addressed table has a trap. Empty the slot and any key that probed past it can no longer be found, because the search stops at the empty slot. The usual fix is to mark a deleted slot rather than clear it: a search carries on past the mark, and a new key may be put there.
The load factor
The load factor is how full the table is:
load factor = keys stored ÷ slots
The nine keys in eleven slots above give 9 ÷ 11, about 0.82, which is high. This demo builds a table of 101 slots again and again, with more keys in it each time, and measures the average number of slots looked at to find a key.
The program
from bugbot import *
connect()
# change the size or the loads and press Run
SIZE = 101
COUNTS = [10, 20, 30, 40, 50, 60, 70, 80, 90, 95, 98, 100]
def keys(how_many):
# the same made up marker numbers every time, 1000 to 9999
out = []
seed = 7
while len(out) < how_many:
seed = (seed * 1103515245 + 12345) % 2147483648
key = seed % 9000 + 1000
if key not in out:
out.append(key)
return out
for count in COUNTS:
table = [None] * SIZE
chosen = keys(count)
for key in chosen:
slot = key % SIZE
while table[slot] is not None:
slot = (slot + 1) % SIZE
table[slot] = key
total = 0
for key in chosen:
slot = key % SIZE
probes = 1
while table[slot] != key:
slot = (slot + 1) % SIZE
probes = probes + 1
total = total + probes
load = count / SIZE
plot("average slots looked at", total / count)
print("keys", count, "| load factor", round(load, 2),
"| average slots looked at", round(total / count, 2))
wait(0.3)
Each point on the chart is one load factor, the emptiest on the left. The line is almost flat up to about 0.7 and then climbs away. That is the number behind the usual rule: keep a hash table below about 70 percent full.
When a table passes its limit, the program resizes it: make a new array, usually about twice as big, and put every key in again. Every key has to be hashed again, because the slot depends on the size, so key MOD 101 and key MOD 211 are different answers. Resizing is slow, which is why it is done rarely and all at once, and it is the reason a hash table can promise fast look-up on average but not on any particular day.
A hash function that does not spread
The other thing that decides the cost is the hash function itself. Here are nine marker numbers that are all multiples of 10, put into a table of 10 slots and then into a table of 11.
The program
from bugbot import *
connect()
# change the sizes or the keys and press Run
SIZES = [10, 11]
KEYS = [10, 20, 30, 40, 50, 60, 70, 80, 90]
for size in SIZES:
table = [None] * size
total = 0
for key in KEYS:
slot = key % size
probes = 1
while table[slot] is not None:
slot = (slot + 1) % size
probes = probes + 1
table[slot] = key
total = total + probes
plot("size " + str(size), total)
print("size", size, "| key", key, "| hash", key % size,
"| stored in", slot, "| probes", probes)
wait(0.2)
print("size", size, "| slots looked at in total:", total)
Ten slots is a terrible size for these keys. Every key is a multiple of 10, so every key gives 0, every key collides, and the ninth key has to walk past eight full slots. Eleven slots is a good size for exactly the same keys, because 11 shares no factor with 10, so the remainders spread out and no key collides at all.
That is the reason hash tables are usually given a prime number of slots. Real keys come in patterns (every tenth marker, every record ending in 00, every name starting with S), and a table size that shares a factor with the pattern turns the pattern into a pile.
A good hash function:
- is quick, or the table loses the speed it was chosen for;
- is deterministic: the same key always gives the same slot, or nothing could ever be found again;
- spreads keys evenly over the slots, so that clusters stay small;
- always returns a valid index for the table.
For text keys, the usual method is to add up the character codes and take MOD size, often multiplying the running total by a small prime as it goes, so that "tar" and "rat" do not land in the same slot.
In Python
Python's dictionary is a hash table, and its hash() is the hash function.
seen = {} # a dictionary: keys to values
seen[23] = (40, 10) # marker 23 is at x 40, y 10
seen[7] = (90, 65)
print(seen[23]) # (40, 10), found without searching
print(7 in seen) # True
print(len(seen))
print(hash("ramp") % 11) # the same slot every time, in one run
seen[23] hashes the key, goes to the slot and returns the value, so it is O(1) on average. The dictionary resizes itself when it gets full, and Python looks after the collisions. A set works the same way and keeps only the keys, which is why if cell in visited in a search program is fast however many cells have been visited.
Where this is taught
- Hash tables is the full lesson: hashing functions, linear probing, chaining, and resizing.
- Dictionaries is the structure built on top of a hash table, and what a robot keeps in one.
- Arrays, records and tuples is the array a hash table is built in.
- Compression, encryption and hashing is the other meaning of hashing, for passwords and checking files.
- Big O notation and the Big O guide are where O(1) and O(n) come from, and the linear and binary search guide is what a hash table is faster than.
Questions
What is a hash table in simple terms?
An array, plus a rule that works out which slot an item belongs in from the item's key. Because the rule is the same when you store the item and when you look for it, finding an item takes one calculation and one look, instead of a search.
What is a hash function?
The rule that turns a key into a slot number. For whole numbers it is usually the remainder after dividing by the table size, key MOD size. For text it is usually the character codes added up, then MOD size. A good one is quick, always gives the same answer for the same key, and spreads keys evenly.
Why is a hash table O(1)?
Because the number of steps does not grow with the number of items. Hashing the key costs the same whether the table holds ten items or ten million, and going to a slot in an array costs the same as well. Only collisions add anything, and a table kept below about 70 percent full has few of them: on the demo above, an average of 1.33 slots looked at against a list search's 5.
What is a collision in a hash table?
Two different keys that hash to the same slot. There are always more possible keys than slots, so collisions cannot be avoided. On this page, keys 23 and 12 both hash to slot 1 in a table of 11.
How are collisions resolved?
Two ways. Open addressing puts the key somewhere else in the same array, usually the next free slot along, which is called linear probing; a search then follows the same path. Chaining keeps a list at each slot and adds the key to that list. Chaining copes better with a full table; open addressing keeps everything in one array and is usually faster while the table is not crowded.
What is the load factor of a hash table?
The number of keys stored divided by the number of slots. It is the one number that decides how much probing a table does. The demo on this page measures an average of 1.00 slots looked at at a load factor of 0.10, 1.86 at 0.69 and 5.22 at 0.89, which is why tables are usually resized once they pass about 0.7.
What happens when a hash table gets full?
It is resized: a bigger array is made, usually about double, and every key is hashed again and put into the new array, because the slot depends on the size. With open addressing the table cannot hold more keys than it has slots at all, so it must be resized before then. With chaining it can carry on, with longer and longer lists at each slot and worse and worse look-up.
Why are hash tables usually a prime number of slots?
Because real keys come in patterns, and a size that shares a factor with the pattern collapses it into a few slots. The demo on this page puts nine multiples of 10 into 10 slots and every one hashes to slot 0. The same keys in 11 slots each get a slot of their own.
What is the difference between a hash table and a dictionary?
A dictionary is the idea: a collection of key and value pairs that you can look things up in. A hash table is the usual way of building one. Python's dict, a Java HashMap and a C# Dictionary are all hash tables underneath.
What is a hash table used for?
Dictionaries and sets in most languages, the symbol table a compiler keeps of every name in your program, caches, database indexes, checking whether a word is in a dictionary, and, in a robot, any map from a name or a number to something else: marker 23 to a position, a command word to the function that runs it, a visited cell to the cell it was reached from.
Is a hash table on the A level Computer Science specification?
Yes, on all the main boards, and not at GCSE. AQA's A level (7517) covers the concept and uses of hash tables, simple hashing algorithms, collisions and rehashing (4.2.1.4 and 4.2.6.1). OCR's H446 lists hash tables among the data structures you must be able to create, traverse, add to and remove from (1.4.2). Eduqas covers hash tables and collisions in its data structures section (1.1).
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- A3.5 Hash tables Data structures, A level
- A3.6 Dictionaries Data structures, A level
- A3.1 Arrays, records and tuples Data structures, A level
- A7.9 Compression, encryption and hashing Data representation, A level
- A5.2 Big O notation Algorithms and complexity, A level