Quadratic probing is an
open addressing
Open addressing, or closed hashing, is a method of Hash table#Collision resolution, collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternative locations in the array (the ''prob ...
scheme in
computer programming
Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by-step specifications of proc ...
for resolving
hash collisions in
hash table
In computer science, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps Unique key, keys to Value (computer science), values. ...
s. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary
quadratic polynomial
In mathematics, a quadratic function of a single variable is a function of the form
:f(x)=ax^2+bx+c,\quad a \ne 0,
where is its variable, and , , and are coefficients. The expression , especially when treated as an object in itself rather tha ...
until an open slot is found.
An example sequence using quadratic probing is:
Quadratic probing is often recommended as an alternative to
linear probing because it incurs less
clustering. Quadratic probing exhibits better
locality of reference
In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference localit ...
than many other hash table such as
chaining; however, for queries, quadratic probing does not have as good
locality as
linear probing, causing the latter to be faster in some settings.
Quadratic probing was first introduced by Ward Douglas Maurer in 1968.
Quadratic function
Let ''h''(''k'') be a
hash function
A hash function is any Function (mathematics), function that can be used to map data (computing), data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output. The values returned by a ...
that maps an element ''k'' to an integer in
, ''m''−1 where ''m'' is the size of the table. Let the ''i''
th probe position for a value ''k'' be given by the function
:
where ''c''
2 ≠ 0 (If ''c''
2 = 0, then ''h''(''k'',''i'') degrades to a
linear probe). For a given
hash table
In computer science, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps Unique key, keys to Value (computer science), values. ...
, the values of ''c''
1 and ''c''
2 remain constant.
Examples:
*If
, then the probe sequence will be
*For ''m'' = 2
''n'', a good choice for the constants are ''c''
1 = ''c''
2 = 1/2, as the values of ''h''(''k'',''i'') for ''i'' in
, ''m''−1are all distinct (in fact, it is a permutation on
, ''m''−1. This leads to a probe sequence of
(the
triangular numbers
A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots in ...
) where the values increase by 1, 2, 3, ...
*For prime ''m'' > 2, most choices of ''c''
1 and ''c''
2 will make ''h''(''k'',''i'') distinct for ''i'' in
, (''m''−1)/2 Such choices include ''c''
1 = ''c''
2 = 1/2, ''c''
1 = ''c''
2 = 1, and ''c''
1 = 0, ''c''
2 = 1. However, there are only ''m''/2 distinct probes for a given element, requiring other techniques to guarantee that insertions will succeed when the load factor exceeds 1/2.
*For
, where ''m'', ''n'', and ''p'' are integer greater or equal 2 (degrades to linear probe when ''p'' = 1), then
gives cycle of all distinct probes. It can be computed in loop as:
, and
*For any ''m'', full cycle with quadratic probing can be achieved by rounding up ''m'' to closest power of 2, compute probe index:
, and skip iteration when
. There is maximum
skipped iterations, and these iterations do not refer to memory, so it is fast operation on most modern processors. Rounding up ''m'' can be computed by:
uint64_t roundUp2(uint64_t v)
Limitations
Alternating signs
If the sign of the offset is alternated (e.g. +1, −4, +9, −16, etc.), and if the number of buckets is a prime number
congruent to 3 modulo 4 (e.g. 3, 7, 11, 19, 23, 31, etc.), then the first
offsets will be unique (modulo
). In other words, a permutation of 0 through
is obtained, and, consequently, a free bucket will always be found as long as at least one exists.
References
{{reflist
External links
Tutorial/quadratic probing
Hashing
Articles with example C code
Articles with example Java code
Search algorithms