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 kx1D4A6_EuclidMathOne_10n_000100 to a cell in a hash table with n cells

c14ue001

with a pair h = (h1, h2) of integer-valued hashing functions

c14ue002

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 c14ue003 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, HTic, HTi−2c, …

  • If cell HTi contains k, DH-SEARCH (k) has been successful and ends.
  • Otherwise, each key in ...

Get Hashing in Computer Science: Fifty Years of Slicing and Dicing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.