Quadratic Probing (Module 7)

Question 1

Which probing method uses a quadratic function to determine the next index?

Answer 1

quadratic probing

Question 2

What is quadratric probing’s primary hash function?

Answer 2

hash(k)

Question 3

What is quadratic probing’s formula?

Answer 3

(hash(k) + i^2) mod m

Question 4

In quadratic probing, what happens when multiple key hash to the same initial index value?

Answer 4

they share the same probe sequence

Question 5

What type of clustering happens when clusters form for keys with the same hash value?

Answer 5

secondary clustering

Question 6

What is an advantage of quadratic probing?

Answer 6

reduces primary clustering (compared to linear probing)

Question 7

What are disadvantages of quadratic probing?

Answer 7

• possible secondary clustering
• needs custom table size so all slots can be probed