Top Description Fields Constructors Methods
com.google.common.collect

pack-priv final Class CompactHashing

extends Object
Class Inheritance
Annotations
@GwtIncompatible
@ElementTypesAreNonnullByDefault
Imports
com.google.common.annotations.GwtIncompatible, com.google.common.base.Objects, com.google.common.primitives.Ints, java.util.Arrays, javax.annotation.CheckForNull, org.checkerframework.checker.nullness.qual.Nullable
Helper classes and static methods for implementing compact hash-based collections.
Author
Jon Noack

Field Summary

Modifier and TypeField and Description
private static final int
BYTE_MASK

private static final int
BYTE_MAX_SIZE

pack-priv static final int
DEFAULT_SIZE

Default size of a compact hash-based collection.

pack-priv static final int
HASH_TABLE_BITS_MASK

Bitmask that selects the low bits of metadata to get hashTableBits.

private static final int
HASH_TABLE_BITS_MAX_BITS

Number of bits used to store the numbers of hash table bits (max 30).

pack-priv static final int
MAX_SIZE

Maximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).

private static final int
MIN_HASH_TABLE_SIZE

Minimum size of the hash table of a compact hash-based collection.

pack-priv static final int
MODIFICATION_COUNT_INCREMENT

Use high bits of metadata for modification count.

private static final int
SHORT_MASK

private static final int
SHORT_MAX_SIZE

pack-priv static final byte
UNSET

Indicates blank table entries.

Constructor Summary

AccessConstructor and Description
private
CompactHashing()

Method Summary

Modifier and TypeMethod and Description
pack-priv static Object
createTable(int buckets)

Creates and returns a properly-sized array with the given number of buckets.

pack-priv static int
getHashPrefix(int value, int mask)

Returns the hash prefix given the current mask.

pack-priv static int
getNext(int entry, int mask)

Returns the index, or 0 if the entry is "null".

pack-priv static int
maskCombine(int prefix, int suffix, int mask)

Returns a new value combining the prefix and suffix using the given mask.

pack-priv static int
newCapacity(int mask)

Returns a larger power of 2 hashtable size given the current mask.

pack-priv static int
remove(Object key, Object value, int mask, Object table, int[] entries, @Nullable Object[] keys, @Nullable Object[] values)

pack-priv static void
tableClear(Object table)

pack-priv static int
tableGet(Object table, int index)

Returns table[index], where table is actually a byte[], short[], or int[].

pack-priv static void
tableSet(Object table, int index, int entry)

Sets table[index] to entry, where table is actually a byte[], short[], or int[].

pack-priv 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.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

BYTE_MASKback to summary
private static final int BYTE_MASK
BYTE_MAX_SIZEback to summary
private static final int BYTE_MAX_SIZE
DEFAULT_SIZEback to summary
pack-priv static final int DEFAULT_SIZE

Default size of a compact hash-based collection.

HASH_TABLE_BITS_MASKback to summary
pack-priv static final int HASH_TABLE_BITS_MASK

Bitmask that selects the low bits of metadata to get hashTableBits.

HASH_TABLE_BITS_MAX_BITSback to summary
private static final int HASH_TABLE_BITS_MAX_BITS

Number of bits used to store the numbers of hash table bits (max 30).

MAX_SIZEback to summary
pack-priv static final int MAX_SIZE

Maximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).

MIN_HASH_TABLE_SIZEback to summary
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.

MODIFICATION_COUNT_INCREMENTback to summary
pack-priv static final int MODIFICATION_COUNT_INCREMENT

Use high bits of metadata for modification count.

SHORT_MASKback to summary
private static final int SHORT_MASK
SHORT_MAX_SIZEback to summary
private static final int SHORT_MAX_SIZE
UNSETback to summary
pack-priv static final byte UNSET

Indicates blank table entries.

Constructor Detail

CompactHashingback to summary
private CompactHashing()

Method Detail

createTableback to summary
pack-priv static Object createTable(int buckets)

Creates and returns a properly-sized array with the given number of buckets.

getHashPrefixback to summary
pack-priv static int getHashPrefix(int value, int mask)

Returns the hash prefix given the current mask.

getNextback to summary
pack-priv static int getNext(int entry, int mask)

Returns the index, or 0 if the entry is "null".

maskCombineback to summary
pack-priv static int maskCombine(int prefix, int suffix, int mask)

Returns a new value combining the prefix and suffix using the given mask.

newCapacityback to summary
pack-priv 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.

removeback to summary
pack-priv static int remove(Object key, Object value, int mask, Object table, int[] entries, @Nullable Object[] keys, @Nullable Object[] values)
tableClearback to summary
pack-priv static void tableClear(Object table)
tableGetback to summary
pack-priv static int tableGet(Object table, int index)

Returns 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.

tableSetback to summary
pack-priv static void tableSet(Object table, int index, int entry)

Sets 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.

tableSizeback to summary
pack-priv 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.