Package com.google.common.collect
Class CompactHashing
java.lang.Object
com.google.common.collect.CompactHashing
Helper classes and static methods for implementing compact hash-based collections.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final intprivate static final int(package private) static final intDefault size of a compact hash-based collection.(package private) static final intBitmask that selects the low bits of metadata to get hashTableBits.private static final intNumber of bits used to store the numbers of hash table bits (max 30).(package private) static final intMaximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).private static final intMinimum size of the hash table of a compact hash-based collection.(package private) static final intUse high bits of metadata for modification count.private static final intprivate static final int(package private) static final byteIndicates blank table entries. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static ObjectcreateTable(int buckets) Creates and returns a properly-sized array with the given number of buckets.(package private) static intgetHashPrefix(int value, int mask) Returns the hash prefix given the current mask.(package private) static intgetNext(int entry, int mask) Returns the index, or 0 if the entry is "null".(package private) static intmaskCombine(int prefix, int suffix, int mask) Returns a new value combining the prefix and suffix using the given mask.(package private) static intnewCapacity(int mask) Returns a larger power of 2 hashtable size given the current mask.(package private) static intremove(Object key, Object value, int mask, Object table, int[] entries, Object[] keys, Object[] values) (package private) static voidtableClear(Object table) (package private) static intReturnstable[index], wheretableis actually abyte[],short[], orint[].(package private) static voidSetstable[index]toentry, wheretableis actually abyte[],short[], orint[].(package private) static inttableSize(int expectedSize) Returns the power of 2 hashtable size required to hold the expected number of items or the minimum hashtable size, whichever is greater.
-
Field Details
-
UNSET
static final byte UNSETIndicates blank table entries.- See Also:
-
HASH_TABLE_BITS_MAX_BITS
private static final int HASH_TABLE_BITS_MAX_BITSNumber of bits used to store the numbers of hash table bits (max 30).- See Also:
-
MODIFICATION_COUNT_INCREMENT
static final int MODIFICATION_COUNT_INCREMENTUse high bits of metadata for modification count.- See Also:
-
HASH_TABLE_BITS_MASK
static final int HASH_TABLE_BITS_MASKBitmask that selects the low bits of metadata to get hashTableBits.- See Also:
-
MAX_SIZE
static final int MAX_SIZEMaximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).- See Also:
-
DEFAULT_SIZE
static final int DEFAULT_SIZEDefault size of a compact hash-based collection.- See Also:
-
MIN_HASH_TABLE_SIZE
private static final int MIN_HASH_TABLE_SIZEMinimum size of the hash table of a compact hash-based collection. Because small hash tables use a byte[], any smaller size uses the same amount of memory due to object padding.- See Also:
-
BYTE_MAX_SIZE
private static final int BYTE_MAX_SIZE- See Also:
-
BYTE_MASK
private static final int BYTE_MASK- See Also:
-
SHORT_MAX_SIZE
private static final int SHORT_MAX_SIZE- See Also:
-
SHORT_MASK
private static final int SHORT_MASK- See Also:
-
-
Constructor Details
-
CompactHashing
private CompactHashing()
-
-
Method Details
-
tableSize
static int tableSize(int expectedSize) Returns the power of 2 hashtable size required to hold the expected number of items or the minimum hashtable size, whichever is greater. -
createTable
Creates and returns a properly-sized array with the given number of buckets. -
tableClear
-
tableGet
Returnstable[index], wheretableis actually abyte[],short[], orint[]. When it is abyte[]orshort[], the returned value is unsigned, so the range of possible returned values is 0–255 or 0–65535, respectively. -
tableSet
Setstable[index]toentry, wheretableis actually abyte[],short[], orint[]. The value ofentryshould fit in the size of the assigned array element, when seen as an unsigned value. So iftableis abyte[]then we should have0 ≤ entry ≤ 255, and iftableis ashort[]then we should have0 ≤ entry ≤ 65535. It is the caller's responsibility to ensure this. -
newCapacity
static int newCapacity(int mask) Returns a larger power of 2 hashtable size given the current mask.For hashtable sizes less than or equal to 32, the returned power of 2 is 4x the current hashtable size to reduce expensive rehashing. Otherwise the returned power of 2 is 2x the current hashtable size.
-
getHashPrefix
static int getHashPrefix(int value, int mask) Returns the hash prefix given the current mask. -
getNext
static int getNext(int entry, int mask) Returns the index, or 0 if the entry is "null". -
maskCombine
static int maskCombine(int prefix, int suffix, int mask) Returns a new value combining the prefix and suffix using the given mask. -
remove
-