Quadratic probing


Quadratic probing

Quadratic probing is a scheme in computer programming for resolving collisions in hash tables.

Quadratic probing operates by taking the original hash value and adding successive values of an arbitrary quadratic polynomial to 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 probing has 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 System to 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 h(k) be a hash function that maps an element k to an integer in [0,m-1] , where m is the size of the table.

Let the ith probe position for a value k be given by the function h(k,i) = ( h(k) + c_1 i + c_2 i^2 ) pmod{m}, where c_2 eq 0. If c_2 = 0, then h(k,i) degrades to a linear probe. For a given hash table, the values of c_1 and c_2 remain constant.

Example: If h(k,i) = (h(k) + i + i^2) pmod{m}, then the probe sequence will be h(k), h(k)+2, h(k)+6, ...

For m = 2^n, a good choice for the constants are c_1 = c_2 = 1/2, as the values h(k,i) for i in [0,m-1] are all distinct. [Proof: assume there exist i,j such that i,j in [0,m-1] 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 [0,m-1] , and the former implies that i=j. ] This leads to a probe sequence of h(k), h(k)+1, h(k)+3, h(k)+6, ... 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 [0, (m-1)/2] . Such choices include c_1 = c_2 =1/2, c_1 = c_2 =1, and c_1 = 0, c_2 = 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.

ee also

* Hash tables
* Hash collision
* Double hashing
* Linear probing
* Hash function

Notes

References


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