Package 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 Details

    • 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 Details

    • 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