# Quadratic Probing Infinite Loop?

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?

• 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. – Hendrik Jan Feb 21 '20 at 15:15
• 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. – Hendrik Jan Feb 21 '20 at 15:18

## 2 Answers

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.

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