2
$\begingroup$

For quadratic hashing, i.e an open-addressed table with the hash function of the form -

$h(x, i)= (h'(x) + c_1i + c_2i^2) \mod m$

Setting $c_1 = c_2 = 1/2$, and $m$ to some power of 2, leads to a hash function

$h(x, i) = (h'(x) + 1 + 2 + ... +i) \mod m$

I have read that the load-factor of a quadratically probed table should not exceed $0.5$ to guarantee insertion to succeed if an empty cell exists in the table. Wikipedia's article here https://en.wikipedia.org/wiki/Quadratic_probing#Limitations says that

"With the exception of the triangular number case for a power-of-two-sized hash table, there is no guarantee of finding an empty cell once the table gets more than half full, or even before the table gets half full if the table size is not prime. "

So what is the maximum load factor that will guarantee successful insertion for this case?

$\endgroup$
4
$\begingroup$

For the case you describe ($c_1=c_2=1/2$, $m=2^k$), you can reach a load factor of 1. The probe sequence touches all the cells in the table.

As a practical matter, you probably don't want to get really close to a load factor of 1, as the probing can take $O(n)$ time.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.