Hash tables

CIE A-Level Computer Science· Unit 10: Data types & structures· 15 min read

1. Hash Tables and Hash Functions★★☆☆☆⏱ 4 min

A hash table stores key-value pairs, using a special hash function to map each input key to an index in the underlying array. This index directly tells us where to store the corresponding value, enabling very fast access.

📘 Definition

Hash Function

$h (k)$

A function that takes an input key (string or number) and converts it to a fixed-size numerical hash value, used as an index in the hash table array.

Example:

For a table of size 10, $h (k) = k mod 10$

📐 Worked Example

Calculate hash indices for the keys [12, 25, 31, 48, 52] for a hash table of size 10, using $h (k) = k mod 10$ .

1
Calculate hash for 12: $12 mod 10 = 2$
2
Calculate hash for 25: $25 mod 10 = 5$
3
Calculate hash for 31: $31 mod 10 = 1$
4
Calculate hash for 48: $48 mod 10 = 8$
5
Calculate hash for 52: $52 mod 10 = 2$
6
We now have a collision: two keys (12 and 52) hash to the same index 2. We will resolve this collision in later sections.

2. Collision Resolution: Chaining★★☆☆☆⏱ 3 min

A collision occurs when two different keys hash to the same index. Chaining is the simplest collision resolution method, where each array slot stores a dynamic collection of all keys that hash to that index.

📘 Definition

Chaining

A collision resolution method where each index in the hash table array stores a linked list (or other dynamic structure) of all keys that hash to that index.

📐 Worked Example

Resolve the collision of 12 and 52 at index 2 (from the previous example) using chaining, table size 10.

1
Each array element acts as the head of a linked list. After inserting 12, the linked list at index 2 is [12].
2
When inserting 52 (which also hashes to 2), add 52 to the end of the linked list at index 2.
3
To search for 52: hash to get index 2, then traverse the linked list until 52 is found.
4
Final state of index 2: Head → 12 → 52 → null

3. Collision Resolution: Open Addressing (Linear Probing)★★★☆☆⏱ 5 min

Open addressing is an alternative collision resolution method where all keys are stored directly in the main hash table array. If a collision occurs, you probe (search) for the next available empty slot to store the new key. CIE most commonly examines linear probing.

📘 Definition

Linear Probing

An open addressing method where if a collision occurs at hash index $h$ , you check slots $h + 1, h + 2, ...$ (wrapping around to the start of the array if needed) until you find an empty slot.

📐 Worked Example

Insert the keys [12, 25, 31, 48, 52] into a hash table of size 10, using $h (k) = k mod 10$ and linear probing.

1
Insert 12: h=2, slot 2 is empty → store 12 at index 2
2
Insert 25: h=5, slot 5 is empty → store 25 at index 5
3
Insert 31: h=1, slot 1 is empty → store 31 at index 1
4
Insert 48: h=8, slot 8 is empty → store 48 at index 8
5
Insert 52: h=2, slot 2 is full → check next slot 3, which is empty → store 52 at index 3
6
Final table state: [empty, 31, 12, 52, empty, 25, empty, empty, 48, empty]

4. Performance and Load Factor★★★☆☆⏱ 3 min

The performance of a hash table depends on its load factor, which measures how full the table is. When the load factor exceeds a threshold, the table is resized (rehashed) to maintain good performance.

📘 Definition

Load Factor

$λ$

The ratio of the number of stored entries to the total size of the hash table array: $λ = \frac{Number of entries}{Table size}$

Typical thresholds are 0.7 for chaining and 0.5 for open addressing. Average time complexity for search, insert, and delete is O(1), while worst case is O(n) when all keys hash to the same index.

📐 Worked Example

What is the load factor of the linear probing example above, with 5 entries in a size 10 array? Is resizing needed if the threshold for open addressing is 0.5?

1
Substitute values into the load factor formula:
2
$\lambda = \frac{5}{10} = 0.5$
3
If the threshold is 0.5, resizing is triggered if load factor is greater than or equal to the threshold, so resizing will be performed.
4
After resizing to a new array of size 20, the new load factor is $\frac{5}{20} = 0.25$

5. Common Pitfalls

Wrong move:

Forgetting to wrap around to the start of the array in linear probing when the end is reached

Why:

Many candidates stop searching for empty slots once they reach the end of the array, even if there are empty slots at the start

Correct move:

Always continue searching from index 0 after reaching the end of the array until you find an empty slot or confirm the table is full

Wrong move:

Confusing chaining and open addressing, stating all keys are stored directly in the main array for chaining

Why:

Mixing up the core structure of the two collision resolution methods

Correct move:

Chaining uses linked lists in each array slot, open addressing stores all keys directly in the main array

Wrong move:

Calculating load factor as (number of collisions) / (table size)

Why:

Misremembering the definition of load factor

Correct move:

Load factor is always the fraction of the table that is full: (number of stored entries) / (total table size)

Wrong move:

Stating that hash table operations are always O(1) time complexity

Why:

Confusing average case with worst case complexity

Correct move:

Hash table operations are O(1) average case, but O(n) worst case if all keys hash to the same index

Wrong move:

Stopping a linear probing search when you hit a non-target key

Why:

Misunderstanding how open addressing search works

Correct move:

Continue searching consecutive slots until you find the key or hit an empty slot (which means the key is not present)

6. Quick Reference Cheatsheet

Concept	Key Fact
Hash function	Maps key to array index
Collision	Two keys hash to the same index
Chaining	Each slot has a linked list of entries
Linear Probing	Check next empty slot, wrap around
Load Factor	Entries ÷ Table Size, threshold 0.5-0.7
Rehashing	Resize table when load factor exceeds threshold
Average time complexity	Search/Insert/Delete = O(1)
Worst time complexity	Search/Insert/Delete = O(n)

7. Frequently Asked

Do I need to write my own hash function in the exam?

No, you will almost always be given a hash function to apply. You only need to use it to calculate indices and resolve collisions.

What is the difference between average and worst case hash table performance?

With a good hash function, average case for all operations is O(1). Worst case is O(n), when all keys hash to the same index.

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 12
Collision resolution with chaining
2023 · 11
Linear probing insertion question
2021 · 13
Load factor calculation

Going deeper

syllabusOfficial CIE 9618 SyllabusCheck page 32 for unit 10 content

What's Next

Hash tables are a core data structure tested regularly in CIE A-Level Computer Science, appearing in both paper 1 data structure questions and paper 2 problem-solving tasks. They are widely used in real-world applications for database indexing, caching, and implementing hash sets and dictionaries. Mastering how hashing and collision resolution work provides a strong foundation for understanding more complex data structures. After completing this topic, you can move on to learning about other common data structures that build on your existing knowledge of arrays and dynamic storage.