Package it.unimi.dsi.big.util

Class ShiftAddXorSignedStringMap

java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<CharSequence>
it.unimi.dsi.big.util.ShiftAddXorSignedStringMap
All Implemented Interfaces:
StringMap<CharSequence>, it.unimi.dsi.fastutil.Function<CharSequence,Long>, it.unimi.dsi.fastutil.objects.Object2LongFunction<CharSequence>, it.unimi.dsi.fastutil.Size64, Serializable, Function<CharSequence,Long>, ToLongFunction<CharSequence>
@Deprecated public class ShiftAddXorSignedStringMap extends it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<CharSequence> implements StringMap<CharSequence>, Serializable
Deprecated.
There are much better and faster hash functions.
A string map based on a function signed using Shift-Add-Xor hashes.

A minimal perfect hash function maps a set of string to an initial segment of the natural numbers, but will actually map any string to that segment. By signing each output value with a hash of the string, we get a dictionary-like functionality with a rate error that can be balanced with space occupancy (signatures can go from 1 to Long.SIZE bits).

For the kind of hash we use, see “Performance in practice of string hashing functions”, by M.V. Ramakrishna and Justin Zobel, Proc. of the Fifth International Conference on Database Systems for Advanced Applications, 1997, pages 215−223.

Since:
2.0
Author:
Sebastiano Vigna
See Also:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final it.unimi.dsi.fastutil.objects.Object2LongFunction<? extends CharSequence>
    function
    Deprecated.
    The underlying map.
    protected final long
    mask
    Deprecated.
    The mask to get only width nonzero bits.
    protected final int
    shift
    Deprecated.
    The left shift to get only width nonzero bits.
    protected final it.unimi.dsi.fastutil.longs.LongBigList
    signatures
    Deprecated.
    Signatures.
    protected final int
    width
    Deprecated.
    The width in bits of each signature.

    Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

    defRetValue

  • Constructor Summary

    Constructors
    Constructor
    Description
    ShiftAddXorSignedStringMap(Iterator<? extends CharSequence> iterator, it.unimi.dsi.fastutil.objects.Object2LongFunction<? extends CharSequence> map)
    Deprecated.
    Creates a new shift-add-xor signed string map using a given hash map and 32-bit signatures.
    ShiftAddXorSignedStringMap(Iterator<? extends CharSequence> iterator, it.unimi.dsi.fastutil.objects.Object2LongFunction<? extends CharSequence> map, int signatureWidth)
    Deprecated.
    Creates a new shift-add-xor signed string map using a given hash map.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    containsKey(Object o)
    Deprecated.
     
    Long
    get(Object o)
    Deprecated.
     
    long
    getLong(Object o)
    Deprecated.
     
    it.unimi.dsi.fastutil.objects.ObjectBigList<CharSequence>
    list()
    Deprecated.
    Returns a list view of the domain of this string map (optional operation).
    static void
    main(String[] arg)
    Deprecated.
     
    int
    size()
    Deprecated.
    long
    size64()
    Deprecated.
    Returns the intended number of keys in this function, or -1 if no such number exists.

    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, defaultReturnValue, defaultReturnValue, getOrDefault, getOrDefault, put, put, remove, removeLong

  • Field Details

    • function

      protected final it.unimi.dsi.fastutil.objects.Object2LongFunction<? extends CharSequence> function
      Deprecated.
      The underlying map.

    • signatures

      protected final it.unimi.dsi.fastutil.longs.LongBigList signatures
      Deprecated.
      Signatures.

    • width

      protected final int width
      Deprecated.
      The width in bits of each signature.

    • shift

      protected final int shift
      Deprecated.
      The left shift to get only width nonzero bits.

    • mask

      protected final long mask
      Deprecated.
      The mask to get only width nonzero bits.

  • Constructor Details

    • ShiftAddXorSignedStringMap

      public ShiftAddXorSignedStringMap(Iterator<? extends CharSequence> iterator, it.unimi.dsi.fastutil.objects.Object2LongFunction<? extends CharSequence> map)
      Deprecated.
      Creates a new shift-add-xor signed string map using a given hash map and 32-bit signatures.
      Parameters:
      iterator - an iterator enumerating a set of strings.
      map - a minimal perfect hash for the strings enumerated by iterator; it must support size() and have default return value -1.

    • ShiftAddXorSignedStringMap

      public ShiftAddXorSignedStringMap(Iterator<? extends CharSequence> iterator, it.unimi.dsi.fastutil.objects.Object2LongFunction<? extends CharSequence> map, int signatureWidth)
      Deprecated.
      Creates a new shift-add-xor signed string map using a given hash map.
      Parameters:
      iterator - an iterator enumerating a set of strings.
      map - a minimal perfect hash for the strings enumerated by iterator; it must support size() and have default return value -1.
      signatureWidth - the width, in bits, of the signature of each string.

  • Method Details

    • getLong

      public long getLong(Object o)
      Deprecated.
      Specified by:
      getLong in interface it.unimi.dsi.fastutil.objects.Object2LongFunction<CharSequence>

    • get

      public Long get(Object o)
      Deprecated.
      Specified by:
      get in interface it.unimi.dsi.fastutil.Function<CharSequence,Long>
      Specified by:
      get in interface it.unimi.dsi.fastutil.objects.Object2LongFunction<CharSequence>

    • containsKey

      public boolean containsKey(Object o)
      Deprecated.
      Specified by:
      containsKey in interface it.unimi.dsi.fastutil.Function<CharSequence,Long>

    • size

      @Deprecated public int size()
      Deprecated.
      Description copied from interface: StringMap
      Specified by:
      size in interface it.unimi.dsi.fastutil.Function<CharSequence,Long>
      Specified by:
      size in interface it.unimi.dsi.fastutil.Size64
      Specified by:
      size in interface StringMap<CharSequence>

    • size64

      public long size64()
      Deprecated.
      Description copied from interface: StringMap
      Returns the intended number of keys in this function, or -1 if no such number exists.

      Most function implementations will have some knowledge of the intended number of keys in their domain. In some cases, however, this might not be possible. This default implementation, in particular, returns -1.

      Specified by:
      size64 in interface it.unimi.dsi.fastutil.Size64
      Specified by:
      size64 in interface StringMap<CharSequence>
      Returns:
      the intended number of keys in this function, or -1 if that number is not available.

    • list

      public it.unimi.dsi.fastutil.objects.ObjectBigList<CharSequence> list()
      Deprecated.
      Description copied from interface: StringMap
      Returns a list view of the domain of this string map (optional operation).

      Note that the list view acts as an inverse of the mapping implemented by this map.

      Specified by:
      list in interface StringMap<CharSequence>
      Returns:
      a list view of the domain of this string map, or null if this map does not support this operation.

    • main

      public static void main(String[] arg) throws NoSuchMethodException, IOException, com.martiansoftware.jsap.JSAPException, ClassNotFoundException
      Deprecated.
      Throws:
      NoSuchMethodException
      IOException
      com.martiansoftware.jsap.JSAPException
      ClassNotFoundException