Hash tables — AQA A-Level Computer Science
A hash table is an associative data structure that maps unique keys to values using a mathematical hashing function to determine array indices. Under ideal conditions, hash tables achieve average O(1) constant time complexity for insertions, lookups, and deletions, though collision resolution strategies like open addressing or chaining are essential.
Hash tables explained
A hash table is a data structure that stores items in an array so that each item can be located using a key rather than a search through every element.
Read the full explanation
A hash function takes a key and converts it into an integer index, which is used as the storage position for that item. Because the index is calculated directly from the key, retrieval, insertion and deletion can all be carried out in constant time on average, which is why hash tables are used where fast lookup matters, such as dictionaries, symbol tables in compilers, caches and the indexing of database records. Learners should understand that two different keys can produce the same index, known as a collision, and that collisions are handled by techniques such as chaining, where each array slot holds a linked list of items, or open addressing, where another free slot is found.
Your focus
- Be familiar with the concept of a hash table and its uses.
Which command word is this?
Set out the mathematical or logical process clearly with causal links (e.g. explain how linear probing resolves collisions when two keys map to index 3).
Hash tables exam tips
Topic Overview
Hash tables are fundamental associative data structures designed to store key-value pairs with near-instantaneous data retrieval. They convert search keys into integer array indices using mathematical hash algorithms, drastically reducing the search overhead compared to linear or binary search approaches.
Within the AQA A-Level Computer Science specification, hash tables bridge the gap between theoretical algorithm design and efficient memory management. Mastery of hash tables requires understanding hash function properties, collision resolution mechanisms, dynamic rehashing, and big-O time complexity trade-offs.
Key Concepts
- →Hash function: A deterministic mathematical algorithm that converts a variable-length key into a fixed-range numerical array index.
- →Collision: A state occurring when two distinct search keys generate the identical array index after hashing.
- →Open addressing (Linear Probing): Resolving collisions by searching sequentially through subsequent array indices until an unoccupied slot is located.
- →Closed addressing (Separate Chaining): Resolving collisions by maintaining an auxiliary data structure, typically a linked list, at each index.
- →Load factor: The ratio of stored records (n) to total available table slots (k); exceeding a threshold (typically 0.7) necessitates resizing and rehashing.
Marking Points
- Explains that a hash table stores items in an array addressed by a key.
- Describes the role of the hash function in turning a key into an index.
- Identifies that lookup, insertion and deletion are fast on average because the index is calculated directly.
- Gives a suitable use such as a dictionary, cache or symbol table.
- Explains that a collision occurs when two keys map to the same index.
- Describes a collision handling method such as chaining or open addressing.
Examiner Tips
- 💡Define the hash table in terms of key, hash function and index before giving any detail.
- 💡Link the stated use to the advantage of fast average-case access.
- 💡When a collision is mentioned, always name at least one way of resolving it.
- 💡When tracing open addressing questions, clearly show your MOD calculations for each step before writing down the probed index.
- 💡Always state what happens when reaching the end of an array during linear probing; mention that the search wraps around back to index 0.
- 💡In evaluation questions, explicitly contrast the memory overhead of pointers in separate chaining against the clustering issues found in linear probing.
Common Mistakes
- Describes a hash table as a sorted list that is searched in order; correct by stating that the key is hashed directly to an index.
- Claims that hash tables never have collisions; correct by stating that collisions are possible and must be handled.
- Gives a use that depends on ordered traversal as its main purpose; correct by choosing a use based on fast key-based lookup.
- Believing that a hash table automatically expands without cost: resizing requires allocating a larger array and recalculating the hash for every existing key, which is an O(n) operation.
- Confusing deleting an element in linear probing: simply clearing an index breaks probe chains for subsequent items; a special 'deleted' flag/tombstone must be placed instead.
- Thinking hashing is encryption: hashing is a one-way mathematical transformation meant for fast retrieval or verification, not reversible data concealment.
Revision Plan
- 1Day 1-2: Master the fundamentals of hashing functions (folding, truncation, MOD arithmetic) and practice calculating indices manually.
- 2Day 3-4: Draw step-by-step traces of collision resolution using both linear probing and separate chaining methods.
- 3Day 5-6: Code a basic hash table in Python, implementing insert, search, and delete with tombstones to reinforce edge cases.
- 4Day 7: Work through past AQA exam questions focusing on time complexity comparisons and algorithmic traces.
Exam Question Types
- 📋Algorithm trace questions: Given a specific hash function (e.g. key MOD table_size) and a sequence of keys, show the table state after linear probing.
- 📋Written explanation questions: Defining collisions, explaining why they are unavoidable via the pigeonhole principle, and describing resolution techniques.
- 📋Comparative analysis questions: Comparing the average and worst-case time complexity of hash tables against binary search trees or arrays.
Command Word Expectations (AQA)
Set out the mathematical or logical process clearly with causal links (e.g. explain how linear probing resolves collisions when two keys map to index 3).
Give a factual account of how an operation works step-by-step without necessarily analysing advantages and disadvantages.
Identify both similarities and differences between two approaches (e.g. separate chaining vs linear probing), using technical terminology for full marks.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: A hash table of size 7 uses the hash function h(key) = key MOD 7. Insert the keys 15, 22, 8, and 29 in order using linear probing to resolve any collisions. Show the contents of the array after all keys are inserted, indexing from 0 to 6.
- 1.Step 1: Calculate index for key 15: 15 MOD 7 = 1. Index 1 is empty, insert 15 at index 1.
- 2.Step 2: Calculate index for key 22: 22 MOD 7 = 1. Index 1 is occupied (collision with 15). Apply linear probing: check index 2. Index 2 is empty, insert 22 at index 2.
- 3.Step 3: Calculate index for key 8: 8 MOD 7 = 1. Index 1 is occupied. Check index 2 (occupied). Check index 3 (empty). Insert 8 at index 3.
- 4.Step 4: Calculate index for key 29: 29 MOD 7 = 1. Indices 1, 2, and 3 are occupied. Check index 4 (empty). Insert 29 at index 4.
Question: Explain how a record with the key 'Smith' is retrieved from a hash table that uses separate chaining, including the case where a collision has occurred.
- 1.Step 1: Pass the key 'Smith' into the hashing function to generate the target table index.
- 2.Step 2: Access the array at the calculated index, which stores a reference/pointer to the head of a linked list.
- 3.Step 3: Sequentially traverse through the nodes of the linked list, comparing 'Smith' with the key stored in each node.
- 4.Step 4: Stop when a matching key is found to return the associated record, or return a not found indicator if the end of the list is reached.