Hashing (Cambridge (CIE) A Level Computer Science): Revision Note
Exam code: 9618
Hashing algorithms
What is a hashing algorithm?
A hashing algorithm is used to calculate the storage location (address) of a record in a random (direct access) file
It allows for fast access to data without searching sequentially through a file
Why use hashing?
Provides direct access to records using a key (e.g. ID, account number)
Useful when dealing with large files that need fast search, read, or write operations
Used in random files and sometimes in indexed sequential files
How hashing works?
A hashing algorithm takes a key (e.g. StudentID) and uses a mathematical function to calculate a file address
Address = HashFunction(Key)If two keys produce the same address, a collision occurs
This must be resolved (e.g. via linear probing or overflow areas)
Writing a record to a file:
Address ← HashFunction(Key)
WRITE file[Address], RecordReading a record from a file:
Address ← HashFunction(Key)
READ file[Address], RecordIf the expected record is not found, collision handling must be applied to find the correct record
Types of hashing algorithms
Method | Description |
|---|---|
Modulo Division | Most common method: |
Folding Method | Breaks the key into parts and adds them together |
Mid-Square Method | Square the key and use the middle digits as the address |
Multiplicative Hashing | Multiplies the key by a constant and uses fractional part × tablesize |
Collision handling strategies
Strategy | Description |
|---|---|
Linear probing | Try the next available slot in sequence |
Overflow area | Store conflicting records in a separate file/area |
Chaining | Store all records with the same address in a list |
You've read 0 of your 5 free revision notes this week
Unlock more, it's free!
Did this page help you?
