Double hashing

The secondary hash function ${\displaystyle h_{2}(k)}$ should have several characteristics:

• it should never yield an index of zero
• it should cycle through the whole table
• it should be very fast to compute
• it should be pair-wise independent of ${\displaystyle h_{1}(k)}$
• The distribution characteristics of ${\displaystyle h_{2}}$ are irrelevant. It is analogous to a random-number generator - it is only necessary that ${\displaystyle h_{2}}$ be ’’relatively prime’’ to |T|.

In practice, if division hashing is used for both functions, the divisors are chosen as primes.

Let ${\displaystyle n}$ be the number of elements stored in ${\displaystyle T}$, then ${\displaystyle T}$'s load factor is ${\displaystyle \alpha =n/|T|}$. That is, start by randomly, uniformly and independently selecting two universal hash functions ${\displaystyle h_{1}}$ and ${\displaystyle h_{2}}$ to build a double hashing table ${\displaystyle T}$. All elements are put in ${\displaystyle T}$ by double hashing using ${\displaystyle h_{1}}$ and ${\displaystyle h_{2}}$. Given a key ${\displaystyle k}$, the ${\displaystyle (i+1)}$-st hash location is computed by:

${\displaystyle h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.}$

Let ${\displaystyle T}$ have fixed load factor ${\displaystyle \alpha :1>\alpha >0}$.

Bradford and Katehakis[1] showed the expected number of probes for an unsuccessful search in ${\displaystyle T}$, still using these initially chosen hash functions, is ${\displaystyle {\frac {1}{1-\alpha }}}$ regardless of the distribution of the inputs. Pair-wise independence of the hash functions suffices.

Like all other forms of open addressing, double hashing becomes linear as the hash table approaches maximum capacity. The usual heuristic is to limit the table loading to 75% of capacity. Eventually, rehashing to a larger size will be necessary, as with all other open addressing schemes.

Peter Dillinger's PhD thesis[2] points out that double hashing produces unwanted equivalent hash functions when the hash functions are treated as a set, as in Bloom filters: If ${\displaystyle h_{2}(y)=-h_{2}(x)}$ and ${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)}$, then ${\displaystyle h(i,y)=h(k-i,x)}$ and the sets of hashes ${\displaystyle \left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y)\right\}}$ are identical. This makes a collision twice as likely as the hoped-for ${\displaystyle 1/|T|^{2}}$.

There are additionally a significant number of mostly-overlapping hash sets; if ${\displaystyle h_{2}(y)=h_{2}(x)}$ and ${\displaystyle h1(y)=h1(x)\pm h_{2}(x)}$, then ${\displaystyle h(i,y)=h(i\pm 1,x)}$, and comparing additional hash values (expanding the range of ${\displaystyle i}$) is of no help.

Adding a quadratic term ${\displaystyle i^{2},}$[3] ${\displaystyle i(i+1)/2}$ (a triangular number) or even ${\displaystyle i^{2}\cdot h_{3}(x)}$ (triple hashing) to the hash function improves the hash function somewhat[3] but does not fix this problem; if:

${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)+k^{2}\cdot h_{3}(x),}$

${\displaystyle h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x),}$ and

${\displaystyle h_{3}(y)=h_{3}(x).}$

then

${\displaystyle {\begin{aligned}h(k-i,y)&=h_{1}(y)+(k-i)\cdot h_{2}(y)+(k-i)^{2}\cdot h_{3}(y)\\&=h_{1}(y)+(k-i)(-h_{2}(x)-2kh_{3}(x))+(k-i)^{2}h_{3}(x)\\&=h_{1}(y)+(i-k)h_{2}(x)+(2ki-2k^{2})h_{3}(x)+(k^{2}-2ki+i^{2})h_{3}(x)\\&=h_{1}(y)+(i-k)h_{2}(x)+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(i-k)h_{2}(x)+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3}(x)\\&=h(i,x).\\\end{aligned}}}$

Adding a cubic term ${\displaystyle i^{3}}$[3] or ${\displaystyle (i^{3}-i)/6}$ (a tetrahedral number),[4] does solve the problem, a technique known as enhanced double hashing. This can be computed efficiently by forward differencing:

struct key;	// Opaque
extern unsigned int h1(struct key const *), h2(struct key const *);

// Calculate k hash values from two underlying hash function
// h1() and h2() using enhanced double hashing.  On return,
// hashes[i] = h1(x) + i*h2(x) + (i*i*i - i)/6
// Takes advantage of automatic wrapping (modular reduction)
// of unsigned types in C.
void hash(struct key const *x, unsigned int hashes[], unsigned int n)
{
	unsigned int a = h1(x), b = h2(x), i;

	for (i = 0; i < n; i++) { 
		hashes[i] = a;
		a += b;	// Add quadratic difference to get cubic
		b += i;	// Add linear difference to get quadratic
		       	// i++ adds constant difference to get linear
	}
}

• Cuckoo hashing
• 2-choice hashing

• How Caching Affects Hashing by Gregory L. Heileman and Wenbin Luo 2005.
• Hash Table Animation
• klib a C library that includes double hashing functionality.