it.unimi.dsi.sux4j.mph
Class Hashes

java.lang.Object
  it.unimi.dsi.sux4j.mph.Hashes

public class Hashes
extends Object

Basic hash functions.

Method Summary

static long	jenkins(BitVector bv) Jenkins 64-bit hashing.
static long	jenkins(BitVector bv, long seed) Jenkins 64-bit hashing.
static void	jenkins(BitVector bv, long seed, long[] h) Jenkins 64-bit hashing (all three values produced).
static long	jenkins(BitVector bv, long prefixLength, long[] aa, long[] bb, long[] cc) Constant-time Jenkins 64-bit hashing for any prefix.
static void	jenkins(BitVector bv, long prefixLength, long[] aa, long[] bb, long[] cc, long[] h) Constant-time Jenkins 64-bit hashing for any prefix (all three values produced).
static void	jenkins(long[] triple, long seed, long[] h) Jenkins 64-bit hashing (all three values produced) for a triple of longs.
static long[][]	preprocessJenkins(BitVector bv, long seed) Preprocesses a bit vector so that Jenkins 64-bit hashing can be computed in constant time on all prefixes.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

jenkins

public static void jenkins(BitVector bv,
                           long seed,
                           long[] h)

Jenkins 64-bit hashing (all three values produced).

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.

Parameters:

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.

jenkins

public static long jenkins(BitVector bv,
                           long seed)

Jenkins 64-bit hashing.

Parameters:

bv - a bit vector.

seed - a seed for the hash.

Returns:

the first of the three hash values returned by jenkins(BitVector, long, long[]).

jenkins

public static long jenkins(BitVector bv)

Jenkins 64-bit hashing.

Parameters:

bv - a bit vector.

Returns:

the first of the three hash values returned by jenkins(BitVector, long, long[]) with seed 0.

preprocessJenkins

public static long[][] preprocessJenkins(BitVector bv,
                                         long seed)

Preprocesses a bit vector so that Jenkins 64-bit hashing can be computed in constant time on all prefixes.

Parameters:

bv - a bit vector.

seed - a seed for the hash.

Returns:

an array of three element; each element is an array containing the state of the variables a, b and c during the hash computation; these vector must be passed to jenkins(BitVector, long, long[], long[], long[]) (and analogous functions) in this order.

See Also:

jenkins(BitVector)

jenkins

public static void jenkins(BitVector bv,
                           long prefixLength,
                           long[] aa,
                           long[] bb,
                           long[] cc,
                           long[] h)

Constant-time Jenkins 64-bit hashing for any prefix (all three values produced).

Parameters:

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.

jenkins

public static long jenkins(BitVector bv,
                           long prefixLength,
                           long[] aa,
                           long[] bb,
                           long[] cc)

Constant-time Jenkins 64-bit hashing for any prefix.

Parameters:

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).

Returns:

the first of the three hash values returned by jenkins(BitVector, long, long[], long[], long[], long[]).

jenkins

public static void jenkins(long[] triple,
                           long seed,
                           long[] h)

Jenkins 64-bit hashing (all three values produced) for a triple of longs.

Parameters:

triple - three longs.

seed - a seed for the hash.

h - a triple of long values in which the three generated hashes will be saved.