Past exam question: 2064 Jestha, Q8
Open in the Padhaiko appQuestion
Define hashing and hash collision. How do you minimize the hash collision? Write an algorithm for collision resolution by open addressing.
Solution
Hashing, Hash Collision, and Minimizing Collisions:
- Hashing: A technique that maps search keys directly to table indices using a hash function for average-time lookup.
- Hash Collision: Occurs when two distinct keys hash to the same index ().
- How to Minimize Collisions:
- Choose a prime table size (not a power of 2 or 10) for division hashing .
- Keep the load factor low (typically , rehashing when exceeded).
- Design a uniform hash function that distributes keys evenly across all buckets.
Algorithm for Open Addressing Insertion & Search (Linear Probing):
Algorithm OPEN_ADDR_INSERT(HT, m, key):
1. h0 = key % m
2. For i = 0 to m - 1:
idx = (h0 + i) % m
If HT[idx] == EMPTY or HT[idx] == DELETED:
HT[idx] = key
Return idx
If HT[idx] == key:
Return idx // duplicate
3. Print "Hash Table Overflow"
4. Return -1
(Replacing idx = (h0 + i) % m with (h0 + i*i) % m gives quadratic probing, and (h0 + i*h2(key)) % m gives double hashing.)
Answer:
Hashing maps keys to indices via for average access; collisions () are minimized using prime table sizes, low load factors, and uniform hash functions, and resolved in open addressing by probing (h(k) + i) % m until an empty/deleted slot is found.