jsat.utils

Class ClosedHashingUtil

java.lang.Object

jsat.utils.ClosedHashingUtil

public class ClosedHashingUtil
extends Object

This class provides some useful methods and utilities for implementing Closed Hashing structures

Author:

Edward Raff

Field Summary

Fields

Modifier and Type	Field and Description
static byte	DELETED This value indicates that the status of an open addressing space is DELETED, meaning i should not stop a search for a value - but the code is free to overwrite the values at this location and change the status to OCCUPIED.
static byte	EMPTY This value indicates that that status of an open addressing space is EMPTY, meaning any value can be stored in it
static long	EXTRA_INDEX_INFO This store the value Integer.MIN_VALUE in the upper 32 bits of a long, so that the lower 32 bits can store any regular integer.
static int	INT_MASK Applying this bitwise AND mask to a long will give the bits corresponding to an integer.
static byte	OCCUPIED This value indicates that the status of an open addressing space is OCCUPIED, meaning it is in use.
static int[]	twinPrimesP2 This array lits twin primes that are just larger than a power of 2.

Constructor Summary

Constructors

Constructor and Description
ClosedHashingUtil()

Method Summary

Modifier and Type	Method and Description
static int	getNextPow2TwinPrime(int m) Gets the next twin prime that is near a power of 2 and greater than or equal to the given value

Methods inherited from class java.lang.Object

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

Field Detail

INT_MASK

public static final int INT_MASK

Applying this bitwise AND mask to a long will give the bits corresponding to an integer.

See Also:

Constant Field Values

EMPTY

public static final byte EMPTY

This value indicates that that status of an open addressing space is EMPTY, meaning any value can be stored in it

See Also:

Constant Field Values

OCCUPIED

public static final byte OCCUPIED

This value indicates that the status of an open addressing space is OCCUPIED, meaning it is in use.

See Also:

Constant Field Values

DELETED

public static final byte DELETED

This value indicates that the status of an open addressing space is DELETED, meaning i should not stop a search for a value - but the code is free to overwrite the values at this location and change the status to OCCUPIED.
This can not be set to EMPTY unless we can guarantee that no value is stored in a index chain that stops at this location.

See Also:

Constant Field Values

EXTRA_INDEX_INFO

public static final long EXTRA_INDEX_INFO

This store the value Integer.MIN_VALUE in the upper 32 bits of a long, so that the lower 32 bits can store any regular integer. This allows a fast way to return 2 integers from one method in the form of a long. The two values can then be recovered from the upper and lower 32 bits of the long. This is meant to be used as a nonsense default value, indicating that no information is present in the upper 32 bits.

See Also:

Constant Field Values

twinPrimesP2

public static final int[] twinPrimesP2

This array lits twin primes that are just larger than a power of 2. The prime in the list will be the larger of the twins, so the smaller can be obtained by subtracting 2 from the value stored. The list is stored in sorted order.
Note, the last value stored is just under 2³¹, where the other values are just over 2^x for x < 31

Constructor Detail

ClosedHashingUtil

public ClosedHashingUtil()

Method Detail

getNextPow2TwinPrime

public static int getNextPow2TwinPrime(int m)

Gets the next twin prime that is near a power of 2 and greater than or equal to the given value

Parameters:

m - the integer to get a twine prime larger than

Returns:

the a twin prime greater than or equal to