All subjects · Computer Science · WCP04 Advanced Practical Programming and Problem-solving

Hash tables and hash algorithms

Edexcel IAL Computer Science · WCP04 Advanced Practical Programming and Problem-solving

A hash table stores key-value pairs so that a value can be found almost instantly from its key. A hash algorithm turns the key into the index of the slot where the pair is stored.

Practise this in the app: instant marking and a fix for every mistake. Free, no email needed to start.

Practise this lesson

The idea

The table is a fixed-length list of slots.
To insert, find or remove a key, calculate index = hash(key) and go straight to that slot: no searching.
A collision happens when two different keys hash to the same index. The next lesson handles collisions; this lesson's table just reports them.
The load factor is items / slots. As it rises, collisions become more likely.

Hash algorithms

A good hash algorithm is deterministic (the same key always gives the same index), fast, and spreads keys evenly over the slots, using every part of the key.

Sum of character codes mod size: simple, but anagrams such as CAT and ACT always collide.
Polynomial (weighted) hash: h = h * 31 + ord(ch) for each character, mod size, so position matters.
Modulo division for integer keys: key % size; a prime table size spreads keys better.
Folding (split a long key into parts and add them) and mid-square (square the key and take the middle digits) are other methods for numbers.

Do not rely on Python's built-in hash() for strings in an exam answer: it is randomised each time Python starts, so indexes change between runs.

def hash_sum(key, size):
    return sum(ord(ch) for ch in key) % size

def hash_poly(key, size):
    h = 0
    for ch in key:
        h = (h * 31 + ord(ch)) % size
    return h

for word in ["CAT", "ACT", "DOG"]:
    print(word, hash_sum(word, 11), hash_poly(word, 11))

Output:

CAT 7 2
ACT 7 1
DOG 9 9

A hash table class

An Entry object holds a key and value; the table holds references to entries, with None for an empty slot.

class Entry:
    def __init__(self, key, value):
        self.key = key
        self.value = value

class HashTable:
    def __init__(self, size):
        self.size = size
        self.slots = [None] * size

    def hash(self, key):
        return sum(ord(ch) for ch in key) % self.size

    def insert(self, key, value):
        i = self.hash(key)
        slot = self.slots[i]
        if slot is None or slot.key == key:
            self.slots[i] = Entry(key, value)
            return True
        return False                     # collision: see the next lesson

    def find(self, key):
        slot = self.slots[self.hash(key)]
        if slot is not None and slot.key == key:
            return slot.value
        return None

    def remove(self, key):
        i = self.hash(key)
        if self.slots[i] is not None and self.slots[i].key == key:
            self.slots[i] = None
            return True
        return False

    def traverse(self):
        return [(i, s.key, s.value) for i, s in enumerate(self.slots) if s is not None]

Using it

# Entry and HashTable classes as above

stock = HashTable(7)
for item, qty in [("pen", 40), ("ink", 12), ("pad", 25)]:
    print(item, stock.hash(item), stock.insert(item, qty))
stock.insert("pen", 38)
print(stock.find("pen"), stock.find("cap"), stock.remove("ink"))
print(stock.traverse())

Output:

pen 1 True
ink 0 True
pad 1 False
38 None True
[(1, 'pen', 38)]

Inserting an existing key replaces its value. Traversal walks every slot in index order, which is not the order of insertion.

Worked example

Using the sum-of-codes hash with 11 slots, find the index for the key 'BEE'. (ord('B') = 66, ord('E') = 69)

Sum = 66 + 69 + 69 = 204
Index = 204 % 11 = 6

Answer: BEE is stored in slot 6.

Key idea: hash(key) gives the slot index directly; good hashes are deterministic, fast and even; sum of codes makes anagrams collide, a polynomial hash does not; prime table sizes help; load factor = items / slots.

Check yourself

Using `sum(ord(ch) for ch in key) % 13`, find the index for the key 'AB'. (ord('A') = 65, ord('B') = 66)
Show answer
1. 65 + 66 = 131; 131 % 13 = 1.
Integer keys are hashed with `key % 17`. Which slot does key 1000 go in?
Show answer
14. 1000 = 58 x 17 + 14, so the slot is 14.
hash_sum and hash_poly are the functions from the lesson. What does this print? ```python def hash_sum(key, size): return sum(ord(ch) for ch in key) % size def hash_poly(key, size): h = 0 for ch in key: h = (h * 31 + ord(ch)) % size return h print(hash_sum("STOP", 11) == hash_sum("POTS", 11), hash_poly("STOP", 11) == hash_poly("POTS", 11)) ```
Show answer
True False. The sum hash ignores order, so the anagrams collide (True); the polynomial hash weights position, so here they differ (False). Output: `True False`
The Entry and HashTable classes from the lesson are included in the code below. What does this print? ```python class Entry: def __init__(self, key, value): self.key = key self.value = value class HashTable: def __init__(self, size): self.size = size self.slots = [None] * size def hash(self, key): return sum(ord(ch) for ch in key) % self.size def insert(self, key, value): i = self.hash(key) slot = self.slots[i] if slot is None or slot.key == key: self.slots[i] = Entry(key, value) return True return False # collision: see the next lesson def find(self, key): slot = self.slots[self.hash(key)] if slot is not None and slot.key == key: return slot.value return None def remove(self, key): i = self.hash(key) if self.slots[i] is not None and self.slots[i].key == key: self.slots[i] = None return True return False def traverse(self): return [(i, s.key, s.value) for i, s in enumerate(self.slots) if s is not None] t = HashTable(5) t.insert("a", 1) t.insert("f", 2) print(t.hash("a"), t.hash("f"), t.find("f")) ```
Show answer
2 2 None. ord('a') = 97 and ord('f') = 102 both give 2 mod 5, so 'f' collides; insert returns False and find('f') returns None. Output: `2 2 None`
A hash table has 40 slots and holds 30 items. What is its load factor?
Show answer
0.75. Load factor = items / slots = 30 / 40 = 0.75.
Which property is essential for any hash algorithm used by a hash table?
- The same key must always produce the same index
- Every key must produce a different index
- The index must be larger than the key
- It must use random numbers
Show answer
The same key must always produce the same index. If the index changed, a stored item could never be found again. Different keys sharing an index (collisions) are allowed and handled.
Why should an exam answer use its own hash function rather than Python's `hash()` on strings?
- hash() does not work on strings
- hash() always returns 0
- String hashes from hash() are randomised each time Python starts, so indexes change between runs
- hash() is not allowed in Python 3
Show answer
String hashes from hash() are randomised each time Python starts, so indexes change between runs. Python salts string hashes for security, so results are not repeatable between runs. Your own function is predictable and testable.
Why is finding a key in a hash table usually faster than in an unsorted list?
- Hash tables keep items in sorted order
- Hash tables use binary search
- Hash tables store fewer items
- The hash gives the slot directly, so no item-by-item search is needed
Show answer
The hash gives the slot directly, so no item-by-item search is needed. Calculating the index takes the same time whatever the table size (unless collisions build up).

Practise with instant feedback

Sources

Last updated 8 November 2026. Spotted a mistake? Tell us.