Package squidpony.squidmath

Class HashCommon

java.lang.Object
squidpony.squidmath.HashCommon
public class HashCommon
extends Object
Code used internally for hashing OrderedMap, OrderedSet, IntDoubleOrderedMap, Arrangement, and so on. Has some methods and constants that may be useful in other kinds of code. Created by Tommy Ettinger on 7/28/2017.

  • Field Details

  • Method Details

    • mixOther

      public static int mixOther​(int x)
      Thoroughly mixes the bits of an integer.
      This method mixes the bits of the argument using a multiplication by a smaller int (19 bits) followed by XOR with two different rotations of the earlier product; it should work well even on GWT, where overflow can't be relied on without bitwise operations being used. The previous mix(int) method would lose precision rather than overflowing on GWT, which could have serious effects on the performance of a hash table (where lost precision means more collisions). This is a little slower than mix(int), and does almost exactly as well at avoiding collisions on most input, so mix() is preferred.
      Parameters:
      x - an integer.
      Returns:
      a hash value obtained by mixing the bits of x.

    • mix

      public static int mix​(int n)
      Thoroughly mixes the bits of an integer.
      This method acts like mixOriginal(int) (which is used by Koloboke and Fastutil), but doesn't multiply by any too-large numbers to ease compatibility with GWT. Specifically, it multiplies n by 0x9E375 (found using the golden ratio times 2 to the 20, minus 2 to improve quality slightly) then xors that with itself unsigned-right-shifted by 16 before returning. It tends to have less pathologically-bad cases than using an unmixed integer in a hash table, but will still often have more collisions than an unmixed integer if that hash table is filled with numbers that vary in their lower bits. The value of this is that when ints are given that only differ in their upper bits, if you didn't mix a hash code you would have 95% or higher collision rates in some cases. This acts as a safeguard for that kind of scenario.
      This replaces mixOther(int), which is also GWT-compatible but is a little slower without offering any improvement in collision rates.
      This is used in IntDoubleOrderedMap and IntIntOrderedMap, at the least. The algorithm this uses is also used by CrossHash.defaultHasher.
      Parameters:
      n - an integer.
      Returns:
      a hash value obtained by mixing the bits of 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 (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.
      See Also:
      invMix(long)

    • nextPowerOfTwo

      public static int nextPowerOfTwo​(int x)
      Return 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.
      This is a cleaned-up Java version of this C code.
      Parameters:
      x - a non-negative int.
      Returns:
      the least power of two greater than or equal to the specified value.

    • nextPowerOfTwo

      public static long nextPowerOfTwo​(long x)
      Return 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.
      This is a cleaned-up Java version of this C code.
      Parameters:
      x - a non-negative long.
      Returns:
      the least power of two greater than or equal to the specified value.