Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Quadratic Probing

An alternative to linear probing that addresses the primary clustering problem is called quadratic probing . In quadratic probing, the function c(i) is a quadratic function in i.gif The general quadratic has the form


However, quadratic probing is usually done using tex2html_wrap_inline63068.

Clearly, tex2html_wrap_inline63068 satisfies property 1. What is not so clear is whether it satisfies property 2. In fact, in general it does not. The following theorem gives the conditions under which quadratic probing works:

Theorem  When quadratic probing is used in a table of size M, where M is a prime number, the first tex2html_wrap_inline63076 probes are distinct.

extbfProof (By contradiction). Let us assume that the theorem is false. Then there exist two distinct values i and j such that tex2html_wrap_inline63082, that probe exactly the same position. Thus,


Since M is a prime number, the only way that the product (i-j)(i+j) can be zero modulo M is for either i-j to be zero or i+j to be zero modulo M. Since i and j are distinct, tex2html_wrap_inline63100. Furthermore, since both i and j are less than tex2html_wrap_inline63076, the sum i+j is less than M. Consequently, the sum cannot be zero. We have successfully argued an absurdity--if the theorem is false one of two quantities must be zero, neither of which can possibly be zero. Therefore, the original assumption is not correct and the theorem is true.

Applying Theorem gif we get that quadratic probing works as long as the table size is prime and there are fewer than n=M/2 items in the table. In terms of the load factor tex2html_wrap_inline62864, this occurs when tex2html_wrap_inline63116.

Quadratic probing eliminates the primary clustering phenomenon of linear probing because instead of doing a linear search, it does a quadratic search:


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.