Double hashing

Short description: Computer programming technique

Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is a classical data structure on a table T.

The double hashing technique uses one hash value as an index into the table and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is set by a second, independent hash function. Unlike the alternative collision-resolution methods of linear probing and quadratic probing, the interval depends on the data, so that values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering.

Given two random, uniform, and independent hash functions h1 and h2, the ith location in the bucket sequence for value x in a hash table of |T| buckets is: h(i,x)=(h1(x)+i⋅h2(x))mod|T|. The locations can be conveniently calculated by incrementing the previous hash by h2(x), i.e. h(i+1,x)=(h(i,x)+h2(x))mod|T|.

Generally, h1 and h2 are selected from a set of universal hash functions; h1 is selected to have a range of {0,|T|−1} and h2 to have a range of {1,|T|−1}. Double hashing approximates a random distribution; more precisely, pair-wise independent hash functions yield a probability of (n/|T|)2 that any pair of keys will follow the same bucket sequence.

## Contents

* 1 Selection of h2(x)
* 2 Analysis
* 3 Variants
* 3.1 Triple hashing
* 3.2 Enhanced double hashing
* 4 See also
* 5 References
* 6 External links

## Selection of h2(x)

The secondary hash function h2(x) should have several characteristics:[1]

1. It should never yield an index of zero. When 0 is returned, only one index is probed.
2. All h2(x) should be relatively prime to |T|. Otherwise the number of indices probed over k items would be min⁡(k,|T|/h2(x)), which could be as small as 2.
3. It should cycle through the whole table.
4. It should be very fast to compute.
5. It should be pair-wise independent of h1(x).

The distribution characteristics of h2 are irrelevant. It is analogous to a random-number generator.

In practice:

* If division hashing is used for both functions, the divisors are chosen as primes.
* If |T| is a power of 2, the first two requirements are usually satisfied by making h2(x) always return an odd number by setting the least significant bit to 1 (h2(x)=h2,orig(x)|1). This has the side effect of doubling the chance of collision due to one wasted bit.[1]

## Analysis

Suppose one selects two hash functions h1 and h2 and inserts α|T| elements into a hash table with |T| slots. Suppose each insertion of a key x places the key in the first available slot from the sequence h(0,x),h(1,x),h(2,x),… defined by

h(i,x)=(h1(x)+i⋅h2(x))mod|T|.

Given this setup, theoretical analyses seek to determine the time needed to perform an additional insertion (or, equivalently, the time needed to perform an unsuccessful search). Guibas and Szemerédi[2] proved in 1978 that, if h1 and h2 are uniformly random, and α<0.319, then the expected time is O(1). Subsequent work by Lueker and Molodowitch[3] proved a bound of 1/(1−α) for any α, and established that the behavior of the hash table can be directly coupled to that of a standard random-probing based solution. Much more recently, in 2007, Bradford and Katehakis[4] showed that even using universal hash functions, rather than fully random ones, suffices to get a 1/(1−α) bound.

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.

## Variants

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

There are additionally a significant number of mostly-overlapping hash sets; if h2(y)=h2(x) and h1(y)=h1(x)±h2(x), then h(i,y)=h(i±1,x), and comparing additional hash values (expanding the range of i) is of no help.

### Triple hashing

Adding a third hash as a quadratic term (triple hashing) makes the overlap a lot less likely, since equivalent classes now need to be generated by a collaboration of both h2(x) and h3(x), at a cost of 50% more calculations due to the added hash function. Choices for the factor for this h3(x) include i2[6] and the triangular numbers i(i±1)/2. The added hash function should obey the same requirements as listed above for h2(x).[1]

Using the triangular numbers make it easier to calculate the value by forward differencing: for the i(i−2)/2 variety,[1]

from collections.abc import Iterator, Callable
from typing import TypeVar

T = TypeVar('T')
hashfunc = Callable[T, int]
# assume h1, h2, h3 are defined and of type hashfunc

MODULUS = (1 << 32)

def triple_hash(key: T, k: int) -> Iterator[int]:
"""Return k iterations of a triple hash."""
x, y, z = h1(key), h2(key), h3(key)
yield x
for i in range(1, k-1):
x = (x + y) % MODULUS
y = (y + z) % MODULUS
yield x

This kind of construction does not fully remove equivalent sets. If:

h1(y)=h1(x)+k⋅h2(x)+k2⋅h3(x),
h2(y)=−h2(x)−2k⋅h3(x), and
h3(y)=h3(x).

then

h(k−i,y)=h1(y)+(k−i)⋅h2(y)+(k−i)2⋅h3(y)=h1(y)+(k−i)(−h2(x)−2kh3(x))+(k−i)2h3(x)=…=h1(x)+kh2(x)+k2h3(x)+(i−k)h2(x)+(i2−k2)h3(x)=h1(x)+ih2(x)+i2h3(x)=h(i,x).

### Enhanced double hashing

Adding a cubic term i3[6] or (i3−i)/6 (a tetrahedral number),[1] does solve the problem, a technique known as enhanced double hashing. The tetrahedral number can be computed efficiently by forward differencing:

struct key;	/// Opaque
/// Replace "unsigned int" with other types as needed. (Must be unsigned for guaranteed wrapping.)
typedef unsigned int hashfunc(struct key const *);
extern hashfunc h1, h2;

/// 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;

In addition to rectifying the collision problem, enhanced double hashing also removes double-hashing's numerical restrictions on h2(x)'s properties, allowing a hash function similar in property to (but still independent of) h1 to be used. (Using the numbering in § Selection, the first two requirements are removed.)[1]

## See also

* Cuckoo hashing
* 2-choice hashing

## References

1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Dillinger, Peter C.; Manolios, Panagiotis (November 15–17, 2004). "Bloom Filters in Probabilistic Verification". 5h International Conference on Formal Methods in Computer Aided Design (FMCAD 2004). Austin, Texas. doi:10.1007/978-3-540-30494-4_26. https://www.khoury.northeastern.edu/~pete/pub/bloom-filters-verification.pdf.
2. ↑ Guibas; Szemeredi (1978). "The Analysis of Double Hashing". J. Comput. System Sci. 16: 226–274.
3. ↑ Lueker, George; Molodowitch, Mariko (1988). "More analysis of double hashing". Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 (New York, New York, USA: ACM Press): 354–359. doi:10.1145/62212.62246. https://doi.org/10.1145/62212.62246.
4. ↑ Bradford, Phillip G. (April 2007), "A Probabilistic Study on Combinatorial Expanders and Hashing", SIAM Journal on Computing 37 (1): 83–111, doi:10.1137/S009753970444630X, http://phillipbradford.com/papers/AProbStudyExpandersAndHashing.pdf .
5. ↑ Dillinger, Peter C. (December 2010). Adaptive Approximate State Storage (PDF) (PhD thesis). Northeastern University. pp. 93–112.
6. ↑ 6.0 6.1 "Less Hashing, Same Performance: Building a Better Bloom Filter". Random Structures and Algorithms 33 (2): 187–218. September 2008. doi:10.1002/rsa.20208. https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf.

## External links

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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Double hashing. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Double_hashing&oldid=4414760"