Package com.google.common.collect

Class 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)  
      (package private) static void tableSet​(java.lang.Object table, int index, int entry)  
      (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 Detail

      • 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

    • Constructor Detail

      • CompactHashing

        private CompactHashing()

    • 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)

      • tableSet

        static void tableSet​(java.lang.Object table,
                     int index,
                     int entry)

      • 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​(java.lang.Object key,
                  java.lang.Object value,
                  int mask,
                  java.lang.Object table,
                  int[] entries,
                  java.lang.Object[] keys,
                  java.lang.Object[] values)