Quadratic probing

Quadratic probing is an open addressing scheme for resolving hash collisions in hash tables. When the slot given by the hash function is already taken, it examines further slots by adding successive values of a quadratic polynomial to the original hash index, for example offsets of 1, 4, 9 and 16 squared steps, until an open slot is found. It is often recommended as an alternative to linear probing because it causes less clustering, and it has better locality of reference than approaches such as chaining, although for queries its locality is not as good as linear probing, which can therefore be faster in some settings. The scheme was first introduced by Ward Douglas Maurer in 1968, and later variations in the 1970s aimed to guarantee that the probe sequence visits every slot without cycling early. It underlies several high-performance hash tables, including Google's open-source Abseil hash table. A non-trivial time bound for insertion remains an open problem, although it is conjectured that insertions take expected time proportional to one over epsilon when the table is filled to one minus epsilon.