cc.redberry.core.utils

Class HashFunctions

java.lang.Object

cc.redberry.core.utils.HashFunctions

public final class HashFunctions
extends java.lang.Object

Hashing algorithms. The algorithms was taken from different open sources.

Links:

http://www.concentric.net/~ttwang/tech/inthash.htm
http://www.burtleburtle.net/bob/hash/doobs.html
http://bretm.home.comcast.net/~bretm/hash
http://www.isthe.com/chongo/tech/comp/fnv/
http://en.wikipedia.org/wiki/Jenkins_hash_function's
http://sites.google.com/site/murmurhash/
http://dmy999.com/article/50/murmurhash-2-java-port
http://en.wikipedia.org/wiki/MurmurHash

Since:

1.0

Field Summary

Fields

Modifier and Type	Field and Description
static long	FNV_BASIS Fowler/Noll/Vo hash algorithms FNV_BASIS constant
static long	FNV_PRIME_32 Fowler/Noll/Vo hash algorithms FNV_PRIME constant for 32 bit hash
static long	FNV_PRIME_64 Fowler/Noll/Vo hash algorithms FNV_PRIME constant for 64 bit hash

Method Summary

Modifier and Type	Method and Description
static int	FVN32hash(byte[] bytes) Fowler-Noll-Vo 32 bit hash (FNV-1a) for bytes array.
static int	FVN32hash(int c) Fowler-Noll-Vo 32 bit hash (FNV-1a) for integer key.
static long	FVN64hash(byte[] bytes) Fowler-Noll-Vo 64 bit hash (FNV-1a) for bytes array.
static long	FVN64hash(long c) Fowler-Noll-Vo 64 bit hash (FNV-1a) for long key.
static int	FVN64to32hash(long c) Fowler-Noll-Vo 32 bit hash (FNV-1a) for long key.
static int	JenkinWang32shift(int key) Based on an original suggestion on Robert Jenkin's part in 1997 and Thomas Wang 2007 updates.
static long	JenkinWang64shift(long key) Based on an original suggestion on Robert Jenkin's part in 1997 and Thomas Wang 2007 updates.
static int	mix(int a, int b, int c) Robert Jenkins' 96 bit Mix Function.
static int	MurmurHash2(byte[] data) MurmurHash hash function for bytes array with default seed value equals 0x2f1a32b3.
static int	MurmurHash2(byte[] data, int seed) MurmurHash hash function for bytes array.
static int	MurmurHash2(int c) MurmurHash hash function integer with default seed value equals to 0x2f1a32b3.
static int	MurmurHash2(int c, int seed) MurmurHash hash function integer.
static int	Wang32shiftmult(int key) This method uses a combination of bit shifts and integer multiplication to hash the input key.
static int	Wang64to32shift(long key) Hashing long to int.

Methods inherited from class java.lang.Object

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

Field Detail

FNV_BASIS

public static final long FNV_BASIS

Fowler/Noll/Vo hash algorithms FNV_BASIS constant

Links

http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param

See Also:

Constant Field Values

FNV_PRIME_32

public static final long FNV_PRIME_32

Fowler/Noll/Vo hash algorithms FNV_PRIME constant for 32 bit hash

Links

http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param

See Also:

Constant Field Values

FNV_PRIME_64

public static final long FNV_PRIME_64

Fowler/Noll/Vo hash algorithms FNV_PRIME constant for 64 bit hash

Links

http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param

See Also:

Constant Field Values

Method Detail

mix

public static int mix(int a,
                      int b,
                      int c)

Robert Jenkins' 96 bit Mix Function.

Variable 'c' contains the input key. When the mixing is complete, variable 'c' also contains the hash result. Variable 'a', and 'b' contain initialized random bits. Notice the total number of internal state is 96 bits, much larger than the final output of 32 bits. Also notice the sequence of subtractions rolls through variable 'a' to variable 'c' three times. Each row will act on one variable, mixing in information from the other two variables, followed by a shift operation.

Subtraction is similar to multiplication in that changes in upper bits of the key do not influence lower bits of the addition. The 9 bit shift operations in Robert Jenkins' mixing algorithm shifts the key to the right 61 bits in total, and shifts the key to the left 34 bits in total. As the calculation is chained, each exclusive-or doubles the number of states. There are at least 2^9 different combined versions of the original key, shifted by various amounts. That is why a single bit change in the key can influence widely apart bits in the hash result.

The uniform distribution of the hash function can be determined from the nature of the subtraction operation. Look at a single bit subtraction operation between a key, and a random bit. If the random bit is 0, then the key remains unchanged. If the random bit is 1, then the key will be flipped. A carry will occur in the case where both the key bit and the random bit are 1. Subtracting the random bits will cause about half of the key bits to be flipped. So even if the key is not uniform, subtracting the random bits will result in uniform distribution.

Links:

http://www.concentric.net/~ttwang/tech/inthash.htm
http://www.burtleburtle.net/bob/hash/doobs.html
http://www.isthe.com/chongo/tech/comp/fnv/
http://en.wikipedia.org/wiki/Jenkins_hash_function's
http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Parameters:

a - initialized random bits

b - initialized random bits

c - key to be hashed

Returns:

randomized c bits (hashed c)

