Skip to topic
    ← Back to course topics

    Dictionaries — AQA A-Level Computer Science

    A dictionary is an abstract data structure that stores data as an associative collection of key-value pairs, where each unique key maps directly to a specific value. In AQA A-Level Computer Science, dictionaries are typically implemented via hash tables to provide average-case O(1) time complexity for lookup, insertion, and deletion operations.

    Dictionaries explained

    A dictionary is an abstract data type that stores a collection of key-value pairs, where each key is unique and maps to exactly one value.

    Read the full explanation

    The purpose of a dictionary is to retrieve, insert, update or delete a value quickly by supplying its key, rather than by its position in a list. For example, a dictionary might map a student's ID number to their name, so that the name for ID 1042 can be looked up directly. Keys identify entries and values hold the associated data, and the key is what must be unique. Dictionaries are often implemented using hash tables, which is why the topic links closely to hashing. To be familiar with the concept, a learner should be able to describe the key-value structure, explain why keys must be unique, and give a realistic example of when a dictionary would be used.

    Your focus

    1. Be familiar with the concept of a dictionary.

    Which command word is this?

    Set out the technical mechanism or reasoning clearly. For dictionaries, this means detailing how keys are hashed to access values directly in memory.

    Dictionaries exam tips

    Topic Overview

    A dictionary is an abstract data type (ADT) composed of a collection of key-value pairs, where each unique key maps to a corresponding value. Widely used for associative mapping, symbol tables, and fast record retrieval, dictionaries allow programmers to access data via meaningful identifiers rather than arbitrary integer indices.

    Within the AQA A-Level specification, understanding dictionaries links abstract data structures to concrete implementations, primarily hash tables. Mastery of this topic requires students to evaluate the time complexities of operations (O(1) average vs O(n) worst case) and understand the trade-offs between associative structures, linear arrays, and ordered binary search trees.

    Key Concepts
    • →Key-Value Association: Values are stored and retrieved using unique, hashable keys rather than sequential numeric positions.
    • →Hash Table Implementation: Dictionaries typically rely on an internal hash table that maps keys to array buckets via a hash function.
    • →Time Complexity: Average-case time complexity for search, insertion, and deletion is O(1) constant time, degrading to O(n) in the worst case due to collisions.
    • →Collision Resolution: Mechanisms such as separate chaining (linked lists at buckets) or open addressing (linear/quadratic probing) resolve hash clashes.
    Marking Points
    • Defines a dictionary as a collection of key-value pairs.
    • States that each key must be unique and maps to one value.
    • Explains that values are retrieved by key rather than by position.
    • Gives a realistic example, such as mapping an ID number to a name.
    • Identifies that dictionaries are an abstract data type that can be implemented in several ways, including with hash tables.
    Examiner Tips
    • 💡Always name both the key and the value when defining a dictionary.
    • 💡Make sure you state that keys are unique, as this is a commonly tested point.
    • 💡When choosing a dictionary example, use a clear key-to-value mapping such as a word and its definition.
    • 💡Always state both the key and the value when defining a dictionary element, referencing the key's role as an index/identifier.
    • 💡When asked why a dictionary is chosen over a 2D array or linear list, highlight the O(1) average lookup time via direct key addressing rather than O(n) sequential searching.
    • 💡Remember to mention error handling or key membership checks (e.g. 'IF key IN dict') when writing pseudocode to avoid runtime key errors.
    Common Mistakes
    • Describes a dictionary as an ordered list indexed by position; correct it by stating that values are accessed through their keys.
    • Assumes values must be unique rather than keys; correct it by stating that keys are the unique part of each pair.
    • Confuses a dictionary with an array; correct it by explaining that an array uses integer indices while a dictionary uses arbitrary keys.
    • Believing dictionaries are ordered by default: While modern Python 3.7+ preserves insertion order, theoretically and under the AQA specification, dictionaries are treated as unordered associative collections.
    • Assuming keys can be duplicate: Values can be duplicated, but keys must always be unique within a dictionary; assigning to an existing key overwrites its associated value.
    • Confusing average and worst-case efficiency: Students often state search is always O(1), neglecting the impact of pathological hash collisions which cause O(n) degradation.
    Revision Plan
    1. 1Day 1-2: Review abstract data types and the theoretical definition of associative arrays and key-value mapping.
    2. 2Day 3-4: Study the mechanics of hash tables, hash functions, and collision resolution methods (linear probing and separate chaining).
    3. 3Day 5-6: Practise writing pseudocode algorithms for dictionary operations (insert, lookup, delete, update, membership test).
    4. 4Day 7: Compare time and space complexities across arrays, linked lists, trees, and dictionaries in tabular form, then complete past paper questions.
    Exam Question Types
    • 📋Algorithm Design / Pseudocode: Writing code to populate a dictionary from raw inputs, update counts, or extract specific values using keys.
    • 📋Comparative Evaluation: Comparing dictionaries to 1D/2D arrays or binary search trees in terms of time complexity and memory overhead.
    • 📋Mechanics / Trace Questions: Demonstrating how key-value pairs are stored in a hash table array and tracing collision resolution.
    Command Word Expectations (AQA)
    Explain

    Set out the technical mechanism or reasoning clearly. For dictionaries, this means detailing how keys are hashed to access values directly in memory.

    Compare

    Identify both similarities and differences between two structures (e.g. dictionary vs 2D array), explicitly addressing time complexity, index mechanisms, and memory consumption.

    Write an algorithm

    Provide clear pseudocode or high-level code using structured programming constructs to manipulate dictionary keys and values correctly without syntax ambiguity.

    How Students Lose Marks (Examiner Pitfalls)
    Pitfall: Confusing index-based access with key-based access or claiming dictionaries are indexed sequentially by integers starting at 0.
    ❌ Weak Answer (Loses Marks):A dictionary works like an array where elements are numbered 0, 1, 2 and you access values using their position.
    Example improved answer:A dictionary is an associative data structure containing pairs of keys and values. Unlike 0-indexed arrays, values are accessed via their associated unique keys, which are hashed to determine storage locations rather than using sequential numeric indices.
    Examiner Tip: Always specify that keys must be unique and immutable/hashable, whereas values can be duplicated and of any data type.
    Pitfall: Assuming lookup time in a dictionary is always O(1) in the worst case without mentioning hash collisions.
    ❌ Weak Answer (Loses Marks):Dictionaries always retrieve data instantly in O(1) constant time because you just give it the key.
    Example improved answer:Dictionaries achieve O(1) time complexity on average for lookups, insertions, and deletions. However, in the worst-case scenario where extensive hash collisions occur and all keys hash to the same bucket, performance degrades to O(n).
    Examiner Tip: Distinguish clearly between average-case O(1) and worst-case O(n) performance, attributing the difference to hash collision resolution strategies like chaining or open addressing.
    Step-by-Step Worked Solutions

    Question: A program processes a text file to count word frequencies using a dictionary called 'wordCounts'. Write an algorithm in pseudocode to take a list of strings called 'words', populate 'wordCounts', and return the frequency of the word 'algorithm'. Handle the case where the word does not exist.

    1. 1.Step 1: Initialise an empty dictionary: wordCounts = {}
    2. 2.Step 2: Iterate through each word in the 'words' array using a FOR loop.
    3. 3.Step 3: Check if the word is already a key in wordCounts. If it exists, increment its value by 1; if not, initialise its value to 1.
    4. 4.Step 4: Retrieve the count for 'algorithm' using a conditional check to avoid a key error, returning 0 if not found.
    Final Answer: wordCounts = {} FOR EACH word IN words: IF word IN wordCounts THEN wordCounts[word] = wordCounts[word] + 1 ELSE wordCounts[word] = 1 ENDIF ENDFOR IF 'algorithm' IN wordCounts THEN RETURN wordCounts['algorithm'] ELSE RETURN 0 ENDIF

    Question: Explain how a dictionary handles the insertion of a new key-value pair ('GB', 'United Kingdom') into an underlying hash table of size 11, where hash('GB') % 11 = 4. State what occurs if index 4 is already occupied by ('DE', 'Germany').

    1. 1.Step 1: Calculate the bucket location using the hashing function: hash('GB') % 11 = 4.
    2. 2.Step 2: Inspect index 4 of the underlying array to determine availability.
    3. 3.Step 3: Identify the collision with existing entry ('DE', 'Germany').
    4. 4.Step 4: Describe a standard collision resolution technique: linear probing (checking index 5, then 6, cyclically until an empty slot is found) or separate chaining (appending ('GB', 'United Kingdom') to a linked list at index 4).
    Final Answer: The key 'GB' is hashed and mapped to index 4. Since index 4 is occupied by ('DE', 'Germany'), a hash collision occurs. Under linear probing (open addressing), the algorithm checks subsequent contiguous indices (5, 6, etc.) until an empty bucket is located to store the pair. Under separate chaining, the pair is appended to a linked list or dynamic array maintained at bucket 4.
    Active Recall Memory Test
    What is the average Big-O time complexity for searching, inserting, and deleting items in a dictionary?
    Key Fact: O(1) constant time.
    Why must keys in a dictionary be unique?
    Key Fact: Because the key acts as the unique identifier used by the hashing function to locate the exact address of its associated value; duplicate keys would create retrieval ambiguity.
    Under what circumstance does a dictionary lookup degrade to O(n) time complexity?
    Key Fact: When multiple keys produce the same hash value (hash collisions), forcing the system to traverse a linear sequence of elements to locate the target key.
    Frequently Asked Questions
    What is the difference between a dictionary and a hash table?
    A dictionary is an abstract data type (ADT) defined by its behaviour—specifically, mapping unique keys to values. A hash table is a concrete data structure used to implement a dictionary in memory, utilising a hash function to compute an index into an array of buckets.
    Can a dictionary have duplicate keys or duplicate values?
    A dictionary cannot have duplicate keys; each key must be unique to ensure unambiguous data retrieval. If you assign a value to an existing key, the old value is overwritten. However, duplicate values are fully permitted across different keys.
    Why are dictionaries considered faster than linear arrays for searches?
    In an unsorted linear array, finding an element requires a linear search with O(n) time complexity because each element must be checked sequentially. In a dictionary, the key is passed through a hash function that directly calculates the storage index, allowing data retrieval in O(1) average time.
    What data types can be used as keys in a dictionary?
    Keys must generally be immutable and hashable data types, such as integers, strings, or tuples. Mutable types like lists or other dictionaries cannot be used as keys because altering their contents would change their hash value, making the stored value unretrievable.