data-structureshashtablequadratic-probing

Reasons as to use Quadratic Probing for Hash table implementation


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?


Solution

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