Class TwoStepsLcpMonotoneMinimalPerfectHashFunction<T>

java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<K>
it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
it.unimi.dsi.sux4j.mph.TwoStepsLcpMonotoneMinimalPerfectHashFunction<T>
All Implemented Interfaces:
Function<T,Long>, Object2LongFunction<T>, Size64, Serializable, Function<T,Long>, ToLongFunction<T>

public class TwoStepsLcpMonotoneMinimalPerfectHashFunction<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, and store their lengths using a TwoStepsGOV3Function.

This implementation should use a few less bits per elements than LcpMonotoneMinimalPerfectHashFunction, but it is a bit slower as one or two additional functions must be queried.

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

See Also:
  • Field Details

    • serialVersionUID

      public static final long serialVersionUID
      See Also:
    • n

      protected final long n
      The number of elements.
    • 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.
    • offsets

      protected final GOV3Function<BitVector> offsets
      A function mapping each element to the offset inside its bucket.
    • lcpLengths

      protected final TwoStepsGOV3Function<BitVector> lcpLengths
      A function mapping each element to the length of the longest common prefix of its bucket.
    • 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

    • TwoStepsLcpMonotoneMinimalPerfectHashFunction

      protected TwoStepsLcpMonotoneMinimalPerfectHashFunction(Iterable<? extends T> keys, long numKeys, TransformationStrategy<? super T> transform, int signatureWidth, File tempDir) throws IOException
      Creates a new two-steps 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