committedandroider committedandroider - 5 months ago 18
Java Question

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

    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) + n2) 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

There must be a proof for this out there somewhere. But, I don't see how quadratic probing could hit every bucket in most cases.

Let's say the table size is 7, and h(k) is 0. For the ith iteration, probe = i^2 mod 7. I tested all i less than 10,000 and this always evaluates to 0, 1, 2, or 4 for any i. Buckets 3, 5, and 6 will never be probed.

Here's the script I used:

var hash_of_k = 0;
var table_size = 7;
var iteration_limit = 10000;
var buckets =  new Object();

//Probe buckets
for(var i=0; i<iteration_limit; i++){
  b = (hash_of_k+(i*i)) % table_size;
  buckets[b] = 1;
}

//Report which buckets were probed.
var buckets_probed = '';
for(b in buckets){
  buckets_probed += b + '  ';
}

alert(buckets_probed);

You could set the iteration limit higher, but that just doesn't seem practical. It seems like the whole point of quadratic probing would be to find an empty bucket faster than linear probing.

Comments