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 int
private static final int
(package private) static final int
Default size of a compact hash-based collection.(package private) static final int
Bitmask that selects the low bits of metadata to get hashTableBits.private static final int
Number of bits used to store the numbers of hash table bits (max 30).(package private) static final int
Maximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).private static final int
Minimum size of the hash table of a compact hash-based collection.(package private) static final int
Use high bits of metadata for modification count.private static final int
private static final int
(package private) static final byte
Indicates blank table entries. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) static Object
createTable
(int buckets) Creates and returns a properly-sized array with the given number of buckets.(package private) static int
getHashPrefix
(int value, int mask) Returns the hash prefix given the current mask.(package private) static int
getNext
(int entry, int mask) Returns the index, or 0 if the entry is "null".(package private) static int
maskCombine
(int prefix, int suffix, int mask) Returns a new value combining the prefix and suffix using the given mask.(package private) static int
newCapacity
(int mask) Returns a larger power of 2 hashtable size given the current mask.(package private) static int
remove
(Object key, Object value, int mask, Object table, int[] entries, Object[] keys, Object[] values) (package private) static void
tableClear
(Object table) (package private) static int
Returnstable[index]
, wheretable
is actually abyte[]
,short[]
, orint[]
.(package private) static void
Setstable[index]
toentry
, wheretable
is actually abyte[]
,short[]
, orint[]
.(package private) 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.
-
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]
, wheretable
is 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
, wheretable
is actually abyte[]
,short[]
, orint[]
. The value ofentry
should fit in the size of the assigned array element, when seen as an unsigned value. So iftable
is abyte[]
then we should have0 ≤ entry ≤ 255
, and iftable
is 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
-