Quadratic probing is an
open addressing
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternative locations in the array (the ''probe sequence'') until either the t ...
scheme in
computer programming for resolving
hash collisions
In computer science, a hash collision or hash clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits.
Al ...
in
hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...
s. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary
quadratic polynomial
In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomi ...
until an open slot is found.
An example sequence using quadratic probing is:
Quadratic probing can be a more efficient algorithm in an
open addressing
Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternative locations in the array (the ''probe sequence'') until either the t ...
table, since it better avoids the clustering problem that can occur with
linear probing
Linear probing is a scheme in computer programming for resolving collisions in hash tables, data structures for maintaining a collection of key–value pairs and looking up the value associated with a given key. It was invented in 1954 by Gene ...
, although it is not immune. It also provides good memory caching because it preserves some
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 ...
; however, linear probing has greater locality and, thus, better cache performance.
Quadratic function
Let ''h''(''k'') be a
hash function
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually ...
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 computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...
, 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. 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