it.unimi.dsi.fastutil

Class HashCommon

java.lang.Object

it.unimi.dsi.fastutil.HashCommon

public class HashCommon
extends java.lang.Object

NOTE: This source code was copied from the fastutil project, and has been modified.

Common code for all hash-based classes.

Author:

Sebastiano Vigna

See Also:

fastutil

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	HashCommon()

Method Summary

Modifier and Type	Method and 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

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

Constructor Detail

HashCommon

protected HashCommon()

Method Detail

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(int)

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 2³⁰.

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 2⁶².

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 2³⁰ 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:

java.lang.IllegalArgumentException - if the necessary size is larger than 2³⁰.

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.