NIST

double hashing

(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

Implementation

insert (C and Pascal), search (C and Pascal)
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 16 November 2009.
HTML page formatted Fri Feb 23 10:06:07 2018.

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: https://www.nist.gov/dads/HTML/doublehashng.html