# 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⋅h_{1}(k))modM$

*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)=⌊M(kA−⌊kA⌋)⌋$, where

- $A$ is some floating-point number with $0<A<1$ $kA−⌊kA⌋$ 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=φ=2√5−1 ≈0.618033988749.....$