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
- 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
- 1Day 1-2: Review abstract data types and the theoretical definition of associative arrays and key-value mapping.
- 2Day 3-4: Study the mechanics of hash tables, hash functions, and collision resolution methods (linear probing and separate chaining).
- 3Day 5-6: Practise writing pseudocode algorithms for dictionary operations (insert, lookup, delete, update, membership test).
- 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)
Set out the technical mechanism or reasoning clearly. For dictionaries, this means detailing how keys are hashed to access values directly in memory.
Identify both similarities and differences between two structures (e.g. dictionary vs 2D array), explicitly addressing time complexity, index mechanisms, and memory consumption.
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)
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.Step 1: Initialise an empty dictionary: wordCounts = {}
- 2.Step 2: Iterate through each word in the 'words' array using a FOR loop.
- 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.Step 4: Retrieve the count for 'algorithm' using a conditional check to avoid a key error, returning 0 if not found.
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.Step 1: Calculate the bucket location using the hashing function: hash('GB') % 11 = 4.
- 2.Step 2: Inspect index 4 of the underlying array to determine availability.
- 3.Step 3: Identify the collision with existing entry ('DE', 'Germany').
- 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).