package jsat.utils;
import java.util.Arrays;
/**
* This class provides some useful methods and utilities for implementing Closed
* Hashing structures
*
* @author Edward Raff
*/
public class ClosedHashingUtil
{
/**
* Applying this bitwise AND mask to a long will give the bits corresponding
* to an integer.
*/
public static final int INT_MASK = -1;
/**
* This value indicates that that status of an open addressing space is
* EMPTY, meaning any value can be stored in it
*/
public static final byte EMPTY = 0;
/**
* This value indicates that the status of an open addressing space is
* OCCUPIED, meaning it is in use.
*/
public static final byte OCCUPIED = EMPTY + 1;
/**
* 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 {@link #OCCUPIED}.
* This can not be set to {@link #EMPTY} unless we can guarantee that no
* value is stored in a index chain that stops at this location.
*/
public static final byte DELETED = OCCUPIED + 1;
/**
* This store the value {@link 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.
*/
public static final long EXTRA_INDEX_INFO = ((long) Integer.MIN_VALUE) << 32;
/**
* Gets the next twin prime that is near a power of 2 and greater than or
* equal to the given value
*
* @param m the integer to get a twine prime larger than
* @return the a twin prime greater than or equal to
*/
public static int getNextPow2TwinPrime(int m)
{
int pos = Arrays.binarySearch(twinPrimesP2, m+1);
if(pos >= 0)
return twinPrimesP2[pos];
else
return twinPrimesP2[-pos - 1];
}
/**
* 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 231, where the other
* values are just over 2x for x < 31
*
*/
public static final int[] twinPrimesP2 =
{
7, //2^2 , twin with 5
13, //2^3 , twin with 11
19, //2^4 , twin with 17
43, //2^5 , twin with 41
73, //2^6 , twin with 71
139, //2^7 , twin with 137
271, //2^8 , twin with 269
523, //2^9 , twin with 632
1033, //2^10 , twin with 1031
2083, //2^11 , twin with 2081
4129, //2^12 , twin with 4127
8221, //2^13 , twin with 8219
16453, //2^14 , twin with 16451
32803, //2^15 , twin with 32801
65539, //2^16 , twin with 65537
131113, //2^17 , twin with 131111
262153, //2^18 , twin with 262151
524353, //2^19 , twin with 524351
1048891, //2^20 , twin with 1048889
2097259, //2^21 , twin with 2097257
4194583, //2^22 , twin with 4194581
8388619, //2^23 , twin with 8388617
16777291, //2^24 , twin with 16777289
33554503, //2^25 , twin with 33554501
67109323, //2^26 , twin with 67109321
134217781, //2^27 , twin with 134217779
268435579, //2^28 , twin with 268435577
536871019, //2^29 , twin with 536871017
1073741833, //2^30 , twin with 1073741831
2147482951, //first twin under 2^31, twin with 2147482949
};
}
Ads help maintain this website.