(algorithm)
Definition: A method of open addressing for a hash table in which a collision is resolved by searching the table for an empty place at intervals given by a different hash function, thus minimizing clustering.
Also known as rehashing.
See also linear probing, hash table.
Note: Since a different hashing function is used to find a location in case of collision, colliding values should be spread out. In linear probing, primary clustering occurs when collisions fill up every space for long stretches. Even in quadratic probing, secondary clustering may develop since colliding values follow the same probe sequence.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 16 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "double hashing", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/doublehashng.html