Class PerfectHash

java.lang.Object
smile.hash.PerfectHash
All Implemented Interfaces:
Serializable
public class PerfectHash extends Object implements Serializable
A perfect hash of an array of strings to their index in the array.

A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. In mathematical terms, it is an injective function.

Perfect hash functions may be used to implement a lookup table with constant worst-case access time.

A perfect hash function for a specific set S can be found by a randomized algorithm in a number of operations that is proportional to the size of S. The original construction of Fredman, Komlós and Szemerédi (1984) chooses a large prime p (larger than the size of the universe from which S is drawn), and a parameter k, and maps each element x of S to the index g(x) = (kx mod p) mod n.

See Also:

  • Constructor Details

    • PerfectHash

      public PerfectHash(String... keywords)
      Constructor.
      Parameters:
      keywords - the fixed set of keywords.

    • PerfectHash

      public PerfectHash(int[] select, String... keywords)
      Constructor.
      Parameters:
      select - The character positions in keywords used to calculate the hash.
      keywords - the fixed set of keywords.

  • Method Details

    • get

      public int get(String key)
      Returns the index of a keyword. If the string is not in the set, returns -1.
      Parameters:
      key - the keyword.
      Returns:
      the index of keyword or -1.