Approximating Streaming Data with Sketching - Real-Time Analytics - page 412

Independent Hash Functions
Many algorithms call for several independent, or pairwise independent,
hash functions. Creating hash functions with these properties is a
well-studied part of computer science, and it turns out to be a difficult
thing to do. Instead, most actual implementations rely on the much more
easily generated universal hash functions . These are hash functions that are
simply selected from the same family at random.
This happens in one of two ways. The first, and most obvious method, is
when the hash function takes an initial seed value, much like a random
number generator (the hash functions used in this chapter are similar in
implementation to many random number generators). To generate k hash
functions, k seeds are selected uniformly from the possible space of initial
values (usually an integer the same size as produced by the hash function).
The other way these hash functions are generated requires only a single
seed value to initialize the hash function. This is used to generate the first
hash value, which is then used as the initial value to generate the next hash
function, until k hash values are produced. For example, the previously
mentioned FNV implementation can be modified to produce any number of
output hash values for the same input as follows:
public class FNV {
public static final long INIT = 0xcbf29ce484222325L;
public static final long PRIME = 0x100000001b3L;
long hash;
byte[] input;
public void set(byte[] input) {
hash = INIT ;
this.input = input;
}
public long next() {
for(int i=0;i<input.length;i++) {
hash ^= input[i];
hash *= PRIME ;
}
return hash;
}
}