it.unimi.dsi.fastutil
Class HashCommon

java.lang.Object
  extended by it.unimi.dsi.fastutil.HashCommon

public class HashCommon
extends Object

Common code for all hash-based classes.


Field Summary
static Object REMOVED
          This reference is used to fill keys and values of removed entries (if they are objects).
 
Constructor Summary
protected HashCommon()
           
 
Method Summary
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 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 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)
          Return the least power of two greater than or equal to the specified value.
static long nextPowerOfTwo(long x)
          Return 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
 

Field Detail

REMOVED

public static final Object REMOVED
This reference is used to fill keys and values of removed entries (if they are objects). null cannot be used as it would confuse the search algorithm in the presence of an actual null key.

Constructor Detail

HashCommon

protected HashCommon()
Method Detail

murmurHash3

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

This function implements the finalisation step of Austin Appleby's MurmurHash3. Its purpose is to avalanche the bits of the argument to within 0.25% bias. It is used, among other things, to scramble quickly (but deeply) the hash values returned by Object.hashCode().

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

murmurHash3

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

This function implements the finalisation step of Austin Appleby's MurmurHash3. Its purpose is to avalanche the bits of the argument to within 0.25% bias. It is used, among other things, to scramble quickly (but deeply) the hash values returned by Object.hashCode().

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

float2int

public static final int float2int(float f)
Returns the hash code that would be returned by Float.hashCode().

Returns:
the same code as new Float(f).hashCode().

double2int

public static final int double2int(double d)
Returns the hash code that would be returned by Double.hashCode().

Returns:
the same code as new Double(f).hashCode().

long2int

public static final int long2int(long l)
Returns the hash code that would be returned by Long.hashCode().

Returns:
the same code as new Long(f).hashCode().

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.

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)
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.

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.


Copyright © 2011. All Rights Reserved.