# Hash tables

> CIE A-Level Computer Science · 9618
> Source: https://www.owlsprep.com/study/cie-9618-u10-hash-tables/

Hash tables are high-performance array-based data structures that enable average O(1) search, insert and delete operations for key-value data. This guide explains hashing, collision resolution, performance, and common exam requirements.

**Prerequisites:** [Arrays](https://www.owlsprep.com/study/cie-9618-u10-arrays/); [Time complexity](https://www.owlsprep.com/study/cie-9618-u08-time-complexity/)

## Learning objectives

- Explain the structure and purpose of hash tables and hash functions
- Describe and apply common collision resolution techniques
- Calculate load factor and understand hash table performance
- Identify common pitfalls in hash table operations

## Hash Tables and Hash Functions

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.

**Hash Function** — 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.

*Notation:* $h(k)$

*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.

## Collision Resolution: Chaining

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.

**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

> **tip**
>
> In CIE exams, you can draw chaining as each array cell pointing to a vertical list of keys that share the index.

## Collision Resolution: Open Addressing (Linear Probing)

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.

**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]

> **warning**
>
> Primary clustering is a key disadvantage of linear probing: filled consecutive slots attract more collisions, increasing average search time.

## Performance and Load Factor

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.

**Load Factor** — The ratio of the number of stored entries to the total size of the hash table array: $\lambda = \frac{\text{Number of entries}}{\text{Table size}}$

*Notation:* $\lambda$

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$

## Common pitfalls

- **Wrong:** Forgetting to wrap around to the start of the array in linear probing when the end is reached
  - Why it fails: 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: 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:** Confusing chaining and open addressing, stating all keys are stored directly in the main array for chaining
  - Why it fails: Mixing up the core structure of the two collision resolution methods
  - Correct: Chaining uses linked lists in each array slot, open addressing stores all keys directly in the main array
- **Wrong:** Calculating load factor as (number of collisions) / (table size)
  - Why it fails: Misremembering the definition of load factor
  - Correct: Load factor is always the fraction of the table that is full: (number of stored entries) / (total table size)
- **Wrong:** Stating that hash table operations are always O(1) time complexity
  - Why it fails: Confusing average case with worst case complexity
  - Correct: Hash table operations are O(1) average case, but O(n) worst case if all keys hash to the same index
- **Wrong:** Stopping a linear probing search when you hit a non-target key
  - Why it fails: Misunderstanding how open addressing search works
  - Correct: Continue searching consecutive slots until you find the key or hit an empty slot (which means the key is not present)

## 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) |

## 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.

- [Programming](https://www.owlsprep.com/study/cie-9618-u11-overview/)
- [Programming fundamentals](https://www.owlsprep.com/study/cie-9618-u11-programming-fundamentals/)
- [Control flow structures](https://www.owlsprep.com/study/cie-9618-u11-control-flow-structures/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u10-hash-tables/