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, 4 written answers and 2 Python tasks. 36 marks, about 50 to 60 minutes.
Series: H446 1.4.2 · Data structures, part 11 of 14.
Shared by Coding PathwayVerified teacher
- 18 cells
- About 60 minutes
- CC BY-SA 4.0
- Shared 31 Aug 2026
- Updated 1 Oct 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 to find an item from its ID without searching every stored record. A hash function converts the key into a valid bucket or address in a hash table. Different keys can produce the same address, so the implementation must also have a collision policy.
By the end, you will be able to
- apply a simple hash function using modulo;
- explain and resolve collisions;
- create, search, add and remove entries;
- distinguish hash-table addressing from cryptographic hashing.
Bucket and collision model
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.
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 2, replacing key 7
- CIndex 3
- DA chain attached to index 2
What is a collision?
- AA key is encrypted twice
- BThe table has no empty buckets
- CA search visits one item
- DTwo keys produce the same bucket index
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.
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.
def lookup(table, key):
bucket_index = key % len(table)
bucket = table[bucket_index]
for stored_key, value in bucket:
if ...:
return value
return NoneIndependent 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.
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 FalseExplain 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.
Explain how table size and many collisions can affect lookup performance.
Use chain length and work.
Students type their answer here.
An open-addressed table stores key 12 at index 3 after a collision at index 2. Key 7, which occupied index 2, is later removed. Explain why index 2 should contain a deleted marker rather than be made never-used empty, and describe how a search for key 12 proceeds.
Use the same linear-probing policy that inserted the key.
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.
Review your work
Check that the hash produces a bucket position and that lookup still compares the stored keys.