Part II: HASHING FOR STORAGE: DATA MANAGEMENT
CHAPTER 14
Double Hashing
14.1 FORMULATION OF DOUBLE HASHING1
Double hashing (DH) is an alternative to linear probing and chaining; it replaces the single integer-valued hashing function h from keys k ∈ 
to a cell in a hash table with n cells
with a pair h = (h1, h2) of integer-valued hashing functions
Bell and Kaman [Bell and Kaman 1970] implemented double hashing h = (h1, h2) with their linear quotient code defined by the formulas
- h1(k) = i, the remainder, and
- h2(k) = c, the (modified) quotient
resulting from the modular-like division 
of the key k by the size n of the hash
table. Limited simulation results cited in [Bell and Kaman 1970] suggest that the search cost for double hashing might be those of uniform hashing. Maurer [Maurer 1968] and Radke [Radke 1970] also constructed pairs h = (h1, h2) with other arithmetic functions.
DH-SEARCH (k) with h(k) = (i, c) generates the probe sequence of hash-table cells in decreasing order HTi, HTi−c, HTi−2c, …
- If cell HTi contains k, DH-SEARCH (k) has been successful and ends.
- Otherwise, each key in ...
