1
$\begingroup$

I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic probing cannot find an empty slot for a new element?

According to https://en.wikipedia.org/wiki/Quadratic_probing:

In the case of quadratic probing, with the exception of the triangular number case for a power-of-two-sized hash table[2], 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.

Does this mean that Load Factor should always be 0.5 for a Hash Table that uses Quadratic Probing?

What is the proof of this claim?

$\endgroup$
  • 1
    $\begingroup$ Some sources suggest a variant to quadratic probing, and look for positive and negative offsets: $h(K) \pm i^2$. That will for prime table size (3 mod 4) probe all adresses. It is a variant of the "alternating sign" approach at the bottom of the Wikipedia page. But, as others have remarked in their answer, when it takes that long to find an empty spot, something is clearly wrong, and measures have to be taken. $\endgroup$ – Hendrik Jan Feb 21 at 15:15
  • $\begingroup$ The proof of the claim you quote is simply that $i^2 = (M-i)^2$ modulo table size $M$. So step $i$ and step $M-i$ lead to the same address. $\endgroup$ – Hendrik Jan Feb 21 at 15:18
2
$\begingroup$

No. It means you should count how many slots you have checked, and if you have checked more than the available number of slots, you resize the table.

In practice, if you regularly visit more than ten slots, then either the hash function is bad (nothing you can do about it while your program is running), or your load factor is too large. Not finding an empty slot will only happen if an attacker can decide your hash values.

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

With quadratic probing (assuming table size is a prime) you'll check exactly half the entries for an alternative empty slot (only half of the numbers are squares modulo $p$). In practice, you'll resize the table long, long before you reach such lengths of searches.

For any probing sequence, it should only repeat in a full cycle (like linear probing --full array checked-- or quadratic probing --exactly half of the entries checked before repeating) you must check if you ended up at the starting point (and won't find an empty slot).

| 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.