Package squidpony.squidmath

Class CrossHash.Hive

java.lang.Object
squidpony.squidmath.CrossHash.Hive
Enclosing class:
CrossHash
public static final class CrossHash.Hive
extends Object
A reasonably-fast hashing function that passes some of SMHasher's quality tests, but neither critically fails nor overwhelmingly succeeds the full SMHasher test battery. This was the default used by methods in the outer class like CrossHash.hash(int[]), but it has been replaced there by CrossHash.Water; you should prefer using the outer class since this inner class is only here for reference. The one advantage Hive has over Water is potentially better optimization for GWT, but since the main usage of CrossHash is for 64-bit hashes, GWT will be slow regardless for that usage.
This mixes three different algorithms: the main one is used whenever inputs or outputs are 64-bit (so, all hash64() overloads and hash(long[]) for long and double), a modification of the main one to perform better on GWT (only used on hash() overloads, and only when inputs are individually 32-bit or less), and a simpler algorithm (which was called Jolt) for hash64() on boolean and byte data.
Speed-wise, the main algorithm is about 20% slower than Wisp, but in hash tables it doesn't have clear failure cases like Wisp does on some inputs (such as fixed-length Strings with identical prefixes). If collisions are expensive or profiling shows that Wisp's algorithm is colliding at a high rate, you should probably use the normal IHasher and CrossHash.hash() methods, since those will use Hive. The modified algorithm for GWT is a little slower than the main algorithm in the C++ implementation that was used to check SMHasher quality, but it may perform similarly to the main algorithm in Java on desktop platforms. Since it avoids creating longs or doing any math on them, it should be at least 3x faster than the main algorithm on GWT (a GWT long is internally represented by 3 JS numbers, so barring special optimizations it takes at least 3x as many math operations to use longs there).
Its design uses two states like CrossHash.Lightning or CrossHash.Wisp, updating them differently from each other, and bitwise-rotates one at each step. It combines the states (xorshifting one state, multiplying it by a huge constant, and adding that to the other state) and then runs that through MurmurHash3's finalization function (its fmix64() function; the main algorithm elides one xorshift at the end that proved unnecessary). Parts of the code here are inspired by the design of DiverRNG, particularly its determine() method since both use an XLCG (XOR Linear Congruential Generator, as PractRand calls it) as a processing step.
The name comes from the song I was listening to when I finally got the tests to pass ("Slave The Hive" by High On Fire) and from the wide assortment of code that I had to employ to achieve a SMHasher successful run (which turned out to be not-so-successful).

  • Constructor Summary

    Constructors 
    Constructor Description
    Hive()  

  • Method Summary

    Modifier and Type Method Description
    static int hash​(boolean[] data)  
    static int hash​(byte[] data)  
    static int hash​(char[] data)  
    static int hash​(char[][] data)  
    static int hash​(char[] data, int start, int end)
    Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
    static int hash​(char[] data, int start, int end, int step)
    Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
    static int hash​(double[] data)  
    static int hash​(float[] data)  
    static int hash​(int[] data)  
    static int hash​(int[][] data)  
    static int hash​(long[] data)  
    static int hash​(long[][] data)  
    static int hash​(short[] data)  
    static int hash​(CharSequence data)  
    static int hash​(CharSequence[] data)  
    static int hash​(CharSequence[]... data)  
    static int hash​(CharSequence data, int start, int end)
    Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
    static int hash​(CharSequence data, int start, int end, int step)
    Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
    static int hash​(Iterable<? extends CharSequence> data)  
    static int hash​(Object data)  
    static int hash​(Object[] data)  
    static int hash​(List<? extends CharSequence> data)  
    static long hash64​(boolean[] data)  
    static long hash64​(byte[] data)  
    static long hash64​(char[] data)  
    static long hash64​(char[][] data)  
    static long hash64​(char[] data, int start, int end)
    Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
    static long hash64​(char[] data, int start, int end, int step)
    Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
    static long hash64​(double[] data)  
    static long hash64​(float[] data)  
    static long hash64​(int[] data)  
    static long hash64​(int[][] data)  
    static long hash64​(long[] data)  
    static long hash64​(long[][] data)  
    static long hash64​(short[] data)  
    static long hash64​(CharSequence data)  
    static long hash64​(CharSequence[] data)  
    static long hash64​(CharSequence[]... data)  
    static long hash64​(CharSequence data, int start, int end)
    Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
    static long hash64​(CharSequence data, int start, int end, int step)
    Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
    static long hash64​(Iterable<? extends CharSequence> data)  
    static long hash64​(Object data)  
    static long hash64​(Object[] data)  
    static long hash64​(List<? extends CharSequence> data)  

    Methods inherited from class java.lang.Object

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

  • Constructor Details

  • Method Details

    • hash64

      public static long hash64​(CharSequence data)

    • hash64

      public static long hash64​(boolean[] data)

    • hash64

      public static long hash64​(byte[] data)

    • hash64

      public static long hash64​(short[] data)

    • hash64

      public static long hash64​(int[] data)

    • hash64

      public static long hash64​(long[] data)

    • hash64

      public static long hash64​(char[] data)

    • hash64

      public static long hash64​(float[] data)

    • hash64

      public static long hash64​(double[] data)

    • hash64

      public static long hash64​(char[] data, int start, int end)
      Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
      Parameters:
      data - the char array to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      Returns:
      a 32-bit hash code for the requested section of data

    • hash64

      public static long hash64​(CharSequence data, int start, int end)
      Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
      Parameters:
      data - the String or other CharSequence to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      Returns:
      a 32-bit hash code for the requested section of data

    • hash64

      public static long hash64​(char[] data, int start, int end, int step)
      Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
      Parameters:
      data - the char array to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      step - how many elements to advance after using one element from data; must be greater than 0
      Returns:
      a 32-bit hash code for the requested section of data

    • hash64

      public static long hash64​(CharSequence data, int start, int end, int step)
      Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
      Parameters:
      data - the String or other CharSequence to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      step - how many elements to advance after using one element from data; must be greater than 0
      Returns:
      a 32-bit hash code for the requested section of data

    • hash64

      public static long hash64​(char[][] data)

    • hash64

      public static long hash64​(int[][] data)

    • hash64

      public static long hash64​(long[][] data)

    • hash64

      public static long hash64​(CharSequence[] data)

    • hash64

      public static long hash64​(CharSequence[]... data)

    • hash64

      public static long hash64​(Iterable<? extends CharSequence> data)

    • hash64

      public static long hash64​(List<? extends CharSequence> data)

    • hash64

      public static long hash64​(Object[] data)

    • hash64

      public static long hash64​(Object data)

    • hash

      public static int hash​(CharSequence data)

    • hash

      public static int hash​(boolean[] data)

    • hash

      public static int hash​(byte[] data)

    • hash

      public static int hash​(short[] data)

    • hash

      public static int hash​(int[] data)

    • hash

      public static int hash​(long[] data)

    • hash

      public static int hash​(char[] data)

    • hash

      public static int hash​(float[] data)

    • hash

      public static int hash​(double[] data)

    • hash

      public static int hash​(char[] data, int start, int end)
      Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
      Parameters:
      data - the char array to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      Returns:
      a 32-bit hash code for the requested section of data

    • hash

      public static int hash​(CharSequence data, int start, int end)
      Hashes only a subsection of the given data, starting at start (inclusive) and ending before end (exclusive).
      Parameters:
      data - the String or other CharSequence to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      Returns:
      a 32-bit hash code for the requested section of data

    • hash

      public static int hash​(char[] data, int start, int end, int step)
      Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
      Parameters:
      data - the char array to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      step - how many elements to advance after using one element from data; must be greater than 0
      Returns:
      a 32-bit hash code for the requested section of data

    • hash

      public static int hash​(CharSequence data, int start, int end, int step)
      Hashes only a subsection of the given data, starting at start (inclusive), ending before end (exclusive), and moving between chars in increments of step (which is always greater than 0).
      Parameters:
      data - the String or other CharSequence to hash
      start - the start of the section to hash (inclusive)
      end - the end of the section to hash (exclusive)
      step - how many elements to advance after using one element from data; must be greater than 0
      Returns:
      a 32-bit hash code for the requested section of data

    • hash

      public static int hash​(char[][] data)

    • hash

      public static int hash​(int[][] data)

    • hash

      public static int hash​(long[][] data)

    • hash

      public static int hash​(CharSequence[] data)

    • hash

      public static int hash​(CharSequence[]... data)

    • hash

      public static int hash​(Iterable<? extends CharSequence> data)

    • hash

      public static int hash​(List<? extends CharSequence> data)

    • hash

      public static int hash​(Object[] data)

    • hash

      public static int hash​(Object data)