Package it.unimi.dsi.fastutil

Class HashCommon

java.lang.Object
it.unimi.dsi.fastutil.HashCommon
public class HashCommon extends Object
Common code for all hash-based classes.

  • Method Summary

    Modifier and Type
    Method
    Description
    static int
    arraySize(int expected, float f)
    Returns the least power of two smaller than or equal to 230 and larger than or equal to Math.ceil(expected / f).
    static long
    bigArraySize(long expected, float f)
    Returns the least power of two larger than or equal to Math.ceil(expected / f).
    static int
    double2int(double d)
    Returns the hash code that would be returned by Double.hashCode().
    static int
    float2int(float f)
    Returns the hash code that would be returned by Float.hashCode().
    static int
    invMix(int x)
    The inverse of mix(int).
    static long
    invMix(long x)
    The inverse of mix(long).
    static int
    long2int(long l)
    Returns the hash code that would be returned by Long.hashCode().
    static int
    maxFill(int n, float f)
    Returns the maximum number of entries that can be filled before rehashing.
    static long
    maxFill(long n, float f)
    Returns the maximum number of entries that can be filled before rehashing.
    static int
    mix(int x)
    Quickly mixes the bits of an integer.
    static long
    mix(long x)
    Quickly mixes the bits of a long integer.
    static int
    murmurHash3(int x)
    Avalanches the bits of an integer by applying the finalisation step of MurmurHash3.
    static long
    murmurHash3(long x)
    Avalanches the bits of a long integer by applying the finalisation step of MurmurHash3.
    static int
    nextPowerOfTwo(int x)
    Returns the least power of two greater than or equal to the specified value.
    static long
    nextPowerOfTwo(long x)
    Returns the least power of two greater than or equal to the specified value.

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • murmurHash3

      public static int murmurHash3(int x)
      Avalanches the bits of an integer by applying the finalisation step of MurmurHash3.

      This method implements the finalisation step of Austin Appleby's MurmurHash3. Its purpose is to avalanche the bits of the argument to within 0.25% bias.

      Parameters:
      x - an integer.
      Returns:
      a hash value with good avalanching properties.

    • murmurHash3

      public static long murmurHash3(long x)
      Avalanches the bits of a long integer by applying the finalisation step of MurmurHash3.

      This method implements the finalisation step of Austin Appleby's MurmurHash3. Its purpose is to avalanche the bits of the argument to within 0.25% bias.

      Parameters:
      x - a long integer.
      Returns:
      a hash value with good avalanching properties.

    • mix

      public static int mix(int x)
      Quickly mixes the bits of an integer.

      This method mixes the bits of the argument by multiplying by the golden ratio and xorshifting the result. It is borrowed from Koloboke, and it has slightly worse behaviour than murmurHash3(int) (in open-addressing hash tables the average number of probes is slightly larger), but it's much faster.

      Parameters:
      x - an integer.
      Returns:
      a hash value obtained by mixing the bits of x.
      See Also:

    • invMix

      public static int invMix(int x)
      The inverse of mix(int). This method is mainly useful to create unit tests.
      Parameters:
      x - an integer.
      Returns:
      a value that passed through mix(int) would give x.

    • mix

      public static long mix(long x)
      Quickly mixes the bits of a long integer.

      This method mixes the bits of the argument by multiplying by the golden ratio and xorshifting twice the result. It is borrowed from Koloboke, and it has slightly worse behaviour than murmurHash3(long) (in open-addressing hash tables the average number of probes is slightly larger), but it's much faster.

      Parameters:
      x - a long integer.
      Returns:
      a hash value obtained by mixing the bits of x.

    • invMix

      public static long invMix(long x)
      The inverse of mix(long). This method is mainly useful to create unit tests.
      Parameters:
      x - a long integer.
      Returns:
      a value that passed through mix(long) would give x.

    • float2int

      public static int float2int(float f)
      Returns the hash code that would be returned by Float.hashCode().
      Parameters:
      f - a float.
      Returns:
      the same code as new Float(f).hashCode().

    • double2int

      public static int double2int(double d)
      Returns the hash code that would be returned by Double.hashCode().
      Parameters:
      d - a double.
      Returns:
      the same code as new Double(f).hashCode().

    • long2int

      public static int long2int(long l)
      Returns the hash code that would be returned by Long.hashCode().
      Parameters:
      l - a long.
      Returns:
      the same code as new Long(f).hashCode().

    • nextPowerOfTwo

      public static int nextPowerOfTwo(int x)
      Returns the least power of two greater than or equal to the specified value.

      Note that this function will return 1 when the argument is 0.

      Parameters:
      x - an integer smaller than or equal to 230.
      Returns:
      the least power of two greater than or equal to the specified value.

    • nextPowerOfTwo

      public static long nextPowerOfTwo(long x)
      Returns the least power of two greater than or equal to the specified value.

      Note that this function will return 1 when the argument is 0.

      Parameters:
      x - a long integer smaller than or equal to 262.
      Returns:
      the least power of two greater than or equal to the specified value.

    • maxFill

      public static int maxFill(int n, float f)
      Returns the maximum number of entries that can be filled before rehashing.
      Parameters:
      n - the size of the backing array.
      f - the load factor.
      Returns:
      the maximum number of entries before rehashing.

    • maxFill

      public static long maxFill(long n, float f)
      Returns the maximum number of entries that can be filled before rehashing.
      Parameters:
      n - the size of the backing array.
      f - the load factor.
      Returns:
      the maximum number of entries before rehashing.

    • arraySize

      public static int arraySize(int expected, float f)
      Returns the least power of two smaller than or equal to 230 and larger than or equal to Math.ceil(expected / f).
      Parameters:
      expected - the expected number of elements in a hash table.
      f - the load factor.
      Returns:
      the minimum possible size for a backing array.
      Throws:
      IllegalArgumentException - if the necessary size is larger than 230.

    • bigArraySize

      public static long bigArraySize(long expected, float f)
      Returns the least power of two larger than or equal to Math.ceil(expected / f).
      Parameters:
      expected - the expected number of elements in a hash table.
      f - the load factor.
      Returns:
      the minimum possible size for a backing big array.