 | This article needs additional citations for verification. (September 2019) |
Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial 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.[1] Quadratic probing exhibits better locality of reference 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.[2]
Quadratic probing was first introduced by Ward Douglas Maurer in 1968.[3]
- ^ Cormen, Thomas H.; Leiserson, Charles Eric; Rivest, Ronald Linn; Stein, Clifford (2009). Introduction to algorithms (3rd ed.). Cambridge, Massachusetts London, England: MIT Press. ISBN 978-0-262-53305-8.
- ^ Richter, Stefan; Alvarez, Victor; Dittrich, Jens (2015). "A seven-dimensional analysis of hashing methods and its implications on query processing". Proceedings of the VLDB Endowment. 9 (3): 96–107. doi:10.14778/2850583.2850585. ISSN 2150-8097.
- ^ Maurer, W. D. (1968). "Programming Technique: An improved hash code for scatter storage". Communications of the ACM. 11 (1): 35–38. doi:10.1145/362851.362880. ISSN 0001-0782.