Editing Double hashing (section)

=== Enhanced double hashing ===

Adding a [[cubic function|cubic term]] <math>i^3</math><ref name=Kirsch08/> or <math>(i^3-i)/6</math> (a [[tetrahedral number]]),<ref name=Dillinger04>{{cite conference
 |title=Bloom Filters in Probabilistic Verification
 |first1=Peter C. |last1=Dillinger  |first2=Panagiotis |last2=Manolios
 |conference=5h International Conference on Formal Methods in Computer Aided Design (FMCAD 2004)
 |location=Austin, Texas |date=November 15–17, 2004
 |doi=10.1007/978-3-540-30494-4_26 |citeseerx=10.1.1.119.628
 |url=https://www.khoury.northeastern.edu/~pete/pub/bloom-filters-verification.pdf
}}</ref> does solve the problem, a technique known as '''enhanced double hashing'''.  This can be computed efficiently by [[Forward difference|forward differencing]]:
<syntaxhighlight lang="c">
struct key;	/// Opaque
/// Use other data types when needed. (Must be unsigned for guaranteed wrapping.)
extern unsigned int h1(struct key const *), h2(struct key const *);

/// Calculate k hash values from two underlying hash functions
/// 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 ext_dbl_hash(struct key const *x, unsigned int hashes[], unsigned int n)
{
	unsigned int a = h1(x), b = h2(x), i = 0;

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

In addition to rectifying the collision problem, enhanced double hashing also removes double-hashing's numerical restrictions on <math>h_2(x)</math>'s properties, allowing a hash function similar in property to (but still independent of) <math>h_1</math> to be used.<ref name=Dillinger04/>