Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1-2: Master the fundamentals of hashing functions (folding, truncation, MOD arithmetic) and practice calculating indices manually.
    2. 2Day 3-4: Draw step-by-step traces of collision resolution using both linear probing and separate chaining methods.
    3. 3Day 5-6: Code a basic hash table in Python, implementing insert, search, and delete with tombstones to reinforce edge cases.
    4. 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)
    Explain

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

    Describe

    Give a factual account of how an operation works step-by-step without necessarily analysing advantages and disadvantages.

    Compare

    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)
    Pitfall: Confusing collision resolution techniques, specifically mistaking linear probing (open addressing) for chaining (closed addressing) or failing to explain how retrieval works after a collision.
    ❌ Weak Answer (Loses Marks):A collision occurs when two values have the same hash, so the computer stores the second item in another linked list or next door.
    Example improved answer:A collision occurs when two distinct keys produce the identical hash index from the hashing algorithm. In linear probing, the algorithm sequentially inspects subsequent array indices until an empty cell is found. In separate chaining, each table index points to a linked list where colliding records are appended.
    Examiner Tip: Always specify that the hashing algorithm operates on the key, not the data item itself, and explicitly state how retrieval handles linear probing by continuing the probe until the key is found or an empty slot is encountered.
    Pitfall: Assuming hash tables are always O(1) in the worst-case scenario and failing to explain why performance degrades.
    ❌ Weak Answer (Loses Marks):Hash tables always search and insert in O(1) constant time because the hashing algorithm calculates the exact location immediately.
    Example improved answer:While hash tables offer average O(1) time complexity, poor hashing functions or a high load factor can cause excessive collisions. In the worst-case scenario where all n keys hash to the same bucket or require scanning the entire array, time complexity degrades to O(n).
    Examiner Tip: Distinguish between average-case O(1) and worst-case O(n) performance. When asked to evaluate efficiency, mention the load factor and table resizing.
    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. 1.Step 1: Calculate index for key 15: 15 MOD 7 = 1. Index 1 is empty, insert 15 at index 1.
    2. 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. 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. 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.
    Final Answer: Index 0: Empty, Index 1: 15, Index 2: 22, Index 3: 8, Index 4: 29, Index 5: Empty, Index 6: Empty.

    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. 1.Step 1: Pass the key 'Smith' into the hashing function to generate the target table index.
    2. 2.Step 2: Access the array at the calculated index, which stores a reference/pointer to the head of a linked list.
    3. 3.Step 3: Sequentially traverse through the nodes of the linked list, comparing 'Smith' with the key stored in each node.
    4. 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.
    Final Answer: Compute h('Smith') to find the bucket index, then linearly traverse the linked list located at that index until the node matching key 'Smith' is found and its record returned.
    Active Recall Memory Test
    What is the average time complexity for searching an element in a well-distributed hash table?
    Key Fact: O(1) constant time complexity.
    What mathematical issue occurs when two distinct keys yield the same index, and what is this termed?
    Key Fact: A collision, caused when h(k1) = h(k2) where k1 != k2.
    Why can an entry not simply be cleared to null/empty when deleted in an open-addressing hash table?
    Key Fact: Because clearing it breaks the probe sequence for existing elements that collided and were stored further down the table; a tombstone marker is needed instead.
    What formula defines the load factor (alpha) of a hash table?
    Key Fact: Load factor = n / k, where n is the number of occupied entries and k is the total number of table slots.
    Frequently Asked Questions
    What happens when a hash table becomes full in linear probing?
    When an open-addressed hash table reaches capacity or exceeds its load factor threshold (usually around 0.7), it must be resized. A new array, typically double the size of the original, is allocated. Every existing element must then be rehashed using the new table size and inserted into the new array, which is an O(n) operation.
    Why is a prime number often chosen for the size of a hash table?
    Using a prime number as the modulus reduces the likelihood of clustering when hashing keys with common factors. It ensures that keys are distributed more uniformly across all available indices, particularly when the hash function uses simple modular arithmetic.
    What is primary clustering in hash tables?
    Primary clustering is a phenomenon in linear probing where occupied slots group together in long continuous blocks. As clusters grow larger, the probability of new keys hashing into the cluster increases, which significantly degrades lookup and insertion times towards O(n).
    How does separate chaining differ from linear probing?
    In linear probing (open addressing), colliding items are placed in alternate vacant cells within the primary array itself. In separate chaining (closed addressing), each array slot holds a pointer to an external data structure, such as a linked list, where all keys hashing to that same index are stored together.