Hash tables + B4 cumulative Paper 2 checkpoint
Explain hashing, collisions and load factor, then retrieve linked lists, BSTs and sets in one cumulative HL ADT checkpoint.
Hashing completes the B4 scope
- explain hashing functions, collisions, collision resolution and load factor;
- connect Python
dictandsetto ADT/hash-table principles; - retrieve the complete B4 linked-list, BST and set scope;
- complete a mixed Paper 2 checkpoint with code, diagrams and explanations.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
A hash narrows the starting location
index = key % 5 with table indices 0–4. This simplified function is only for tracing the mechanics.Calculate the target slots
Find the initial table index for keys 12, 7, 18 and 3. Identify every collision.
- 12 % 5 = 2
- 7 % 5 = 2 → collision with 12
- 18 % 5 = 3
- 3 % 5 = 3 → collision with 18
Two different strategies preserve multiple keys
Separate chaining
Using the hash function index = key % 5 with table indices 0–4, insert keys 12, 7, 18, 3 using separate chaining. Sketch the final table as index → chain.
0 → empty 1 → empty 2 → 12 → 7 3 → 18 → 3 4 → empty
The exact order within each chain depends on the insertion implementation; the key point is that colliding entries share the bucket/chain.
Linear probing
Insert 12, 7, 18 and 3 in that order into an empty five-slot table using key % 5 and linear probing. State the final slot of each key.
12 → slot 2. 7 collides at 2 → slot 3. 18 hashes to 3, which is occupied → slot 4. 3 hashes to 3, then probes 4, then wraps to 0 → slot 0.
Load factor links storage density to collision cost
Load factor
A table has capacity 20 and stores 12 entries. State its load factor as a decimal and explain why rising load factor can reduce performance.
The load factor is 12 / 20 = 0.6. As more of the table is occupied, collisions become more likely; chains can grow or probing can require more slot checks, increasing operation time.
Python connection
Explain the conceptual difference between using a Python dict and a Python set.
A dict maps unique keys to associated values, while a set represents unique elements without key-value pairs. Both expose high-level operations while Python manages underlying hashing mechanics internally.
Key → value is the behaviour the question cares about
Dictionary application
Airport codes map to airport names:
airports = {
"LHR": "London Heathrow",
"SIN": "Singapore",
"LAX": "Los Angeles"
}
Describe how the dictionary can return an airport name when a code is supplied, and connect the explanation to key-value lookup.
The airport code is used as the unique key and the airport name is the associated value. A lookup such as airports["SIN"] asks the dictionary to locate the entry for key "SIN" and return its mapped value "Singapore". At the ADT level, the programmer uses key-based operations without manually managing the underlying hash table.
Linked lists + ADT principles
B4 cumulative checkpoint · Part A
1. Explain what an ADT provides.
2. Evaluate a linked list against an array/list for frequent insertion at known positions but frequent direct indexed access.
3. Sketch head → 10 → 30 → None after inserting 20 between the two nodes, and state the required pointer-change order.
- High-level purpose/data/operations without fixing one implementation.
- Linked list avoids shifting elements for updates once position is known but has O(n)-style traversal for indexed access and extra reference memory; the judgement depends on which operation dominates.
- Final chain is
10 → 20 → 30; point the new node to 30 before redirecting 10’s next link to the new node.
BST + set retrieval
B4 cumulative checkpoint · Part B
1. Insert 65 into this BST and sketch the result:
50
/ \
30 70
/
60
2. State the inorder traversal after insertion.
3. Given A = {1,2,3} and B = {2,3,4}, state A | B, A & B and A - B.
65 is the right child of 60. Inorder is 30, 50, 60, 65, 70. Union is {1, 2, 3, 4}; intersection is {2, 3}; difference A−B is {1}.
Close the B4 block with targeted evidence
Gap diagnosis
Choose the B4 area that still needs the most retrieval: ADT principles, linked lists, BSTs, sets or hashing.
IA progress check
Record one implemented feature, one test result and one development decision that you can explain in Criterion D.
Finish the learning cycle
IA — main task
Continue Criterion D development/testing. Keep evidence focused on important implementation choices and effective testing rather than screenshots alone.
Paper 2 — short practice
Redo only the B4 checkpoint areas you missed. Then explain hashing function, collision, two collision-resolution strategies and load factor from memory.
Checkpoint
Open your Paper 2 notes and make sure you can identify when a task is asking for Python code versus a no-code algorithm description.