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

displaymath62213

However, quadratic probing is usually done using tex2html_wrap_inline62219.

Clearly, tex2html_wrap_inline62219 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_inline62227 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_inline62233, that probe exactly the same position. Thus,

eqnarray13240

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_inline62251. Furthermore, since both i and j are less than tex2html_wrap_inline62227, 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_inline62015, this occurs when tex2html_wrap_inline62267.

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

eqnarray13245


next up previous contents index

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