Class CompactHashing

java.lang.Object
com.google.common.collect.CompactHashing

final class CompactHashing extends Object
Helper classes and static methods for implementing compact hash-based collections.
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private 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
    Modifier
    Constructor
    Description
    private
     
  • Method Summary

    Modifier and Type
    Method
    Description
    (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
     
    (package private) static int
    tableGet(Object table, int index)
    Returns table[index], where table is actually a byte[], short[], or int[].
    (package private) static void
    tableSet(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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • UNSET

      static final byte UNSET
      Indicates blank table entries.
      See Also:
    • 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:
    • MODIFICATION_COUNT_INCREMENT

      static final int MODIFICATION_COUNT_INCREMENT
      Use high bits of metadata for modification count.
      See Also:
    • HASH_TABLE_BITS_MASK

      static final int HASH_TABLE_BITS_MASK
      Bitmask that selects the low bits of metadata to get hashTableBits.
      See Also:
    • MAX_SIZE

      static final int MAX_SIZE
      Maximum size of a compact hash-based collection (2^30 - 1 because 0 is UNSET).
      See Also:
    • DEFAULT_SIZE

      static final int DEFAULT_SIZE
      Default size of a compact hash-based collection.
      See Also:
    • 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:
    • 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

      static Object createTable(int buckets)
      Creates and returns a properly-sized array with the given number of buckets.
    • tableClear

      static void tableClear(Object table)
    • tableGet

      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.
    • tableSet

      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.
    • 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 Object key, @CheckForNull Object value, int mask, Object table, int[] entries, Object[] keys, @CheckForNull Object[] values)