public class Hashes
extends java.lang.Object
This class provides a number of hash functions for bit vectors. For this reason, they are sometimes tweaked with respect to the official C code, which can assume at least byte granularity. In particular, we provide:
In particular, SpookyHash is available in the 4wordstate version and in the 12wordstate version. The 12wordstate version delegates to the 4wordstate version for short keys (i.e., less than 12 words).
All functions (with the exception of the 12wordstate version of SpookyHash) provide preprocessing: a linear pass on the bit vector generates a vector storing the internal state of the function after each mixing round. Using the preprocessed state, one can hash any prefix of the bit vector in constant time.
It is your responsibility to use preprocessing correctly: using the state vector of the wrong bit vector will generate unpredictable results.
Modifier and Type  Method and Description 

static long 
jenkins(BitVector bv)
Jenkins 64bit hashing.

static long 
jenkins(BitVector bv,
long seed)
Jenkins 64bit hashing.

static void 
jenkins(BitVector bv,
long seed,
long[] h)
Jenkins 64bit hashing (all three values produced).

static long 
jenkins(BitVector bv,
long prefixLength,
long[] aa,
long[] bb,
long[] cc)
Constanttime Jenkins 64bit hashing for any prefix.

static void 
jenkins(BitVector bv,
long prefixLength,
long[] aa,
long[] bb,
long[] cc,
long[] h)
Constanttime Jenkins 64bit hashing for any prefix (all three values produced).

static void 
jenkins(long[] triple,
long seed,
long[] h)
Jenkins 64bit hashing (all three values produced) for a triple of longs.

static void 
main(java.lang.String[] arg)
A simple test to check the relative speed of various hashes on your architecture.

static long 
murmur(BitVector bv,
long seed)
MurmurHash 64bit

static long 
murmur(BitVector bv,
long prefixLength,
long[] state)
Constanttime MurmurHash 64bit hashing for any prefix.

static long 
murmur(BitVector bv,
long prefixLength,
long[] state,
long lcp)
Constanttime MurmurHash 64bit hashing reusing precomputed state partially.

static long 
murmur3(BitVector bv,
long seed)
MurmurHash3 64bit

static void 
murmur3(BitVector bv,
long seed,
long[] h)
MurmurHash3 128bit

static long 
murmur3(BitVector bv,
long prefixLength,
long[] hh1,
long[] hh2,
long[] cc1,
long[] cc2)
Constanttime MurmurHash3 64bit hashing for any prefix.

static long 
murmur3(BitVector bv,
long prefixLength,
long[] hh1,
long[] hh2,
long[] cc1,
long[] cc2,
long lcp)
Constanttime MurmurHash3 64bit hashing reusing precomputed state partially.

static void 
murmur3(BitVector bv,
long prefixLength,
long[] hh1,
long[] hh2,
long[] cc1,
long[] cc2,
long[] h)
Constanttime MurmurHash3 128bit hashing for any prefix.

static void 
murmur3(BitVector bv,
long prefixLength,
long[] hh1,
long[] hh2,
long[] cc1,
long[] cc2,
long lcp,
long[] h)
Constanttime MurmurHash3 128bit hashing reusing precomputed state partially.

static long[][] 
preprocessJenkins(BitVector bv,
long seed)
Preprocesses a bit vector so that Jenkins 64bit hashing can be computed in constant time on all prefixes.

static long[] 
preprocessMurmur(BitVector bv,
long seed)
Preprocesses a bit vector so that MurmurHash 64bit can be computed in constant time on all prefixes.

static long[][] 
preprocessMurmur3(BitVector bv,
long seed)
Preprocesses a bit vector so that MurmurHash3 can be computed in constant time on all prefixes.

static long[] 
preprocessSpooky4(BitVector bv,
long seed)
Preprocesses a bit vector so that SpookyHash 4wordstate can be computed in constant time on all prefixes.

static void 
spooky12(BitVector bv,
long seed,
long[] tuple)
SpookyHash 12wordstate (up to four values produced).

static long 
spooky4(BitVector bv,
long seed)
SpookyHash 4wordstate (up to four values produced).

static void 
spooky4(BitVector bv,
long seed,
long[] tuple)
SpookyHash 4wordstate (up to four values produced).

