Limit for quadratic probing a hash table

Question

I was doing a program to compare the average and maximum accesses required for linear probing, quadratic probing and separate chaining in hash table.

I had done the element insertion part for 3 cases. While finding the element from hash table, I need to have a limit for ending the searching. In the case of separate chaining, I can stop when next pointer is null. For linear probing, I can stop when probed the whole table (ie size of table). What should I use as limit in quadratic probing? Will table size do?

My quadratic probing function is like this

newKey = (key + i*i) % size;

where i varies from 0 to infinity. Please help me..

Answer 1

For such problems analyse the growth of i in two pieces:

First Interval : i goes from 0 to size-1

In this case, I haven't got the solution for now. Hopefully will update.

Second Interval : i goes from size to infinity

In this case i can be expressed as i = size + k, then

newKey = (key + i*i) % size 
       = (key + (size+k)*(size+k)) % size
       = (key + size*size + 2*k*size + k*k) % size
       = (key + k*k) % size

So it's sure that we will start probing previously probed cells, after i reaches to size. So you only need to consider the situation where i goes from 0 to size-1. Because rest is only the same story again and again.

What the story tells up to now: A simple analysis showed me that I need to probe at most size times because beyond size times I started probing the same cells.

Answer 2

See this link. If your table size is power of 2 and you are using a reprobe function f(i)=i*(i+1)/2, you are guaranteed to traverse the entire table. If your table size is a prime number, you are guaranteed to traverse at least half of the table. In general, you can check if at some point you are back to the original point. If that happens, you need to rehash.

Answer 3

After doing some simulations in Excel, it appears that iterating up to i = size / 2 would be all that needs to be tested. This is when using the standard method of adding sequential perfect squares to the single-hashed position.

The answer that you can quit if a position is revisited would not allow testing of all possible positions that could be reached by the quadratic-probe method, at least not for all array sizes. (I tested array size 21 and found that i=5 revisits the same position as i=2, but i=6 yields a previously not-calculated position.)