Cambridge practical task: text records, hashing and evidence
Use real text fixtures to build and modify a bounded data structure. Trace its addresses before running code, then use code and output evidence to justify your implementation.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
Explore the idea
Load text records. Trace storage and collect evidence.
Use a five-slot simulated random-access table loaded from text. Follow collision probes and updates, then compare code/output evidence with an expected trace.
The idea to start with
This original task simulates address-based records in a five-slot memory table, loaded from text. Hash a nonnegative integer ID using ID mod 5 and use linear probing with wraparound. The same key updates its record; a new key is rejected if the table is full.
The supplied starter has a lookup defect: it examines only the home slot. Repair retrieval using the insertion probe sequence. This is text-loaded Paper 4 practice, not a binary source file or an imitation of an actual examination task.
Cambridge International 9618 · 19.1; 20.2; 13.2 supporting file-organisation context
Before you start
Useful foundations
Python functions, lists, text files and exceptions
Remainders, hashing and linear probing
By the end, you should be able to
Load and validate text records into a fixed-capacity table.
Trace collisions, wraparound, updates and bounded failed searches.
Save/reload logical records and test normal/boundary/invalid cases.
Construct an update-only variation and capture relevant practical evidence.
Original practice files
Read TASK.txt first. Keep the solution closed while attempting the starter. These plain-text files run locally in your chosen Python environment.
Cambridge 2027–2029 Paper 4 practice: independent construction, modification, text fixtures, collision handling, exceptions and evidence. The model is text-loaded memory storage, not binary-file seeking. Use the examination year's official submission instructions.
Shared foundations and optional extensions are labelled separately; this page does not claim complete coverage of the qualification.
Construct the representation from requirements
Construct the representation from requirements
records.txt stores ID,name lines. Ignore blank lines and reject malformed or negative IDs and empty names. Allocate five empty slots, then insert or update each valid record using linear probing. Every search must stop after at most the table's capacity.
Keys 12,17,22 and 27 all hash to slot 2. They occupy 2,3,4 and 0 respectively. A later key 17 updates slot 3 rather than creating a duplicate. A full-table insert must not overwrite a different record.
Use text fixtures for random-file-style reasoning
Use text fixtures for random-file-style reasoning
The slots represent simulated addresses. Reading text, hashing keys and indexing an array are not binary-file seek operations; keep that distinction clear when explaining the model. The official 2027–2029 assessment details state that supplied Paper 4 source files do not contain binary files.
A text serialisation can write occupied records in slot order. Reloading preserves the logical key/value records but can change physical slot positions when the insertion order changes. Check records by key rather than requiring the same slot array after every reload.
Repair retrieval and test its stopping conditions
Repair retrieval and test its stopping conditions
A lookup must compare the candidate key at each probed slot. An empty slot ends an unsuccessful search because this task has no deletions. A full table needs an explicit capacity bound to avoid an infinite loop when a key is absent.
Adding deletion would require a new policy such as tombstones; clearing a collided slot can break later lookups. That is an extension, not an undocumented operation of this task. Preserve the same wraparound formula in insertion and retrieval.
Make a meaningful modification
Make a meaningful modification
Construct update_existing(ID,new_name): search for the key, replace only that record if present, and report failure without inserting if absent. Use a collided key, an absent key and a full table to distinguish it from the existing insert-or-update operation.
Extend file handling to a user-selected local path with appropriate error reporting. Record a predicted outcome for a missing file and invalid record before running. Avoid using a try/except that silently discards every error; distinguish row validation from file access.
Reference implementation and evidence
Keep the solution closed for the construction/repair attempt. Copy record_store_starter.py to record_store.py, then run python -m unittest test_record_store.py. Five independent test methods cover collisions, wraparound, updates/full tables, invalid/empty input and logical save/reload.
The official syllabus names Python console mode, Java console mode and Visual Basic .Net console mode. This exercise uses Python; it does not replace practice in a centre's chosen language. Save regularly and capture labelled listings and test outputs using the examination year's evidence instructions.
Original text-loaded record-store referencePython
"""Original text-loaded hash-table simulation; not binary-file access."""
from pathlib import Path
def insert(table, identifier, name):
for offset in range(len(table)):
index = (identifier % len(table) + offset) % len(table)
if table[index] is None or table[index][0] == identifier:
table[index] = (identifier, name)
return index
raise OverflowError('table full')
def find_record(table, identifier):
for offset in range(len(table)):
index = (identifier % len(table) + offset) % len(table)
if table[index] is None:
return None
if table[index][0] == identifier:
return table[index]
return None
def load_records(text, capacity=5):
if type(capacity) is not int or capacity < 1:
raise ValueError('positive integer capacity required')
table, rejected = [None] * capacity, []
for line_number, raw in enumerate(text.splitlines(),1):
if not raw.strip():
continue
fields = raw.strip().split(',')
if len(fields) != 2 or not fields[0].isascii() or not fields[0].isdigit() or not fields[1].strip():
rejected.append((line_number,'format'))
continue
try:
insert(table,int(fields[0]),fields[1].strip())
except OverflowError:
rejected.append((line_number,'full'))
return table,rejected
def save_records(table):
return ''.join(f'{row[0]},{row[1]}\n' for row in table if row is not None)
if __name__ == '__main__':
try:
table,rejected = load_records(Path('records.txt').read_text(encoding='utf-8'))
print(list(enumerate(table)))
print('Lookup 17:',find_record(table,17))
print('Rejected:',rejected)
Path('saved-records.txt').write_text(save_records(table),encoding='utf-8')
except (OSError,UnicodeError) as error:
print(f'Cannot read/write task files: {error}')
Follow a collision through the end of the table
Worked example
Follow a collision through the end of the table
Load 12,Alder into home slot 2. Load 17,Birch: 2 is occupied by a different key, so use slot 3.
Load 22,Cedar: probe 2,3,4. Load 27,Elm: probe 2,3,4,0; the last step wraps.
Load 17,Updated: compare 12 at slot 2, then match key 17 at slot 3 and overwrite its name. Count stays four.
Lookup 99 hashes to 4, sees keys 22 and 27, then finds empty slot 1 and reports absent. In a full table, examine at most five slots before reporting absence.
Common mix-up: A collision means the keys are equalCommon mix-up: Saving text must reproduce identical physical slots
Original A-Level practice
4 original questions total 14 marks. Attempt each before opening the independently written indicative marking guidance.
Question 1
4 marks
Capacity 5, h(ID)=ID mod 5, linear probing with wraparound, no deletion. Insert 12:A, 17:B, 22:C, 27:D in order. Give the occupied slots and the probes for 27.
Show solution and marking guidance+
Indicative answer
Slot 2→12:A and slot 3→17:B.
Slot 4→22:C.
Slot 0→27:D; slot 1 remains empty.
27 probes 2,3,4,0.
Question 2
3 marks
Using that table, insert-or-update 17:Edited. State its slot, whether the count changes and the probe sequence.
Show solution and marking guidance+
Indicative answer
Update slot 3.
Count remains four.
Probe 2 then 3; compare the ID before replacing its name.
Question 3
4 marks
Design an update-only operation and distinguish it from insertion with two explicit tests.
Show solution and marking guidance+
Indicative answer
Search using the same bounded probe sequence; replace only when the key matches.
Return/report absence without allocating a slot for a missing key.
Existing collided key 17: update succeeds and count is unchanged.
Absent key 99: update fails and every stored record/count is unchanged.
Question 4
3 marks
Explain two reasons why a single screenshot of a final table is insufficient testing evidence. Give an appropriate full-table absent-key test.
Show solution and marking guidance+
Indicative answer
It does not demonstrate the code/probe path or connect an expected result to a requirement.
It does not cover boundary/error behaviour such as wraparound or failed searches.
Fill five distinct keys, search for another key, and expect absence after at most five probes with no mutation.
Specification and references
This guide addresses Cambridge International 9618 19.1; 20.2; 13.2 supporting file-organisation context. Check your examination year and the complete specification for the assessment scope.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.