AQA 7517 · Paper 1 · 4.2.7

Hash
Tables

AQA A-Level Computer Science · Section 4.2 Fundamentals of Data Structures

WHAT YOU'LL LEARN

Hash functions · Collision handling · Chaining · Linear probing · O(1) average

AQA SPEC LINK

4.2.7 — Hash tables as data structures

Hash Table Concept

What is a Hash Table?

A hash table maps keys to array positions using a hash function. This enables near O(1) average time for insert, search, and delete.

TYPICAL HASH FUNCTION (for integers)

index ← key MOD tableSize

Example: Insert key 43 into a table of size 10 → 43 MOD 10 = 3 → store at index 3

Worked Example

Hashing Example (Size 7)

Insert keys: 15, 24, 36, 8, 22 using key MOD 7

Key	key MOD 7	Index
15	15 MOD 7 = 1	1
24	24 MOD 7 = 3	3
36	36 MOD 7 = 1	COLLISION!
8	8 MOD 7 = 1	COLLISION!
22	22 MOD 7 = 1	COLLISION!

Collisions

Collision Handling

A collision occurs when two keys hash to the same index. Two main strategies:

1. CHAINING (open hashing)

Each table slot holds a linked list. Colliding keys are added to the list at that index. No theoretical limit. Easy to implement.

2. LINEAR PROBING (open addressing)

If index i is full, try i+1, i+2, … (wrapping round with MOD). All data stays in the table. Can cause clustering.

Linear Probing

Linear Probing Example

Table size 7. Insert 15 (→1), then 36 (→1 occupied, try 2). Next probe: index ← (hash + 1) MOD size

Index	Contents after inserts
0	—
1	15 (hashed here)
2	36 (probed to 2)
3	24 (hashed here)
4	8 (probed to 4)
5	22 (probed to 5)
6	—

Time Complexity

Hash Table Performance

Operation	Average Case	Worst Case
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

Worst case O(n) happens when all keys hash to the same bucket (degenerate case). A good hash function distributes keys evenly to keep average-case O(1).

Chaining vs Probing

Comparing Collision Strategies

CHAINING

No clustering

Never full (linked list grows)

Easy deletion

Extra memory for pointers

LINEAR PROBING

Better cache performance

No pointer overhead

Primary clustering

Deletion is complex

Applications

Real-World Uses of Hash Tables

Symbol tables in compilers — fast variable lookup

Password storage — store hash(password), not plaintext

Dictionaries/maps — Python dict, Java HashMap use hash tables

Caches — web caches use hashes of URLs as keys

Database indexing — fast record lookup by key field

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

A hash table of size 11 uses the function: index = key MOD 11.
(a) Calculate the index for key 58. [1]
(b) Key 47 also hashes to the same index. Describe how linear probing would resolve this collision. [2]
(c) State ONE disadvantage of using linear probing. [1]

[4 marks]

1 mark

(a) 58 MOD 11 = 3

2 marks

(b) 47 MOD 11 = 3 (collision). Try index 4. If index 4 is empty, store at 4. Otherwise try 5, 6… wrapping around with MOD 11.

1 mark

(c) Primary clustering — long runs of filled slots slow down lookups OR table can become full requiring rehashing

Summary

Key Points to Remember

Hash function maps key → index; typical: key MOD tableSize

Collision = two keys map to same index — must be resolved

Chaining — linked list at each slot; Linear probing — next free slot

Average-case O(1) for insert/search/delete — faster than arrays for lookups

Worst case O(n) if all keys collide

🎉 Lesson complete — move to the quiz!