The shape of the lesson
By the end of the lesson, learners can
- Three ways to organise a file: The organisation is fixed when records are written.
- Sequential and direct access: Organisation is how the records sit in the file; access is how the program reaches one.
- Hashing and collisions: A hashing algorithm is a calculation on the key field that produces the address where the record is stored.
- Serial: order of arrival. Sequential: key order. Random: address = hash(key).
- Sequential access reads from the start; direct access jumps to the record.
- High hit rate, batch: sequential. One record at a time, fast: random.
- Collisions: next free address (wrap round) or an overflow area; always check the key you read.
One picture every idea returns to
File organisation is how records are arranged in a file. In a serial file records are stored in the order they arrive; in a sequential file they are stored in order of a key field; in a random file each record is stored at an address calculated from its key by a hashing algorithm. File access is how a record is reached: sequential access reads records one after another from the start (serial and sequential files), while direct access goes straight to the record (random files via the hash, sequential files via an index). When two keys hash to the same address there is a collision, handled by storing the record in the next free address or in an overflow area.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, Find the record fast.. How records are arranged in a file decides how quickly one can be found. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Three ways to organise a file | The organisation is fixed when records are written. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Sequential and direct access | Organisation is how the records sit in the file; access is how the program reaches one. Model the worked example Choose the organisation on the board, one line at a time. Your turn: A school's door-entry system records every swipe card use with the time. The log is printed in full at the end of each week. Which file organisation is most suitable, and why? | Pairs |
| 21 to 30 min | Teach and check: Hashing and collisions | A hashing algorithm is a calculation on the key field that produces the address where the record is stored. Project tab 5 of the lab (Hash table: insert keys and watch collisions) and let a student drive it while the class predicts. Model the worked example Insert with collisions on the board, one line at a time. Your turn: Using the file above, how many addresses are read when searching for key 26, and what is the result? | Jigsaw |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 22 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Hashing and collisions, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Jigsaw
Split the content into expert pieces. Expert groups master one piece each, then regroup so every home team has one expert per piece, and each expert teaches their piece to the team.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| Serial and sequential are not the same. | A serial file has no order; a sequential file is sorted on a key field. Say which key the file is ordered by to earn the mark. |
| After hashing, always compare the key of the record found with the key wanted. | The record at the home address may belong to a different key that collided there. |
File organisation, access and hashing: worksheet
6 questions, 22 marks. Written in the style of the papers; no past paper question is reproduced.
Describe the difference between a serial file and a sequential file.
Explain how a record is located in a random file, and why this is faster than searching a serial file.
A random file has addresses 0 to 49. The hashing algorithm is Key MOD 50 and collisions are stored at the next free address. The keys 1207, 3457, 2058 and 907 are inserted in that order into an empty file. State the address of each record.
For each situation, state the most suitable file organisation and justify your choice.
(a) A bank's monthly run that adds interest to every savings account.
(b) A library system that must show the details of one book as soon as its ISBN is scanned.
Describe two methods of handling a collision when writing a record to a random file.
Each record in the random file Stock.dat is of type ItemRecord, with an INTEGER field ItemCode. There are addresses 0 to 499, the hash is ItemCode MOD 500, an empty address has ItemCode 0, and collisions use the next free address. Write a function FindItem(Code : INTEGER) RETURNS INTEGER that returns the address of the record with that code, or -1 if it is not in the file.
Answer key and marking notes
- Serial: records are stored in the order in which they are added / arrive (chronological), with no ordering by key.
- Sequential: records are stored in order of a key field.
- The hashing algorithm is applied to the record's key field to calculate its address.
- The program moves (SEEKs) directly to that address and reads the record, checking its key.
- Searching a serial file reads records one by one from the start, which on average reads half the file.
- 1207 MOD 50 = 7: stored at 7.
- 3457 MOD 50 = 7: collision, stored at 8.
- 2058 MOD 50 = 8: collision with 3457, stored at 9.
- 907 MOD 50 = 7: 7, 8 and 9 taken, stored at 10.
- (a) Sequential (ordered on account number).
- Every record is processed in one batch (high hit rate), so reading in key order from start to end is efficient.
- (b) Random (hashed on the ISBN).
- Each look-up needs one record quickly; the hash gives its address for direct access.
- Next free address: search forward from the home address (wrapping to the start) for the next empty address and store the record there.
- Overflow area: store the record in a separate overflow area, searched serially if the record is not at its home address.
- Both methods must be followed in the same way when the record is later read (third mark for detail on either).
- Declare Address, Count (INTEGER) and Current (ItemRecord);
Address ← Code MOD 500andCount ← 0. OPENFILE "Stock.dat" FOR RANDOM, thenSEEK "Stock.dat", AddressandGETRECORD "Stock.dat", Current.- Loop
WHILE Current.ItemCode <> Code AND Current.ItemCode <> 0 AND Count < 500. - In the loop:
Address ← (Address + 1) MOD 500, SEEK, GETRECORD andCount ← Count + 1. - After the loop:
CLOSEFILE "Stock.dat". IF Current.ItemCode = Code THEN RETURN Address ELSE RETURN -1(ENDIF, ENDFUNCTION).
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
How are the records stored in a sequential file?
- AIn order of a key field
- BIn the order in which they are added
- CAt addresses calculated from the key
- DIn order of the size of each record
A random file uses the hashing algorithm Key MOD 13. At what address is the record with key 200 stored, if there is no collision?
- A5
- B15
- C195
- D8
A random file has addresses 0 to 9, the hash Key MOD 10 and collisions stored at the next free address. Keys 34, 54, 45 and 64 are inserted, in that order, into an empty file. At which address is 64 stored?
- A7
- B4
- C5
- D8
A supermarket till must display the price of an item as soon as its barcode is scanned. The product file holds 40 000 records. Which file organisation and access method are most suitable?
- ARandom organisation with direct access
- BSerial organisation with sequential access
- CSequential organisation with sequential access
- DSerial organisation with direct access
A random file has addresses 0 to 99. The hashing algorithm splits a six-digit key into three pairs of digits, adds them, and takes the result MOD 100. Which key would collide with key 482937?
- A731625
- B482973
- C140014
- D114000
A random file has addresses 0 to 10, the hash Key MOD 11 and the next free address method for collisions, wrapping round from 10 to 0. Keys 14, 25, 36, 9 and 20 were inserted, so addresses 3, 4, 5, 9 and 10 hold 14, 25, 36, 9 and 20, and every other address is empty. A search is made for key 31. How many addresses are read, and what is the result?
- A3 addresses are read and 31 is not found
- B2 addresses are read and 31 is not found
- C1 address is read and 31 is not found
- D4 addresses are read and 31 is found at address 0
Quiz key
A sequential file is sorted on a key field, such as customer ID. Storing records in the order they arrive describes a serial file, and calculating an address from the key with a hashing algorithm describes a random file. Record size is not used to order a file.
13 × 15 = 195 and 200 - 195 = 5, so 200 MOD 13 = 5. 15 is the quotient (200 DIV 13), 195 is the largest multiple of 13 below 200, and 8 is 13 - 5, counting the gap from the other side.
34 goes to 4. 54 hashes to 4, which is taken, so it goes to 5. 45 hashes to 5, now taken by 54, so it goes to 6. 64 hashes to 4 and finds 4, 5 and 6 all full, so it goes to 7. Address 4 ignores the collision, 5 ignores 54, and 8 moves on one address too many.
Hashing the barcode gives the record's address, so it can be read directly with no searching. Reading a serial or sequential file from the start would, on average, read thousands of records for every scan. A serial file has no key order or hash, so it cannot be accessed directly by key.
482937 gives 48 + 29 + 37 = 114, and 114 MOD 100 = 14. 731625 gives 73 + 16 + 25 = 114, also 14, so they collide. 482973 gives 48 + 29 + 73 = 150, address 50; 140014 gives 14 + 00 + 14 = 28; 114000 gives 11 + 40 + 00 = 51. Those last two contain the digits 14 or 114 but do not hash to address 14.
31 MOD 11 = 9. Address 9 holds 9 and address 10 holds 20, so the search wraps round to address 0, which is empty: 3 addresses are read and the key is not in the file. Stopping after 2 forgets the wrap-round, stopping after 1 forgets that 31 may have been moved on by a collision, and an empty address means the key was never stored.
What to project
The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.