Hash tables: hashing, collisions, load factor and rehashing

Structure and hashing

A hash table is an array of slots (buckets). A hash function turns a key into a slot index. A common one for whole-number keys is key mod table size. For text keys, add the character codes and then take mod.

A good hash function is quick to calculate, spreads keys evenly and always gives the same index for the same key. A prime table size helps spread keys.

Collisions

A collision happens when two keys hash to the same slot.

• Open addressing with linear probing: if the slot is taken, try the next slot (wrapping round to 0 at the end) until an empty one is found. Searching follows the same path; it stops at the key or at an empty slot.
• Chaining: each slot holds a linked list; colliding items are added to that list.

Deleting with linear probing: the slot is marked 'deleted' (a tombstone) rather than emptied, so later searches do not stop early.

Keys 23, 14, 9, 36, 45, 31 inserted with key mod 11 and linear probing

Load factor and rehashing

Load factor = number of items / number of slots. As it rises, collisions and probe lengths rise, and lookups slow down.

When the load factor passes a chosen threshold (0.7 is common), the table is rehashed: a larger table is created (often about double, with a prime size) and every item is reinserted using the new size, because key mod new size gives new positions.

Operations and trade-offs

• Insert: hash, probe if needed, store.
• Search: hash, compare, probe until found or an empty slot.
• Delete: search, then mark as deleted (open addressing) or remove from the chain.
• Traverse: visit every slot in index order (keys are not in sorted order).

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

    def hash(self, key):
        return key % self.size

    def insert(self, key):          # assumes the table is not full
        i = self.hash(key)
        while self.slots[i] is not None:
            i = (i + 1) % self.size  # linear probing, wrapping round
        self.slots[i] = key

    def search(self, key):
        i = self.hash(key)
        for _ in range(self.size):
            if self.slots[i] is None:
                return -1            # empty slot: not in the table
            if self.slots[i] == key:
                return i
            i = (i + 1) % self.size
        return -1

Benefits: average O(1) insert, search and delete. Drawbacks: collisions slow it down (worst case O(n)); wasted empty slots; no ordering; rehashing is costly when it happens.

Worked example

Insert 23, 14, 9, 36, 45, 31 into an 11-slot table using key mod 11 and linear probing.

1. 23 mod 11 = 1: slot 1. 14 mod 11 = 3: slot 3. 9 mod 11 = 9: slot 9.
2. 36 mod 11 = 3: taken, so try 4: slot 4.
3. 45 mod 11 = 1: taken, try 2: slot 2.
4. 31 mod 11 = 9: taken, try 10: slot 10.

Answer: Slots 1: 23, 2: 45, 3: 14, 4: 36, 9: 9, 10: 31.

Check yourself

1. Using key mod 13, what is the hash value of key 58?
   Show answer

   6. 58 = 4 x 13 + 6, so index 6.

2. In the table built from 23, 14, 9, 36, 45, 31 (key mod 11, linear probing), key 20 is inserted next. In which slot is it stored?
   Show answer

   0. 20 mod 11 = 9; slots 9 and 10 are full; wrap to 0, which is empty.

3. What is the load factor of an 11-slot table holding 6 items? Give your answer to 2 decimal places.
   Show answer

   0.55. 6 / 11 = 0.5455.

4. A 7-slot table is rehashed into a 17-slot table using key mod size. In which slot of the new table does key 40 go (assuming no collision)?
   Show answer

   6. 40 mod 17 = 6.

5. A hash function adds the ASCII codes of a string's characters and takes the result mod 10. 'A' = 65, 'B' = 66, 'C' = 67. What is the hash of 'CAB'?
   Show answer

   8. 67 + 65 + 66 = 198; 198 mod 10 = 8.

6. What is a collision in a hash table?
   • Two keys are identical
   • Two different keys produce the same hash index
   • The table is full
   • A key has no hash value
   Show answer

   Two different keys produce the same hash index. Collisions are unavoidable when keys outnumber slots or are uneven.

7. Why is a deleted slot marked 'deleted' rather than set to empty when linear probing is used?
   • It saves memory
   • It makes the hash function faster
   • Empty slots cannot be reused
   • An empty slot would stop later searches early, so items stored past it would not be found
   Show answer

   An empty slot would stop later searches early, so items stored past it would not be found. Searches stop at empty slots, so the probe chain must be kept.

8. Why is rehashing needed?
   • Hash values expire after a time
   • Keys must be sorted regularly
   • As the load factor rises, collisions increase and operations slow down, so a larger table restores performance
   • The hash function stops working when the table is half full
   Show answer

   As the load factor rises, collisions increase and operations slow down, so a larger table restores performance. Rehashing into a bigger table lowers the load factor.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

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