java.lang.Object
com.tomgibara.crinch.hashing.PerfectStringHash
All Implemented Interfaces:
Hash<String>
public class PerfectStringHashextends 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.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final Comparator<String>
    comparator
    Comparator used to order the supplied string array.
    private final int[]
    hashes
    The hashcodes of the supplied strings.
    private final int[]
    offsets
    Stores two ints for every string, an offset into the pivot array (-1 if not necessary) and the depth of the decision tree that is rooted there.
    private final int[]
    pivots
    Stores two ints for every decision, the index at which a character comparison needs to be made, followed by the character value to be compared against; or -1 to indicate a length comparison, followed by the length to be compared against.
    private final HashRange
    range
    Cache a range object which indicates the range of hash values generated.

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    Description
    private static void
    generatePivots(String[] values, int start, int length, int[] pivots, int pivotIndex)
    Builds a (typically v.
    HashRange
    getRange()
    Returns the hash range for this hash function.
    private int
    hash(String value)
    Generates a hashcode for the supplied string.
    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 Object

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

  • Field Details

    • comparator

      private static final Comparator<String> comparator
      Comparator used to order the supplied string array. Hashcodes take priority, we will do a binary search on those. Otherwise, lengths take priority over character ordering because the hash algorithm prefers to compare lengths, it's faster.

    • hashes

      private final int[] hashes
      The hashcodes of the supplied strings.

    • offsets

      private final int[] offsets
      Stores two ints for every string, an offset into the pivot array (-1 if not necessary) and the depth of the decision tree that is rooted there.

    • pivots

      private final int[] pivots
      Stores two ints for every decision, the index at which a character comparison needs to be made, followed by the character value to be compared against; or -1 to indicate a length comparison, followed by the length to be compared against.

    • range

      private final HashRange range
      Cache a range object which indicates the range of hash values generated.

  • 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

    • generatePivots

      private static void generatePivots(String[] values, int start, int length, int[] pivots, int pivotIndex)
      Builds a (typically v. small) decision tree for distinguishing strings that share the same hash value.
      Parameters:
      values - the string values to distinguish
      start - the index from which the values should be read
      length - the number of string values that need to be distinguished
      pivots - the array that will hold our decision nodes
      pivotIndex - the index at which the tree should be written

    • getRange

      public HashRange getRange()
      Description copied from interface: Hash
      Returns the hash range for this hash function.
      Specified by:
      getRange in interface Hash<String>
      Returns:
      the hash range

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

    • hash

      private int hash(String value)
      Generates a hashcode for the supplied string.
      Parameters:
      value - any string, not null
      Returns:
      a minimal hashcode for the supplied string, or -1