Class LcpMonotoneMinimalPerfectHashFunction<T>

All Implemented Interfaces:
Function<T,​Long>, Object2LongFunction<T>, Size64, Serializable, Function<T,​Long>, ToLongFunction<T>

public class LcpMonotoneMinimalPerfectHashFunction<T>
extends AbstractHashFunction<T>
implements Size64, Serializable
A monotone minimal perfect hash implementation based on fixed-size bucketing that uses longest common prefixes as distributors.

See the package overview for a comparison with other implementations. Similarly to a GOV3Function, an instance of this class may be signed.

See Also:
Serialized Form
  • Field Details

    • serialVersionUID

      public static final long serialVersionUID
      See Also:
      Constant Field Values
    • n

      protected final long n
      The number of keys.
    • bucketSize

      protected final int bucketSize
      The size of a bucket.
    • log2BucketSize

      protected final int log2BucketSize
    • bucketSizeMask

      protected final int bucketSizeMask
      The mask for log2BucketSize bits.
    • offsetLcpLength

      protected final GOV3Function<BitVector> offsetLcpLength
      A function mapping each key to the offset inside its bucket (lowest log2BucketSize bits) and to the length of the longest common prefix of its bucket (remaining bits).
    • lcp2Bucket

      protected final GOV3Function<BitVector> lcp2Bucket
      A function mapping each longest common prefix to its bucket.
    • transform

      protected final TransformationStrategy<? super T> transform
      The transformation strategy.
    • seed

      protected final long seed
      The seed returned by the BucketedHashStore.
    • signatureMask

      protected final long signatureMask
      The mask to compare signatures, or zero for no signatures.
    • signatures

      protected final LongBigList signatures
      The signatures.
  • Constructor Details

    • LcpMonotoneMinimalPerfectHashFunction

      protected LcpMonotoneMinimalPerfectHashFunction​(Iterable<? extends T> keys, long numKeys, TransformationStrategy<? super T> transform, int signatureWidth, File tempDir) throws IOException
      Creates a new LCP monotone minimal perfect hash function for the given keys.
      Parameters:
      keys - the keys to hash.
      numKeys - the number of keys, or -1 if the number of keys is not known (will be computed).
      transform - a transformation strategy for the keys.
      signatureWidth - a signature width, or 0 for no signature.
      tempDir - a temporary directory for the store files, or null for the standard temporary directory.
      Throws:
      IOException
  • Method Details