File Organisation, Access and Hashing
Two separate ideas are examined here and must not be confused.
File organisation is how records are arranged in storage.
File access is how a record is found. A file's organisation limits which access
methods are possible.
1. Serial Organisation
Records are stored one after another in the order they arrive, with no ordering by key. New records are simply appended to the end.
Order of arrival: 1043 | 1007 | 1289 | 1055 | 1100
(no sorted order at all)
| Advantages | Disadvantages |
|---|---|
| Adding a record is very fast — just append | Finding a record requires reading from the start |
| No wasted space | No direct access possible |
| Simple to implement | Slow for anything except processing every record |
Typical use: a transaction log, or any file where records are recorded as events happen and later processed in bulk.
2. Sequential Organisation
Records are stored in order of a key field. The arrangement is maintained whenever records are added.
Sorted by key: 1007 | 1043 | 1055 | 1100 | 1289
| Advantages | Disadvantages |
|---|---|
| Faster searching — a search can stop once it passes the target key | Inserting a record may require rewriting much of the file to preserve order |
| Efficient for processing records in key order | Still no direct access to an arbitrary record |
| Suits batch processing such as payroll | Deleting leaves gaps needing periodic reorganisation |
Serial and sequential are different. Serial has no order; sequential is ordered
by a key field. Using the words interchangeably loses marks, and questions often test exactly this
distinction.
3. Random (Direct) Organisation
The address of a record is calculated from its key using a hashing algorithm. The record is written to, and later read from, that calculated position — so it can be reached without reading anything else.
| Advantages | Disadvantages |
|---|---|
| Very fast access to a single record — typically one read | Space is often wasted, as not every address is used |
| Access time does not grow with the number of records | Collisions must be detected and handled |
| Ideal for real-time enquiries | Reading records in key order is inefficient |
4. Hashing Algorithms
A hashing algorithm converts a key into a storage address. A common simple method is to divide by the number of available addresses and take the remainder.
FUNCTION Hash(Key : INTEGER) RETURNS INTEGER
RETURN Key MOD 100 // 100 available addresses, 0 to 99
ENDFUNCTION
Worked example
| Key | Calculation | Address |
|---|---|---|
| 1043 | 1043 MOD 100 | 43 |
| 1007 | 1007 MOD 100 | 7 |
| 1289 | 1289 MOD 100 | 89 |
| 1143 | 1143 MOD 100 | 43 — collision! |
Collisions
A collision occurs when two different keys hash to the same address. Collisions are unavoidable, so every hashing scheme needs a resolution strategy.
| Method | How it works |
|---|---|
| Open addressing (linear probing) | Search forward from the calculated address for the next free slot and store the record there |
| Chaining / overflow area | Each address holds a pointer to a linked list of records that hashed to it |
Reading a record back must repeat the process. Hash the key, go to that address, and check the
key actually stored there. If it does not match, follow the same collision-resolution method used when writing
until the record is found or a free slot proves it is absent.
A good hashing algorithm distributes keys evenly across the available addresses, so collisions
are rare, and is quick to compute. A poor one clusters records at a few addresses, and performance degrades
towards that of a serial search.
5. File Access Methods
| Access method | How a record is found | Works with |
|---|---|---|
| Sequential access | Read records one after another from the beginning | Serial, sequential and random files |
| Direct access | Calculate the address from the key and read it immediately | Random (hashed) files only |
A random file supports both access methods: direct access for a single enquiry, and sequential
access when every record must be processed. A serial file supports sequential access only. This flexibility is a
frequently credited advantage of random organisation.
6. Choosing an Organisation
| Requirement | Best choice | Reason |
|---|---|---|
| Log events as they occur | Serial | Appending is fastest; order does not matter |
| Process every record monthly in key order | Sequential | Records are already in the required order |
| Look up one customer instantly | Random | Direct access needs only one read |
| Both instant lookup and full reporting | Random | Supports direct and sequential access |
7. Exam Focus
Justify by the intended use. Questions ask you to choose an organisation for a described
scenario. State the choice and tie the reason to what the system actually has to do — frequent single
enquiries point to random, bulk ordered processing points to sequential.
Show the hash calculation. When asked to find an address, write the arithmetic
(1043 MOD 100 = 43). The working carries marks even where the answer is obvious.
Always mention collisions. Any answer describing hashed access is incomplete without stating
that two keys can produce the same address and naming a resolution method.
Quick self-check
- State the difference between serial and sequential organisation.
- Explain the purpose of a hashing algorithm.
- Using Key MOD 50, find the addresses for keys 275 and 325. What do you notice?
- Describe two ways of resolving a collision.
- Which organisation supports both direct and sequential access, and why is that useful?
- Give one disadvantage of random organisation.