committedandroider - 1 year ago 117
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):

ii.May not find a location on the next insertion

iii.None of the above

ii.May not find a location on the next insertion

iii.None of the above

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"

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?

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 + '  ';
}