AQA A-Level Computer Science (7517)

## Learning Outcomes

- Understand how a hash table stores and retrieves data using keys and array indices
- Apply simple hashing algorithms to integers and strings step by step
- Explain what a collision is and why collisions happen
- Describe how collisions can be handled using rehashing, especially linear probing
- Distinguish between a hash value and the final index in the table
- Evaluate when hash tables are useful and what their limitations are in exam answers

## AQA A-Level Computer Science (7517) Syllabus

For the AQA A-Level Computer Science (7517), you are expected to understand hash tables as part of data structures, with a focus on the following syllabus points:

- Know that a **hash table** stores or locates data by converting a key into an index in an array
- Understand that a **hash function** maps a key to a numerical value, often using modulo to keep it within table bounds
- Be able to apply simple hashing algorithms to numbers and strings
- Know what is meant by a **collision**, where two different keys map to the same index
- Understand how collisions are handled using **rehashing**
- Recognise that hash tables are used for fast lookup by key, such as usernames, IDs, or dictionary entries
- Explain why the choice of hash function affects efficiency

## Test Your Knowledge

_Attempt these questions before reading this article. If you find some difficult or cannot remember the answers, look more closely at that area during your revision._

1. What is the difference between a key, a hash value, and an index?
2. How do you calculate a table position using modulo?
3. What is a collision in a hash table?
4. How does linear probing deal with a collision?
5. Why can a poor hash function make a hash table much less efficient?

## Introduction

A hash table is one of the most useful data structures for fast lookup. Instead of searching through each item one by one, a program uses a **key** and a **hash function** to jump to a likely storage position straight away. That is why hash tables are often linked with direct access.

For AQA Paper 1, you need more than a short definition. You need to be able to trace how items are inserted, apply a simple hashing algorithm correctly, and explain what happens when two items try to use the same location. Many students lose marks by knowing the idea but mixing up the stages.

> **Key Term: hash table**
> A data structure, usually implemented using an array, that stores or locates data by converting a key into an index.

### How hash tables work

A hash table usually uses an underlying array. Each item has a **key**, and the key is passed to a **hash function**. The result is turned into an array position, often by using modulo.

This gives a common pattern:

- take the key
- apply the hash function
- calculate an index
- store or retrieve the item from that array slot

Why this matters: arrays support fast direct access if you already know the index. The hash function is the step that turns a meaningful key, such as a student ID or username, into that index.

> **Key Term: key**
> The value used to identify an item in a hash table and to calculate where it should be stored.
>
> **Key Term: hash function**
> An algorithm that converts a key into a numerical value or index.

A common number-based method is:

`index = key MOD tableSize`

If the table size is 10:

- 25 MOD 10 = 5, so item 25 goes to index 5
- 37 MOD 10 = 7, so item 37 goes to index 7
- 102 MOD 10 = 2, so item 102 goes to index 2

The modulo operation is used because array indices must stay within the table bounds. If the table has size 10, valid indices are 0 to 9.

A point students often miss is the difference between the **hash value** and the final **index**. Sometimes the hash function first produces a large value, then modulo reduces it to a valid table position. In simple questions, these may be treated as the same final result, but you should still understand the stages.

For strings, a common school-level method is to add ASCII values of the characters and then take modulo table size.

Worked example:

Hash the string `CAB` into a table of size 11.

- C = 67
- A = 65
- B = 66

Total ASCII value:

`67 + 65 + 66 = 198`

Now apply modulo:

`198 MOD 11 = 0`

So `CAB` is stored at index 0.

Here is AQA-style pseudocode for that process:

```text
hash ← 0
FOR i ← 0 TO LEN(word) - 1
    hash ← hash + CHAR_TO_CODE(word[i])
NEXT i
index ← hash MOD tableSize
```

Why this works: every string is turned into a number, and every number can be reduced to a valid array index.

Why this can be weak: strings with the same letters in a different order produce the same total. That means anagrams often collide.

For example, in a table of size 10:

- `DOG` = 68 + 79 + 71 = 218, so index 8
- `GOD` = 71 + 79 + 68 = 218, so index 8

Different keys, same index. That is a collision.

