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  Description 

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

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 
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 void 
spooky4(long[] triple,
long seed,
long[] tuple) 
SpookyHash (up to four values produced) for a triple of longs.

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.

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.