How can quadratic probing fail to find a location on the next insertion while linear probing always finds one?

Question

    I am doing a practice question from Data Structures Practice

The Question
   1.Linear Probing will (circle one):
        i.gradually degrade in performance as more values are inserted
       ii.May not find a location on the next insertion
       iii.None of the above

   2.Quadratic Probing will (circle one):
        i.gradually degrade in performance as more values are inserted
       ii.May not find a location on the next insertion
       iii.None of the above

According to the answer key(from the link), the answer to 1 is i and the answer to 2 is ii.

I agree with the answer question 1. Linear probing will explore all possibilities and wrap to the beginning of the hashtable if needed. Therefore it will find a location on the next insertion. If you insert a bunch of values that map to the same bucket or near one bucket, clustering will result and performance will degrade.
I understand why the the answer to question 2 isn't i. Quadratic increment probs by different increments to avoid the clustering issue. However can some explain the intution behind how quadratic probing "may not find a location on the next insertion"
A quadratic probing function is defined with (from Quadratic Probing)
nth probe being ((h(k) + n²) mod TableSize) until the probe hits a zero(unoccupied)

From what I learned in my other question Quadratic Probing, it is possible for a quadratic probe to hit every bucket. Like the linear probe, the quadratic probe should also wrap tot he beginning of the hashtable if needed. Why then in this question, can a quadratic probe not find a location on the next insertion while a linear probe can?

Answer 1

To find out if h(k) + n^2 searches all possibilities you need to find out if n^2 takes up all possible values mod the hash table size - say N. So you need to know if by choosing all the N possibilities for n you can have n^2 take up all the N possible different values.

(-n)^2 = n^2 so here are different input values to the square function that produce the same output values. So it is not possible to produce all the N different output values, because there are collisions between the results of the different input values.

Example - work mod 7. 1^2 = 6^2 = 1. 2^2 = 5^2 = 4. 3^2 = 4^2 = 2. 7^2 = 0. So if you square the inputs (0, 1, 2, 3, 4, 5, 6) you get the outputs (0, 1, 4, 2, 2, 4, 1) and you cannot produce 3, 5, or 6 - in fact this example is enough to show that you cannot guarantee to search all possible slots, but the math above is neat enough to be more reliable than my arithmetic, as well as showing that the behaviour here is pretty general.

Answer 2

I think the question is about in what case quadratic probing will not be able to find the next location at all in case there is a collision.

With the below example, I do see that quadratic probing is not able to find a location in case of collisions with same resultant key.

Let's say the hash table size is 7.

Here are the numbers to be inserted 23, 39, 9, 16, 30.

h(k, i) = [h(k) + sqr(i)] mod 7 where h(k) = k mod 7.

for i = 0, h(k,0) = h(k)
for i = 1, h(k,1) = [h(k) + 1] mod 7
for i = 2, h(k,2) = [h(k) + 4] mod 7
for i = 3, h(k,3) = [h(k) + 9] mod 7

23 --> 23 % 7 = 2

39 --> 39 % 7 = 4

9  --> 9 % 7 = 2 <--- Collision
   2 + 1 = 3

16 --> 16 % 7 = 2 <--- Collision
   2 + 1 = 3 <--- Collision
   2 + 4 = 6

30 --> 30 % 7 = 2 <--- Collision

   2 + 1 = 3 <--- Collision

   2 + 4 = 6 <--- Collision
   2 + 9 = 4 <--- Collision
   2 + 16 = 4 <--- Collision
   2 + 25 = 6 <--- Collision
   2 + 36 = 3 <--- Collision
   2 + 49 = 2 <--- Collision
   2 + 64 = 3 <--- Collision
   2 + 81 = 6 <--- Collision
   2 + 100 = 4 <--- Collision
   2 + 121 = 4 <--- Collision
   2 + 144 = 6 <--- Collision
   2 + 169 = 3 <--- Collision
   2 + 196 = 2 <--- Collision
   2 + 225 = 3 <--- Collision
   2 + 256 = 6 <--- Collision
   2 + 289 = 4 <--- Collision
   2 + 324 = 4 <--- Collision
   2 + 361 = 6 <--- Collision
   2 + 400 = 3 <--- Collision

This would be the case with any key k with (k mod size) equal to 2 (like 37, 44, 51, 58, etc.