Package com.google.common.collect
Class CompactHashing
- java.lang.Object
-
- com.google.common.collect.CompactHashing
-
final class CompactHashing extends java.lang.Object
Helper classes and static methods for implementing compact hash-based collections.
-
-
Field Summary
Fields Modifier and Type Field Description private static int
BYTE_MASK
private static int
BYTE_MAX_SIZE
(package private) static int
DEFAULT_SIZE
Default size of a compact hash-based collection.(package private) static int
HASH_TABLE_BITS_MASK
Bitmask that selects the low bits of metadata to get hashTableBits.private static int
HASH_TABLE_BITS_MAX_BITS
Number of bits used to store the numbers of hash table bits (max 30).(package private) static int
MAX_SIZE
Maximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).private static int
MIN_HASH_TABLE_SIZE
Minimum size of the hash table of a compact hash-based collection.(package private) static int
MODIFICATION_COUNT_INCREMENT
Use high bits of metadata for modification count.private static int
SHORT_MASK
private static int
SHORT_MAX_SIZE
(package private) static byte
UNSET
Indicates blank table entries.
-
Constructor Summary
Constructors Modifier Constructor Description private
CompactHashing()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description (package private) static java.lang.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(java.lang.Object key, java.lang.Object value, int mask, java.lang.Object table, int[] entries, java.lang.Object[] keys, java.lang.Object[] values)
(package private) static void
tableClear(java.lang.Object table)
(package private) static int
tableGet(java.lang.Object table, int index)
Returnstable[index]
, wheretable
is actually abyte[]
,short[]
, orint[]
.(package private) static void
tableSet(java.lang.Object table, int index, int entry)
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 Detail
-
UNSET
static final byte UNSET
Indicates blank table entries.- See Also:
- Constant Field Values
-
HASH_TABLE_BITS_MAX_BITS
private static final int HASH_TABLE_BITS_MAX_BITS
Number of bits used to store the numbers of hash table bits (max 30).- See Also:
- Constant Field Values
-
MODIFICATION_COUNT_INCREMENT
static final int MODIFICATION_COUNT_INCREMENT
Use high bits of metadata for modification count.- See Also:
- Constant Field Values
-
HASH_TABLE_BITS_MASK
static final int HASH_TABLE_BITS_MASK
Bitmask that selects the low bits of metadata to get hashTableBits.- See Also:
- Constant Field Values
-
MAX_SIZE
static final int MAX_SIZE
Maximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).- See Also:
- Constant Field Values
-
DEFAULT_SIZE
static final int DEFAULT_SIZE
Default size of a compact hash-based collection.- See Also:
- Constant Field Values
-
MIN_HASH_TABLE_SIZE
private static final int MIN_HASH_TABLE_SIZE
Minimum 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:
- Constant Field Values
-
BYTE_MAX_SIZE
private static final int BYTE_MAX_SIZE
- See Also:
- Constant Field Values
-
BYTE_MASK
private static final int BYTE_MASK
- See Also:
- Constant Field Values
-
SHORT_MAX_SIZE
private static final int SHORT_MAX_SIZE
- See Also:
- Constant Field Values
-
SHORT_MASK
private static final int SHORT_MASK
- See Also:
- Constant Field Values
-
-
Method Detail
-
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
static java.lang.Object createTable(int buckets)
Creates and returns a properly-sized array with the given number of buckets.
-
tableClear
static void tableClear(java.lang.Object table)
-
tableGet
static int tableGet(java.lang.Object table, int index)
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
static void tableSet(java.lang.Object table, int index, int entry)
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
static int remove(@CheckForNull java.lang.Object key, @CheckForNull java.lang.Object value, int mask, java.lang.Object table, int[] entries, java.lang.Object[] keys, @CheckForNull java.lang.Object[] values)
-
-