> **Key Term: index**
> The array position where an item is stored or searched for in a hash table.
>
> **Test Tip:** In exam questions, show every step of the calculation. Do not jump straight from the key to the final slot. Marks are often awarded for the method as well as the answer.

### Collisions and why they happen

A collision happens when two different keys are mapped to the same index. This is normal in hash tables. It is not a sign that the structure is broken.

> **Key Term: collision**
> A situation where two different keys produce the same index in a hash table.

Why collisions happen:

1. There are usually more possible keys than table slots.
2. A simple hash function may not spread values evenly.
3. As the table gets fuller, free spaces become harder to find.

Suppose a table has 11 slots and uses:

`index = key MOD 11`

Insert these values: 78, 55, 34, 19, 29

Calculate indices:

- 78 MOD 11 = 1
- 55 MOD 11 = 0
- 34 MOD 11 = 1
- 19 MOD 11 = 8
- 29 MOD 11 = 7

Now place them in the array:

- 55 goes in slot 0
- 78 goes in slot 1
- 34 also wants slot 1, so a collision occurs
- 19 goes in slot 8
- 29 goes in slot 7

The collision is caused by 34 and 78 both mapping to index 1.

A common wrong answer is to say a collision means "the same value appears twice". That is not precise enough. The issue is not duplicate data. The issue is two different keys producing the same hashed address.

A poor hash function increases collisions. For example, hashing film titles only by length is easy to compute, but many titles will have the same length. That means many collisions and poor performance.

The aim of a good hash function is to spread items as evenly as possible across the table. That reduces the number of collisions and keeps access fast on average.

The fullness of the table matters too. If the table is almost full, even a decent hash function will still lead to more probing. In practice, fuller tables are slower because more collisions occur.

> **Key Term: modulo**
> An operation that returns the remainder after division and is often used to keep a hash index within table size.
>
> **Test Tip:** If asked why a hash table is suitable, do not just say "it is fast". Say that the key is converted into an index, allowing direct access on average, provided collisions are limited.

### Collision handling using rehashing

The AQA wording says collisions are handled using **rehashing**. In school-level questions, this usually means trying another position after a collision rather than giving up.

> **Key Term: rehashing**
> The process of finding another place for an item when a collision occurs; in some contexts it can also mean rebuilding the table and hashing all items again.

That definition matters because the word is used in two related ways:

- in many A-level questions, it means using another placement attempt after a collision
- in wider computer science, it can also mean resizing the table and hashing all items again

For your exam, follow the wording of the question carefully. If you are given a simple table insertion task, rehashing usually means trying a new slot.

The clearest example is **linear probing**.

> **Key Term: linear probing**
> A collision resolution method where the program checks the next slot, then the next, until an empty slot is found.

Linear probing follows a simple rule:

- calculate the home index
- if occupied, check index + 1
- if still occupied, check the next
- wrap around to the start if needed

A common formula is:

`nextIndex = (index + 1) MOD tableSize`

Worked example:

Table size = 10  
Hash rule: `index = key MOD 10`

Insert 25, 35, 15

Step 1: insert 25  
`25 MOD 10 = 5`  
Slot 5 is empty, so store 25 at 5.

Step 2: insert 35  
`35 MOD 10 = 5`  
Slot 5 is occupied by 25, so probe next slot.  
Slot 6 is empty, so store 35 at 6.

Step 3: insert 15  
`15 MOD 10 = 5`  
Slot 5 occupied  
Slot 6 occupied  
Slot 7 empty  
Store 15 at 7.

Final table positions:

- 25 at 5
- 35 at 6
- 15 at 7

This method is easy to implement, which is why it appears often in teaching examples. But it has a weakness: it creates runs of occupied cells, called clustering. Once a block forms, more items are likely to join that block, causing longer searches.

> **Key Term: open addressing**
> A method of collision resolution where all items remain inside the table and alternative slots are searched when a collision occurs.

Linear probing is one form of open addressing. Another possible probing rule is to skip by 3 each time, or use increments such as 1, 3, 5, 7. The exact method can vary, but the aim stays the same: find a free slot while reducing repeated collisions.

Some contexts also mention **separate chaining**.

