Question

Will you provide a brief explanation with the answer please?

1.3 Suppose we are implementing quadratic probing with a hash function Hash(X)= X mod 100. If an element with key 4594 is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is (a) 2 (b) 3 (c) 9 (d) 97 (e) none of the above.

Answer 1

Answer: c) 9

Quadratic Probing We look for i²‘th slot in i’th iteration.

let hash(x) be the slot index computed using hash function.  
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S

......................................................................................................................................

Here we have the hash function hash(X) = X mod 100

for the given key value X = 4594

First Attempt

the hash value yielded would be 4594 mod 100 = 94

It was given that the first three locations attempted were already occupied

So the location 94 was occupied.

Second Attempt

As we are using Quadratic probing We look for i²‘th slot in i’th iteration.

So the first i² index would be 1*1 = 1

The second attempted location was occupied as well.

Third Attempt

The next i² value would be 2 * 2 = 4

The third attempted location was occupied as well

Fourth Attempt (Question)

The next i² value would be 3 * 3 = 9

-------------------------------------------------------------------------------

The next cell will be tried is 9

============================================================================

Hope this helps!

Please let me know if any changes needed.

Thank you!

I hope you're safe during the pandemic.