Package com.tomgibara.crinch.hashing

Class 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 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

      • 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