squidpony.squidmath

Class CrossHash.Hive

java.lang.Object

squidpony.squidmath.CrossHash.Hive

Enclosing class:

CrossHash

public static final class CrossHash.Hive
extends java.lang.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 and Description
Hive()

Method Summary

Modifier and Type	Method and 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(java.lang.CharSequence data)
static int	hash(java.lang.CharSequence[]... data)
static int	hash(java.lang.CharSequence[] data)
static int	hash(java.lang.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(java.lang.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(double[] data)
static int	hash(float[] data)
static int	hash(int[] data)
static int	hash(int[][] data)
static int	hash(java.lang.Iterable<? extends java.lang.CharSequence> data)
static int	hash(java.util.List<? extends java.lang.CharSequence> data)
static int	hash(long[] data)
static int	hash(long[][] data)
static int	hash(java.lang.Object data)
static int	hash(java.lang.Object[] data)
static int	hash(short[] 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(java.lang.CharSequence data)
static long	hash64(java.lang.CharSequence[]... data)
static long	hash64(java.lang.CharSequence[] data)
static long	hash64(java.lang.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(java.lang.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(double[] data)
static long	hash64(float[] data)
static long	hash64(int[] data)
static long	hash64(int[][] data)
static long	hash64(java.lang.Iterable<? extends java.lang.CharSequence> data)
static long	hash64(java.util.List<? extends java.lang.CharSequence> data)
static long	hash64(long[] data)
static long	hash64(long[][] data)
static long	hash64(java.lang.Object data)
static long	hash64(java.lang.Object[] data)
static long	hash64(short[] data)

Methods inherited from class java.lang.Object

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

Constructor Detail

Hive

public Hive()

Method Detail

hash64

public static long hash64(java.lang.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(java.lang.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(java.lang.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(java.lang.CharSequence[] data)

hash64

public static long hash64(java.lang.CharSequence[]... data)

hash64

public static long hash64(java.lang.Iterable<? extends java.lang.CharSequence> data)

hash64

public static long hash64(java.util.List<? extends java.lang.CharSequence> data)

hash64

public static long hash64(java.lang.Object[] data)

hash64

public static long hash64(java.lang.Object data)

hash

public static int hash(java.lang.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(java.lang.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(java.lang.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(java.lang.CharSequence[] data)

hash

public static int hash(java.lang.CharSequence[]... data)

hash

public static int hash(java.lang.Iterable<? extends java.lang.CharSequence> data)

hash

public static int hash(java.util.List<? extends java.lang.CharSequence> data)

hash

public static int hash(java.lang.Object[] data)

hash

public static int hash(java.lang.Object data)