Community resourceWorksheet

OCR H446 1.4.2 Hash tables and collisions

Part 11 of 14 · H446 1.4.2 · Data structures

Hash tables buy fast lookup from a key, provided the collision policy is declared and then followed consistently. Set in a community equipment register, this H446 1.4.2 worksheet covers bucket calculation, chaining and linear probing, and draws the boundary between a hash table's bucket function and the cryptographic hashing of a password.

Students will:

  • apply a simple modulo hash function to place keys into buckets
  • resolve collisions under a declared policy such as separate chaining or linear probing
  • implement lookup, insertion, update and removal for a chained table
  • separate a bucket function from a password hash despite the shared terminology
  • explain how table size and frequent collisions affect lookup performance

Inside: 9 explanation cells, 2 multiple-choice questions, 1 fill-in-the-blanks cell, 3 written answers and 2 Python tasks. 32 marks, about 45 to 55 minutes.

Series: H446 1.4.2 · Data structures, part 11 of 14.

Shared by Coding PathwayVerified teacher

  • 17 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 15 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Hash tables and collisions

A community equipment register needs quick lookup from an item ID. A hash table computes a bucket from a key.

By the end, you will be able to

  • apply a simple hash function;
  • explain and resolve collisions;
  • create, search, add and remove entries;
  • distinguish a hash table from cryptographic hashing.

Reactivate: modulo maps an integer into a fixed range.

Bucket and collision model

Hash table with separate chainingkey 1717 MOD 5 = 2012341742collision chainSearch hashes to one bucket, then checks keys in that bucket.

17 and 42 both map to bucket 2 because each has remainder 2 when divided by 5. A collision is not an error: separate chaining stores both key/value pairs in the bucket and compares keys during lookup.

Worked operations

add(17,A): hash to 2, append pair. add(42,B): hash to 2, detect collision, append pair. search(42): hash directly to 2, compare 17 then 42. remove(17): delete only pair with key 17; bucket 2 and key 42 remain.

Invariant: each stored key is in the bucket selected by the current hash function.

Collision policies must stay consistent

Separate chaining keeps a collection of key/value pairs at each bucket. Open addressing with linear probing checks the calculated position, then successive table positions (wrapping at the end) until it finds the key or a valid empty slot. An overflow table stores collided items separately and is searched after the calculated position.

A search or removal must follow the same policy used during insertion. With open addressing, simply treating a deleted position as never-used can stop a later search too early, so implementations use an appropriate deleted marker or rebuild policy. Larger, less crowded tables generally reduce collisions but use more memory.

Multiple choice1 mark

Keys 7 and 12 both hash to index 2 in a five-slot open-addressed table. Index 2 stores key 7 and index 3 is empty. Where is key 12 inserted by linear probing?

  • AIndex 0
  • BIndex 3
  • CIndex 2, replacing key 7
  • DA chain attached to index 2
Multiple choice1 mark

What is a collision?

  • AA key is encrypted twice
  • BThe table has no empty buckets
  • CTwo keys produce the same bucket index
  • DA search visits one item

Guided bucket table

With key MOD 5, place 7, 12, 3 and 19. Record bucket and chain order. Then search 12 and remove 7 without deleting 12.

Written answer5 marks

Apply the guided operations and give all non-empty buckets after removal.

Keep insertion order within chains.

Students type their answer here.

Independent transfer: chained table

Implement lookup(table,key). table is a list of buckets; each bucket is a list of (key,value) tuples. Use key % len(table). Return value or None.

Coding task5 marks
def lookup(table, key):
    bucket_index = key % len(table)
    bucket = table[bucket_index]
    for stored_key, value in bucket:
        if ...:
            return value
    return None

Independent mutation: add and remove in a chain

Implement put(table,key,value) so an existing key is updated and a new key is appended to its hash bucket. Implement remove_key(table,key) so only the matching pair is removed. Return True when removal occurs and False otherwise.

Coding task8 marks
def put(table, key, value):
    bucket = table[key % len(table)]
    for index, pair in enumerate(bucket):
        if pair[0] == key:
            bucket[index] = ...
            return table
    # No existing key was found.
    ...
    return table

def remove_key(table, key):
    bucket = table[key % len(table)]
    for index, pair in enumerate(bucket):
        if pair[0] == key:
            ...
            return True
    return False
Written answer4 marks

Explain why a hash table’s bucket function and a password cryptographic hash have related terminology but different purposes.

Compare lookup placement with one-way verification/security.

Students type their answer here.

Written answer3 marks

Explain how table size and many collisions can affect lookup performance.

Use chain length and work.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks5 marks
A hash function maps a key to a completion 1. Two different keys mapped to the same position cause a completion 2. Separate completion 3 stores colliding pairs together. Open addressing may use linear completion 4 to check later slots. Search and removal must follow the same collision completion 5 used for insertion.

Review your work

Check that the hash produces a bucket position and that lookup still compares the stored keys.