Quadratic probing is an open addressing scheme in computer programming for resolving collisions in hash tables—when an incoming data's hash value indicates it should be stored in an already-occupied slot or bucket. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found.
For a given hash value, the indices generated by linear probing are as follows:
This method results in primary clustering, and as the cluster grows larger, the search for those items hashing within the cluster becomes less efficient.
An example sequence using quadratic probing is:
Quadratic probing can be a more efficient algorithm in a closed hash table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune. It also provides good memory caching because it preserves some locality of reference; however, linear probing has greater locality and, thus, better cache performance.
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.
Read more about Quadratic Probing: Quadratic Function, Quadratic Probing Insertion, Limitations
Famous quotes containing the word probing:
“Industrial societies turn their citizens into image-junkies; it is the most irresistible form of mental pollution. Poignant longings for beauty, for an end to probing below the surface, for a redemption and celebration of the body of the world. Ultimately, having an experience becomes identical with taking a photograph of it.”
—Susan Sontag (b. 1933)