Hashing (Cambridge (CIE) A Level Computer Science): Revision Note
Exam code: 9618
What is a hashing algorithm?
A hashing algorithm is a mathematical formula applied to the key field of a record
The result of the calculation gives the address where that record should be stored or found
It is used in direct access on random and sequential files, giving fast access to a record without searching through the file one record at a time
Hashing algorithms
How does hashing work?
The key (e.g. a
StudentIDor account number) is passed through the hash function to produce an address:Address ← HashFunction(Key)
Writing a record: calculate the address from the key, then store the record there
Reading a record: calculate the address from the same key, then read the record from there
// Writing
Address ← HashFunction(Key)
WRITE File[Address], Record
// Reading
Address ← HashFunction(Key)
READ File[Address], Record
Types of hashing algorithm
Method | How it works |
|---|---|
Modulo division | The most common method: |
Folding | The key is split into equal parts, the parts are added together, and (usually) |
Handling collisions
Method | How it resolves the collision |
|---|---|
Linear probing | Start at the hashed address and move through the following locations in a linear fashion, storing the record in the first free location |
Overflow area | A separate overflow area is set up; the record is stored in the next free space there |
Chaining | Each location holds a reference to a list (chain) of records that hashed to it; the record is added to that chain |
Examiner Tips and Tricks
When defining a hashing algorithm, use the exam's own words: a mathematical formula / calculation applied to the key field whose result is the address. "It scrambles the data" scores nothing.
For collision resolution, name a method and describe it: "linear probing, store in the next free location" earns more than "linear probing" alone.
Hashing questions almost always ask you to describe the algorithm and handle collisions, not to invent a hash function. Spend your revision there.
Worked Example
A random file has 100 storage locations, addressed 0 to 99. Records use a numeric key.
Show how the modulo division method stores the records with keys 45217 and 88317.
Answer
45217 MOD 100 = 17, so the record with key 45217 is stored at address 1788317 MOD 100 = 17, so this record hashes to the same address, a collisionUsing linear probing, it is stored in the next free location, address 18
Unlock more, it's free!
Join the 100,000+ Students that ❤️ Save My Exams
the (exam) results speak for themselves:
Was this revision note helpful?
Build on this topic
