Quadratic Probing - Quadratic Function

Quadratic Function

Let h(k) be a hash function that maps an element k to an integer in, where m is the size of the table. Let the ith probe position for a value k be given by the function

where c₂ ≠ 0. If c₂ = 0, then h(k,i) degrades to a linear probe. For a given hash table, the values of c₁ and c₂ remain constant.

Examples:

• If, then the probe sequence will be
• For m = 2n, a good choice for the constants are c₁ = c₂ = 1/2, as the values of h(k,i) for i in are all distinct. This leads to a probe sequence of where the values increase by 1, 2, 3, ...
• For prime m > 2, most choices of c₁ and c₂ will make h(k,i) distinct for i in . Such choices include c₁ = c₂ = 1/2, c₁ = c₂ = 1, and c₁ = 0, c₂ = 1. Because there are only about m/2 distinct probes for a given element, it is difficult to guarantee that insertions will succeed when the load factor is > 1/2.