> **Key Term: separate chaining**
> A collision resolution method where each index stores a collection of items, so multiple items can be kept at the same index.

In separate chaining, a slot might hold a linked list or another container of entries. That means colliding items stay at the same index but are stored in a small collection. This is useful for comparison, but for AQA questions you should treat rehashing and probing as the main examinable method unless the question states otherwise.

There is another meaning of rehashing that appears in textbooks: if the table is too full or the available hash values are not enough, the table can be expanded and all existing items can be hashed again into the larger table. This can reduce future collisions, but it is a bigger operation than simple linear probing.

For example, if both `sauce` and `cause` are hashed by ASCII total modulo 6, they produce the same result. A very small table gives too few possible indices. Resizing the table and recalculating all positions gives more room and usually fewer collisions.

### Searching, uses, and exam evaluation

Searching in a hash table must follow the same collision-handling rule used during insertion. This is a key idea.

If linear probing was used to insert an item, then linear probing must also be used to search for it.

Search process with linear probing:

1. Apply the hash function to the key.
2. Check the resulting slot.
3. If the item is there, return it.
4. If the slot is empty, the item is not in the table.
5. If another item is there, continue probing until the item is found or a genuinely empty slot is reached.

Worked example:

Suppose a table size of 10, hash rule `key MOD 10`, and values already stored are:

- 25 at 5
- 35 at 6
- 15 at 7

Search for 15:

- `15 MOD 10 = 5`
- check slot 5: contains 25, not 15
- check slot 6: contains 35, not 15
- check slot 7: contains 15, found

Why you cannot stop too soon: because the item may have been pushed forward by an earlier collision.

Hash tables are especially useful when data must be found quickly from a key. Examples include:

- looking up a telephone number from a name
- checking whether a username exists
- verifying stored user codes or passwords
- implementing a dictionary of key-value pairs
  > **Key Term: dictionary**
  > A data structure that stores data as key-value pairs, where each unique key is linked to a value.

For example:

```text
{"Dave" : 23, "Kev" : 37, "Angelina" : 42}
```

Here, the names are keys and the numbers are values. The key must be unique, but values can repeat.

Dictionaries are useful for frequency counting. Suppose you read text word by word:

- if the word is not already a key, add it with value 1
- if the word already exists, increase its value by 1

That allows fast counting of how often each word appears.

When an exam question asks for advantages, give specific points:

- fast lookup by key
- direct access to an index after hashing
- efficient average performance when collisions are low
- useful for large collections where serial search would be slow

When an exam question asks for limitations, give balanced points:

- collisions are unavoidable
- poor hash functions cause uneven distribution
- simple methods such as ASCII totals can cause many collisions for anagrams
- performance gets worse as the table becomes fuller
- collision handling adds extra searching steps

Avoid overclaiming. Saying "hash tables are always O(1)" is too absolute for this level. A safer phrasing is that they often give near-constant-time access on average when the hash function spreads data well and collisions are limited.

> **Test Tip:** In longer answers, use the words key, hash function, index, collision, and rehashing explicitly. These are the terms examiners expect. General phrases like "it goes somewhere in memory" are too vague.

## Key Point Checklist

_This article has covered the following key knowledge points:_

- A hash table is usually implemented using an array and stores or locates items by converting a key into an index
- A hash function maps a key to a numerical result used to find a storage location
- A common formula is `index = key MOD tableSize`
- For string hashing, a common school-level method is to add ASCII values and then apply modulo
- A collision happens when two different keys produce the same index
- Collisions are normal and become more likely with poor hash functions or fuller tables
- Linear probing handles collisions by checking the next slot, then the next, wrapping around if needed
- Rehashing in A-level questions often means finding another slot after a collision, though it can also mean rebuilding the table
- Searching must use the same probing sequence as insertion
- Hash tables are useful for fast lookup by key, especially in dictionaries and indexed records
- A good hash function spreads values evenly to reduce collisions
- Hash tables are fast on average, but performance falls when many collisions occur

## Key Terms and Concepts

- hash table
- key
- hash function
- index
- collision
- modulo
- rehashing
- linear probing
- open addressing
- separate chaining
- dictionary


Data Structures - Hash tables