craterdog.collections.primitives

Class UniversalHashFunction

java.lang.Object

craterdog.collections.primitives.UniversalHashFunction

public final class UniversalHashFunction
extends java.lang.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 and Description
UniversalHashFunction(int hashWidth) This constructor creates a new hash function with the specified hash width and the default word width (32 bits).
UniversalHashFunction(int wordWidth, int hashWidth) This constructor creates a new hash function with the specified hash width and the default word width (32 bits).

Method Summary

Modifier and Type	Method and Description
int	hashValue(java.lang.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 Detail

UniversalHashFunction

public UniversalHashFunction(int hashWidth)

This constructor creates a new hash function with the specified hash width and the default word width (32 bits).

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 wordWidth,
                             int hashWidth)

This constructor creates a new hash function with the specified hash width and the default word width (32 bits).

Parameters:

wordWidth - The number of bits in the word size for the environment (32 for Java ints).

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

Method Detail

hashValue

public int hashValue(java.lang.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.