Package craterdog.utils

Class UniversalHashFunction

java.lang.Object

craterdog.utils.UniversalHashFunction

public final class UniversalHashFunction
extends Object

This class implements the universal hash function algorithm described by Dietzfelbinger, et al, (1997). "A Reliable Randomized Algorithm for the Closest-Pair Problem". The algorithm provides a very efficient (mod free) way to create and use a universal hash function that creates an evenly distributed hash value for hash tables that have a number of buckets that are a power of two. This function works even for data types that have poor builtin hash functions like are often seen for strings.

Author:

Derk Norton

Constructor Summary

Constructors

Constructor	Description
UniversalHashFunction()	This constructor creates a new hash function with a hash width equal to the word width.
UniversalHashFunction(int hashWidth)	This constructor creates a new hash function with the specified hash width.
UniversalHashFunction(int hashWidth, int a, int b)	This constructor creates a new hash function with the specified hash width, and random numbers a and b.

Method Summary

Modifier and Type	Method	Description
int	hashValue(Object object)	This method generates a hash value for the specified object using the universal hash function parameters specified in the constructor.

Methods inherited from class java.lang.Object

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

Constructor Details

UniversalHashFunction

public UniversalHashFunction()

This constructor creates a new hash function with a hash width equal to the word width. The universal hash function will be chosen at random so this will not generate consistent hash functions across different JVM invocations.

UniversalHashFunction

public UniversalHashFunction(int hashWidth)

This constructor creates a new hash function with the specified hash width. The universal hash function will be chosen at random so this will not generate consistent hash functions across different JVM invocations.

Parameters:

hashWidth - The number of bits required of the hash for the index size. In general, this will be the log base 2 of the number of buckets in the hash table (must be a power of 2).

UniversalHashFunction

public UniversalHashFunction(int hashWidth,
 int a,
 int b)

This constructor creates a new hash function with the specified hash width, and random numbers a and b. It should be used when the hash values must be consistent across different JVM invocations.

Parameters:

hashWidth - The number of bits required of the hash for the index size. In general, this will be the log base 2 of the number of buckets in the hash table (must be a power of 2).

a - A positive odd random integer.

b - A random integer in the range [0..2^(wordWidth - hashWidth)).

Method Details

hashValue

public int hashValue(Object object)

This method generates a hash value for the specified object using the universal hash function parameters specified in the constructor. The result will be a hash value containing the hash width number of bits.

Parameters:

object - The object to be hashed.

Returns:

A universal hash of the object.