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?

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. Feb 21, 2020 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. Feb 21, 2020 at 15:18

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.