final class CompactHashing
extends java.lang.Object
Modifier and Type | Field and 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.
|
Modifier | Constructor and Description |
---|---|
private |
CompactHashing() |
Modifier and Type | Method and 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)
Returns
table[index] , where table is actually a byte[] , short[] , or int[] . |
(package private) static void |
tableSet(java.lang.Object table,
int index,
int entry)
Sets
table[index] to entry , where table is actually a byte[] ,
short[] , or int[] . |
(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.
|
static final byte UNSET
private static final int HASH_TABLE_BITS_MAX_BITS
static final int MODIFICATION_COUNT_INCREMENT
static final int HASH_TABLE_BITS_MASK
static final int MAX_SIZE
static final int DEFAULT_SIZE
private static final int MIN_HASH_TABLE_SIZE
private static final int BYTE_MAX_SIZE
private static final int BYTE_MASK
private static final int SHORT_MAX_SIZE
private static final int SHORT_MASK
static int tableSize(int expectedSize)
static java.lang.Object createTable(int buckets)
static void tableClear(java.lang.Object table)
static int tableGet(java.lang.Object table, int index)
table[index]
, where table
is actually a byte[]
, short[]
, or int[]
. When it is a byte[]
or short[]
, the returned value
is unsigned, so the range of possible returned values is 0–255 or 0–65535, respectively.static void tableSet(java.lang.Object table, int index, int entry)
table[index]
to entry
, where table
is actually a byte[]
,
short[]
, or int[]
. The value of entry
should fit in the size of the
assigned array element, when seen as an unsigned value. So if table
is a byte[]
then we should have 0 ≤ entry ≤ 255
, and if table
is a short[]
then we
should have 0 ≤ entry ≤ 65535
. It is the caller's responsibility to ensure this.static int newCapacity(int 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.
static int getHashPrefix(int value, int mask)
static int getNext(int entry, int mask)
static int maskCombine(int prefix, int suffix, int mask)
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)