Hashing

Double Hashing

This is an alternative to Linear Probing. Learning in CS240.

Double hashing: open addressing with probe sequence $h(k,i)=(h_0(k)+i\cdot h_1(k))\mathrm{mod}M$

• search, insert, delete work just like for Linear Probing, but with this different probe sequence.

Independent Hash Functions

The two hash functions should be independent. Using two modular hash-functions may often lead to dependencies. This is why we use multiplication method for second hash function: $h(k)=\lfloor M(kA-\lfloor kA\rfloor )\rfloor$, where

• $A$ is some floating-point number with $0<A<1$ $kA-\lfloor kA\rfloor$ computes fractional part of $kA$, which is in $[0,1)$
• Multiply with $M$ to get floating-point number in $[0,M)$
• Round down to get integer in $\{0,...,M-1\}$

Some observations/suggestions:

• Multiplying with $A$ is used to scramble the keys.
• Good scrambling is achieved with $A=\phi =\frac{\surd 5-1}{2}\approx \mathrm{0.618033988749.....}$