JenkinWang32shift

public static int JenkinWang32shift(int key)

Based on an original suggestion on Robert Jenkin's part in 1997 and Thomas Wang 2007 updates.

Links

http://www.concentric.net/~ttwang/tech/inthash.htm
http://en.wikipedia.org/wiki/Jenkins_hash_function's

Parameters:

key - key to be hashed

Returns:

hashed value

Wang32shiftmult

public static int Wang32shiftmult(int key)

This method uses a combination of bit shifts and integer multiplication to hash the input key.

Links

http://www.concentric.net/~ttwang/tech/inthash.htm

Parameters:

key - key to be hashed

Returns:

hashed key

JenkinWang64shift

public static long JenkinWang64shift(long key)

Based on an original suggestion on Robert Jenkin's part in 1997 and Thomas Wang 2007 updates.

Links

http://www.concentric.net/~ttwang/tech/inthash.htm
http://en.wikipedia.org/wiki/Jenkins_hash_function's

Parameters:

key - key to be hashed

Returns:

hashed value

Wang64to32shift

public static int Wang64to32shift(long key)

Hashing long to int.

Links

http://www.concentric.net/~ttwang/tech/inthash.htm

Parameters:

key - key to be hashed

Returns:

hashed value

FVN32hash

public static int FVN32hash(byte[] bytes)

Fowler-Noll-Vo 32 bit hash (FNV-1a) for bytes array.

Algorithm

 hash = offset_basis
 for each octet_of_data to be hashed
    hash = hash xor octet_of_data
    hash = hash * FNV_prime
 return hash

Links

http://www.isthe.com/chongo/tech/comp/fnv/
http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Parameters:

bytes - bytes array to hash

Returns:

hash of the initial bytes array

FVN32hash

public static int FVN32hash(int c)

Fowler-Noll-Vo 32 bit hash (FNV-1a) for integer key. This is big-endian version (native endianess of JVM).

Algorithm

 hash = offset_basis
 for each octet_of_data to be hashed
    hash = hash xor octet_of_data
    hash = hash * FNV_prime
 return hash

Links

http://www.isthe.com/chongo/tech/comp/fnv/
http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Parameters:

c - integer key to be hashed

Returns:

hash 32 bit hash

FVN64hash

public static long FVN64hash(byte[] bytes)

Fowler-Noll-Vo 64 bit hash (FNV-1a) for bytes array.

Algorithm

 hash = offset_basis
 for each octet_of_data to be hashed
    hash = hash xor octet_of_data
    hash = hash * FNV_prime
 return hash

Links

http://www.isthe.com/chongo/tech/comp/fnv/
http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Parameters:

bytes - bytes array to hash

Returns:

hash 64 bit hash

FVN64hash

public static long FVN64hash(long c)

Fowler-Noll-Vo 64 bit hash (FNV-1a) for long key. This is big-endian version (native endianess of JVM).

Algorithm

 hash = offset_basis
 for each octet_of_data to be hashed
    hash = hash xor octet_of_data
    hash = hash * FNV_prime
 return hash

Links

http://www.isthe.com/chongo/tech/comp/fnv/
http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Parameters:

c - long key to be hashed

Returns:

hash 64 bit hash

FVN64to32hash

public static int FVN64to32hash(long c)

Fowler-Noll-Vo 32 bit hash (FNV-1a) for long key. This is big-endian version (native endianess of JVM).

Algorithm

 hash = offset_basis
 for each octet_of_data to be hashed
    hash = hash xor octet_of_data
    hash = hash * FNV_prime
 return hash

Links

http://www.isthe.com/chongo/tech/comp/fnv/
http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Parameters:

c - long key to be hashed

Returns:

hash 32 bit hash

MurmurHash2

public static int MurmurHash2(byte[] data,
                              int seed)

MurmurHash hash function for bytes array.

Links

http://sites.google.com/site/murmurhash/
http://dmy999.com/article/50/murmurhash-2-java-port
http://en.wikipedia.org/wiki/MurmurHash

Parameters:

data - bytes to be hashed

seed - seed parameter

Returns:

32 bit hash

MurmurHash2

public static int MurmurHash2(int c,
                              int seed)

MurmurHash hash function integer.

Links

http://sites.google.com/site/murmurhash/
http://dmy999.com/article/50/murmurhash-2-java-port
http://en.wikipedia.org/wiki/MurmurHash

Parameters:

c - int to be hashed

seed - seed parameter

Returns:

32 bit hash

MurmurHash2

public static int MurmurHash2(byte[] data)

MurmurHash hash function for bytes array with default seed value equals 0x2f1a32b3.

Links

http://sites.google.com/site/murmurhash/
http://dmy999.com/article/50/murmurhash-2-java-port
http://en.wikipedia.org/wiki/MurmurHash

Parameters:

data - bytes to be hashed

Returns:

32 bit hash

MurmurHash2

public static int MurmurHash2(int c)

MurmurHash hash function integer with default seed value equals to 0x2f1a32b3.

Links

http://sites.google.com/site/murmurhash/
http://dmy999.com/article/50/murmurhash-2-java-port
http://en.wikipedia.org/wiki/MurmurHash

Parameters:

c - int to be hashed\

Returns:

32 bit hash