static long 
spooky4(BitVector bv,
long prefixLength,
long seed,
long[] state)
Constanttime SpookyHash 4wordstate hashing reusing precomputed state partially.

static void 
spooky4(BitVector bv,
long prefixLength,
long seed,
long[] state,
long[] tuple)
Constanttime SpookyHash 4wordstate hashing reusing precomputed state partially.

static void 
spooky4(long[] triple,
long seed,
long[] tuple)
SpookyHash (up to four values produced) for a triple of longs.

public static void jenkins(BitVector bv, long seed, long[] h)
This code is based on the lookup8.c
, and in particular
on the version consuming 64 bits at a time, but it has been slightly modified to work correctly with any bit vector length (not just multiples of 64).
Moreover, we return all three values generated by the algorithm.
bv
 a bit vector.seed
 a seed for the hash.h
 a triple of long values in which the three generated hashes will be saved.public static long jenkins(BitVector bv, long seed)
bv
 a bit vector.seed
 a seed for the hash.jenkins(BitVector, long, long[])
.public static long jenkins(BitVector bv)
bv
 a bit vector.jenkins(BitVector, long, long[])
with seed 0.public static long[][] preprocessJenkins(BitVector bv, long seed)
bv
 a bit vector.seed
 a seed for the hash.a
, b
and c
during the hash computation; these vector must be passed to jenkins(BitVector, long, long[], long[], long[])
(and analogous methods) in this order.jenkins(BitVector, long)
public static void jenkins(BitVector bv, long prefixLength, long[] aa, long[] bb, long[] cc, long[] h)
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.aa
 the first state array returned by preprocessJenkins(BitVector, long)
.bb
 the second state array returned by preprocessJenkins(BitVector, long)
.cc
 the third state array returned by preprocessJenkins(BitVector, long)
.h
 a triple of long values in which the three generated hashes will be saved.public static long jenkins(BitVector bv, long prefixLength, long[] aa, long[] bb, long[] cc)
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.aa
 the first state array returned by preprocessJenkins(BitVector, long)
.bb
 the second state array returned by preprocessJenkins(BitVector, long)
.cc
 the third state array returned by preprocessJenkins(BitVector, long)
.jenkins(BitVector, long, long[], long[], long[], long[])
.public static void jenkins(long[] triple, long seed, long[] h)
triple
 three longs.seed
 a seed for the hash.h
 a triple of long values in which the three generated hashes will be saved.public static long murmur(BitVector bv, long seed)
This code is based on a mix of the sources that can be found at MurmurHash's web site, and in particular on the version consuming 64 bits at a time, which has been merged with the 2A version to obtain an incremental implementation.
bv
 a bit vector.seed
 a seed for the hash.public static long murmur(BitVector bv, long prefixLength, long[] state)
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.state
 the state array returned by preprocessMurmur(BitVector, long)
.bv
or prefixLength
bits.public static long murmur(BitVector bv, long prefixLength, long[] state, long lcp)
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.state
 the state array returned by preprocessMurmur(BitVector, long)
.lcp
 the length of the longest common prefix between bv
and the vector over which state
was computed.bv
or prefixLength
bits.public static long[] preprocessMurmur(BitVector bv, long seed)
bv
 a bit vector.seed
 a seed for the hash.h
during the hash computation; these vector must be passed to murmur(BitVector, long, long[])
(and analogous methods) in this order.murmur(BitVector, long)
public static void murmur3(BitVector bv, long seed, long[] h)
This code is based on a mix of the sources that can be found at MurmurHash's web site.
Warning: this code is still experimental.
bv
 a bit vector.seed
 a seed for the hash.h
 a pair of long values in which the two generated hashes will be saved.public static long murmur3(BitVector bv, long seed)
This code is based on a mix of the sources that can be found at MurmurHash's web site.
Warning: this code is still experimental.
bv
 a bit vector.seed
 a seed for the hash.public static void murmur3(BitVector bv, long prefixLength, long[] hh1, long[] hh2, long[] cc1, long[] cc2, long[] h)
Warning: this code is still experimental.
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.hh1
 the first component of the state array returned by preprocessMurmur3(BitVector, long)
