PadhaikoAll subjects

Past exam question: 2064 Jestha, Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

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:

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.

All past exam questions for Data Structure and Algorithms