Reasons as to use Quadratic Probing for Hash table implementation

Question

I have been learning about Hash Tables lately. There are a couple of examples of Collision Resolutions and one of them is Quadratic probing.Why would someone use quadratic probing? Does he know that the hash table will always be less than half full? And if so why does he use such a big table to begin with?

Answer 1

Why would someone use quadratic probing?

Assuming we need some collision resolution algorithm,

Quadratic probing can be a more efficient algorithm in a closed hash table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune.

(From Wikipedia)

Quadratic probing isn't perfect, but it does offer some advantages over alternatives:

The advantages of quadratic (or other forms of) chaining are

• simpler logic for storage management (no dynamic allocation)
• faster inserts (for reason of simpler storage)
• reduced storage requirement in general

(from mjv's answer)

Does he know that the hash table will always be less than half full?

Not necessarily; it depends on the resizing strategy used, if any.

Consider your learning on QP to be primarily educational. Practical hash table implementations don't often use open addressing, in my experience.

Answer 2

Quadratic rehash is a very simple and fast way to avoid the clustering problem of linear hash. It's normally used only when table size is prime (which may also be good for other reasons).

To avoid any worry about "table being half-full" it is simplest to switch to linear probe at some point. (You can put the threshold test for such switching inside the usual if (index >= size) {index -= size;} block, to avoid any performance loss.