Show understanding of hashing algorithms

13.2 File Organisation and Access – Hashing Algorithms

In this section we will explore how hashing helps us organise and quickly access data in files. Think of a hash like a super‑fast librarian who can point you to the exact shelf where your book is stored.

🔑 What is a Hash Function?

A hash function takes a key (like a student ID) and turns it into an index inside a table.

Mathematically: $h(k) = k \bmod m$ where $m$ is the table size.

⚙️ Collision Resolution Techniques

• Linear Probing – move to the next slot until an empty one is found.
• Quadratic Probing – jump by increasing squares: 1, 4, 9, …
• Separate Chaining – each slot holds a linked list of records.

📊 Example: Hash Table for Student IDs

Here $m=10$, so $h(1023)=1023 \bmod 10 = 3$ (but we moved to index 0 due to linear probing).

📝 Exam Tips

1. Remember that a hash function must be fast and uniform.
2. When asked about collisions, list at least two resolution methods.
3. Use the example of a library or locker system to explain how hashing reduces search time.
4. Show the formula $h(k) = k \bmod m$ when asked to design a simple hash.

📚 File Organisation Types

• Sequential Access – read file from start to finish.
• Direct Access – jump straight to a record using an address.
• Hashing – uses a hash function to compute the address.

Hashing is a form of direct access that is especially useful when you need to find a record quickly without scanning the whole file.

🔒 Analogy: Locker System

Imagine each locker in a school hallway has a number. To find a locker, you use a simple rule: $locker = studentID \bmod totalLockers$. If two students get the same locker number, they either share it (chaining) or move to the next available locker (probing).

🔄 Summary

Hashing turns a key into an index, giving O(1) average access time. Key points:

• Choose a good hash function.
• Handle collisions with probing or chaining.
• Use hashing for quick file access.