# 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 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