Class LcpMonotoneMinimalPerfectHashFunction<T>

  • All Implemented Interfaces:
    it.unimi.dsi.fastutil.Function<T,​java.lang.Long>, it.unimi.dsi.fastutil.objects.Object2LongFunction<T>, it.unimi.dsi.fastutil.Size64, java.io.Serializable, java.util.function.Function<T,​java.lang.Long>, java.util.function.ToLongFunction<T>

    public class LcpMonotoneMinimalPerfectHashFunction<T>
    extends AbstractHashFunction<T>
    implements it.unimi.dsi.fastutil.Size64, java.io.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 Summary

      Fields 
      Modifier and Type Field Description
      protected int bucketSize
      The size of a bucket.
      protected int bucketSizeMask
      The mask for log2BucketSize bits.
      protected GOV3Function<it.unimi.dsi.bits.BitVector> lcp2Bucket
      A function mapping each longest common prefix to its bucket.
      protected int log2BucketSize
      Fast.ceilLog2(int) of bucketSize.
      protected long n
      The number of keys.
      protected GOV3Function<it.unimi.dsi.bits.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).
      protected long seed
      The seed returned by the BucketedHashStore.
      static long serialVersionUID  
      protected long signatureMask
      The mask to compare signatures, or zero for no signatures.
      protected it.unimi.dsi.fastutil.longs.LongBigList signatures
      The signatures.
      protected it.unimi.dsi.bits.TransformationStrategy<? super T> transform
      The transformation strategy.
      • Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

        defRetValue
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected LcpMonotoneMinimalPerfectHashFunction​(java.lang.Iterable<? extends T> keys, long numKeys, it.unimi.dsi.bits.TransformationStrategy<? super T> transform, int signatureWidth, java.io.File tempDir)
      Creates a new LCP monotone minimal perfect hash function for the given keys.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      long getLong​(java.lang.Object o)  
      static void main​(java.lang.String[] arg)  
      long numBits()
      Returns the number of bits used by this structure.
      long size64()  
      • Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

        defaultReturnValue, defaultReturnValue
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface it.unimi.dsi.fastutil.Function

        apply, clear
      • Methods inherited from interface java.util.function.Function

        compose
      • Methods inherited from interface it.unimi.dsi.fastutil.objects.Object2LongFunction

        andThen, andThenByte, andThenChar, andThenDouble, andThenFloat, andThenInt, andThenLong, andThenObject, andThenReference, andThenShort, applyAsLong, composeByte, composeChar, composeDouble, composeFloat, composeInt, composeLong, composeObject, composeReference, composeShort, get, getOrDefault, getOrDefault, put, put, remove, removeLong
      • Methods inherited from interface it.unimi.dsi.fastutil.Size64

        size
    • Field Detail

      • n

        protected final long n
        The number of keys.
      • bucketSize

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

        protected final int log2BucketSize
        Fast.ceilLog2(int) of bucketSize.
      • bucketSizeMask

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

        protected final GOV3Function<it.unimi.dsi.bits.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<it.unimi.dsi.bits.BitVector> lcp2Bucket
        A function mapping each longest common prefix to its bucket.
      • transform

        protected final it.unimi.dsi.bits.TransformationStrategy<? super T> transform
        The transformation strategy.
      • signatureMask

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

        protected final it.unimi.dsi.fastutil.longs.LongBigList signatures
        The signatures.
    • Constructor Detail

      • LcpMonotoneMinimalPerfectHashFunction

        protected LcpMonotoneMinimalPerfectHashFunction​(java.lang.Iterable<? extends T> keys,
                                                        long numKeys,
                                                        it.unimi.dsi.bits.TransformationStrategy<? super T> transform,
                                                        int signatureWidth,
                                                        java.io.File tempDir)
                                                 throws java.io.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:
        java.io.IOException
    • Method Detail

      • getLong

        public long getLong​(java.lang.Object o)
        Specified by:
        getLong in interface it.unimi.dsi.fastutil.objects.Object2LongFunction<T>
      • size64

        public long size64()
        Specified by:
        size64 in interface it.unimi.dsi.fastutil.Size64
        Overrides:
        size64 in class AbstractHashFunction<T>
      • numBits

        public long numBits()
        Returns the number of bits used by this structure.
        Returns:
        the number of bits used by this structure.
      • main

        public static void main​(java.lang.String[] arg)
                         throws java.lang.NoSuchMethodException,
                                java.io.IOException,
                                com.martiansoftware.jsap.JSAPException
        Throws:
        java.lang.NoSuchMethodException
        java.io.IOException
        com.martiansoftware.jsap.JSAPException