- Quadratic probing
Quadratic probing is a scheme in
computer programmingfor resolving collisions in hash tables.
Quadratic probing operates by taking the original hash value and adding successive values of an arbitrary
quadratic polynomialto the starting value. This algorithm is used in open-addressed hash tables. Quadratic probing provides good memory caching because it preserves some locality of reference; however, linear probinghas greater locality and, thus, better cache performance. Quadratic probing better avoids the clustering problem that can occur with linear probing, although it is not immune.
Quadratic probing is used in the
Berkeley Fast File Systemto allocate free blocks. The allocation routine chooses a new cylinder-group when the current is nearly full using quadratic probing, because of the speed it shows in finding unused cylinder-groups.
Quadratic probing is a "classical" method to deal with collisions.A recent development to deal with collisions in
hash tables ina potentially more efficient manner is cuckoo hashing.
Quadratic Probing Algorithm
Let be a
hash functionthat maps an element to an integer in , where is the size of the table.
Let the th probe position for a value be given by the function , where . If , then degrades to a linear probe. For a given
hash table, the values of and remain constant.
Example: If , then the probe sequence will be
For , a good choice for the constants are 1/2, as the values for in are all distinct. [Proof: assume there exist i,j such that i,j in and (i+i^2)/2 = (j+j^2)/2 mod m. Then i+i^2 = j+j^2 mod 2m, i^2-j^2 + i-j = 0 mod 2m, (i-j)(i+j) + (i-j) = 0 mod 2m, and (i-j)(i+j+1) = 0 mod 2m. Since 2m is a power of 2, and only one of the two factors can be even, we must have i-j = 0 mod 2m or i+j+1 = 0 mod 2m. The latter is not possible with i,j in , and the former implies that i=j. ] This leads to a probe sequence of where the values increase by .
For prime , most choices of and will make distinct for in . Such choices include 1/2, 1, and . 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.
Wikimedia Foundation. 2010.
Look at other dictionaries:
Quadratic — In mathematics, the term quadratic describes something that pertains to squares, to the operation of squaring, to terms of the second degree, or equations or formulas that involve such terms. Quadratus is Latin for square . Mathematics Algebra… … Wikipedia
Linear probing — is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location. [cite book |last=Dale |first=Nell |title=C++ Plus Data Structures |year=2003… … Wikipedia
Open addressing — Hash collision resolved by linear probing (interval=1). 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 alternate locations in… … Wikipedia
Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space … Wikipedia
Double hashing — is a computer programming technique used in hash tables to resolve hash collisions, cases when two different values to be searched for produce the same hash key. It is a popular collision resolution technique in open addressed hash tables. Like… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Cuckoo hashing — example. The arrows show the alternative location of each key. A new item would be inserted in the location of A by moving A to its alternative location, currently occupied by B, and moving B to its alternative location which is currently vacant … Wikipedia
Swami Bharati Krishna Tirtha's Vedic mathematics — For the actual mathematics of the Vedic period, see the articles on Sulba Sūtras and Indian mathematics.Swami Bharati Krishna Tirtha s Vedic mathematics is a system of mathematics consisting of a list of 16 basic sūtras, or aphorisms. They were… … Wikipedia