.hh2
 the second component of the state array returned by preprocessMurmur3(BitVector, long)
.cc1
 the third component of the state array returned by preprocessMurmur3(BitVector, long)
.cc2
 the fourth component of the state array returned by preprocessMurmur3(BitVector, long)
.h
 a pair of long values in which the two generated hashes will be saved.public static long murmur3(BitVector bv, long prefixLength, long[] hh1, long[] hh2, long[] cc1, long[] cc2)
Warning: this code is still experimental.
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.hh1
 the first component of the state array returned by preprocessMurmur3(BitVector, long)
.hh2
 the second component of the state array returned by preprocessMurmur3(BitVector, long)
.cc1
 the third component of the state array returned by preprocessMurmur3(BitVector, long)
.cc2
 the fourth component of the state array returned by preprocessMurmur3(BitVector, long)
.public static void murmur3(BitVector bv, long prefixLength, long[] hh1, long[] hh2, long[] cc1, long[] cc2, long lcp, long[] h)
Warning: this code is still experimental.
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.hh1
 the first component of the state array returned by preprocessMurmur3(BitVector, long)
.hh2
 the second component of the state array returned by preprocessMurmur3(BitVector, long)
.cc1
 the third component of the state array returned by preprocessMurmur3(BitVector, long)
.cc2
 the fourth component of the state array returned by preprocessMurmur3(BitVector, long)
.lcp
 the length of the longest common prefix between bv
and the vector over which state
was computed.h
 a pair of long values in which the two generated hashes will be saved.public static long murmur3(BitVector bv, long prefixLength, long[] hh1, long[] hh2, long[] cc1, long[] cc2, long lcp)
Warning: this code is still experimental.
bv
 a bit vector.prefixLength
 the length of the prefix of bv
over which the hash must be computed.hh1
 the first component of the state array returned by preprocessMurmur3(BitVector, long)
.hh2
 the second component of the state array returned by preprocessMurmur3(BitVector, long)
.cc1
 the third component of the state array returned by preprocessMurmur3(BitVector, long)
.cc2
 the fourth component of the state array returned by preprocessMurmur3(BitVector, long)
.lcp
 the length of the longest common prefix between bv
and the vector over which state
was computed.public static long[][] preprocessMurmur3(BitVector bv, long seed)
Warning: this code is still experimental.
bv
 a bit vector.seed
 a seed for the hash.h1
, h2
, c1
and c2
during the hash computation; these vector must be passed to murmur3(BitVector, long, long[], long[], long[], long[])
(and analogous methods) in this order.murmur3(BitVector, long)
public static void spooky4(BitVector bv, long seed, long[] tuple)
bv
 a bit vector.seed
 a seed for the hash.tuple
 a tuple of longs in which up to four generated hashes will be saved.public static long spooky4(BitVector bv, long seed)
bv
 a bit vector.seed
 a seed for the hash.public static void spooky12(BitVector bv, long seed, long[] tuple)
This method will automatically switch to spooky4(BitVector, long, long[])
when
the provided bit vector is shorter than 768 bits.
bv
 a bit vector.seed
 a seed for the hash.tuple
 a tuple of longs in which up to four generated hashes will be saved.public static long[] preprocessSpooky4(BitVector bv, long seed)
bv
 a bit vector.seed
 a seed for the hash.spooky4(BitVector, long, long, long[], long[])
(and analogous methods).spooky4(BitVector, long)
public static void spooky4(BitVector bv, long prefixLength, long seed, long[] state, long[] tuple)
bv
 a bit vector.seed
 a seed for the hash.state
 the state vector returned by preprocessSpooky4(BitVector, long)
; note that seed
must be the same.tuple
 a tuple of longs in which up to four generated hashes will be saved.public static long spooky4(BitVector bv, long prefixLength, long seed, long[] state)
bv
 a bit vector.seed
 a seed for the hash.state
 the state vector returned by preprocessSpooky4(BitVector, long)
; note that seed
must be the same.public static void spooky4(long[] triple, long seed, long[] tuple)
triple
 three longs.seed
 a seed for the hash.tuple
 a tuple of longs in which up to four generated hashes will be saved.public static void main(java.lang.String[] arg)
arg
 the length of the bit vector to hash, and then the number of evaluations.