com.tomgibara.crinch.hashing

Class PerfectStringHash

java.lang.Object

com.tomgibara.crinch.hashing.PerfectStringHash

All Implemented Interfaces:

Hash<String>

public class PerfectStringHash
extends Object
implements Hash<String>

A "minimal perfect hash" for Strings. After construction with an array of n unique non-null strings, an instance of this class will return a unique hash value h (0 <= h < n) for any string s in the array. A negative has value will typically be returned for a string that is not in the array.

However, the supplied array is not retained. This means that the implementation cannot necessarily confirm that a string is not in the supplied array. Where this implementation cannot distinguish that a string is not in the array, a 'valid' hash value may be returned. Under no circumstances will a hash value be returned that is greater than or equal to n.

IMPORTANT NOTE: The array of strings supplied to the constructor will be mutated: it is re-ordered so that hash(a[i]) == i. Application code must generally use this information to map hash values back onto the appropriate string value.

NOTE: Good performance of this algorithm is predicated on string hash values being cached by the String class. Experience indicates that is is a good assumption.

Author:

Tom Gibara

Constructor Summary

Constructors

Constructor and Description
PerfectStringHash(String[] values) Constructs a minimal perfect string hashing over the supplied strings.

Method Summary

Modifier and Type	Method and Description
HashRange	getRange()
BigInteger	hashAsBigInt(String value) The hash value as a BigInteger.
int	hashAsInt(String value) The hash value as an int.
long	hashAsLong(String value) The hash value as a long.

Methods inherited from class java.lang.Object

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

Constructor Detail

PerfectStringHash

public PerfectStringHash(String[] values)

Constructs a minimal perfect string hashing over the supplied strings.

Parameters:

values - an array of unique non-null strings that will be reordered such that hash(values[i]) == i.

Method Detail

getRange

public HashRange getRange()

Specified by:

getRange in interface Hash<String>

hashAsBigInt

public BigInteger hashAsBigInt(String value)

Description copied from interface: Hash

The hash value as a BigInteger. This method may be useful in circumstances where the generated hash is too large to be accomodated in a single primitive value, eg. if cryptographic hashes are being used.

Specified by:

hashAsBigInt in interface Hash<String>

Parameters:

value - the object to be hashed

Returns:

the object's hash code, never null

hashAsInt

public int hashAsInt(String value)

Description copied from interface: Hash

The hash value as an int. This method should provide better performance for integer-ranged hashes. This value is not guaranteed to lie within the indicated HashRange.

Specified by:

hashAsInt in interface Hash<String>

Parameters:

value - the object to be hashed

Returns:

the object's hash code

hashAsLong

public long hashAsLong(String value)

Description copied from interface: Hash

The hash value as a long. This method should provide better performance for long-ranged hashes. This value is not guaranteed to lie within the indicated HashRange.

Specified by:

hashAsLong in interface Hash<String>

Parameters:

value - the object to be hashed

Returns:

the object's hash code