Class HashIndexSet


  • final class HashIndexSet
    extends java.lang.Object
    An index set backed by a open-addressed hash table using linear hashing. Table size is a power of 2 and has a maximum capacity of 2^29 with a fixed load factor of 0.5. If the functional capacity is exceeded then the set raises an IllegalStateException.

    Values are stored using bit inversion. Any positive index will have a negative representation when stored. An empty slot is indicated by a zero.

    This class has a minimal API. It can be used to ensure a collection of indices of a known size are unique:

    
     int[] keys = ...
     HashIndexSet set = new HashIndexSet(keys.length);
     for (int k : keys) {
       if (set.add(k)) {
         // first occurrence of k in keys
       }
     }
     
    Since:
    1.2
    See Also:
    Open addressing (Wikipedia)
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static java.lang.String INVALID_INDEX
      Message for an invalid index.
      private static int MAX_CAPACITY
      The maximum capacity of the set.
      private static int MIN_SIZE
      The minimum size of the backing array.
      private static int PHI
      Unsigned 32-bit integer numerator of the golden ratio (0.618) with an assumed denominator of 2^32.
      private int[] set
      The set.
      private int size
      The size.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private HashIndexSet​(int capacity)
      Create an instance with size to store up to the specified capacity.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) boolean add​(int index)
      Adds the index to the set.
      (package private) static HashIndexSet create​(int capacity)
      Create an instance with size to store up to the specified capacity.
      private static int mix​(int x)
      Mix the bits of an integer.
      private static int nextPow2​(int value)
      Returns the closest power-of-two number greater than or equal to value.
      • Methods inherited from class java.lang.Object

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

      • INVALID_INDEX

        private static final java.lang.String INVALID_INDEX
        Message for an invalid index.
        See Also:
        Constant Field Values
      • MAX_CAPACITY

        private static final int MAX_CAPACITY
        The maximum capacity of the set.
        See Also:
        Constant Field Values
      • MIN_SIZE

        private static final int MIN_SIZE
        The minimum size of the backing array.
        See Also:
        Constant Field Values
      • PHI

        private static final int PHI
        Unsigned 32-bit integer numerator of the golden ratio (0.618) with an assumed denominator of 2^32.
         2654435769 = round(2^32 * (sqrt(5) - 1) / 2)
         Long.toHexString((long)(0x1p32 * (Math.sqrt(5.0) - 1) / 2))
         
        See Also:
        Constant Field Values
      • set

        private final int[] set
        The set.
      • size

        private int size
        The size.
    • Constructor Detail

      • HashIndexSet

        private HashIndexSet​(int capacity)
        Create an instance with size to store up to the specified capacity.

        The functional capacity (number of indices that can be stored) is the next power of 2 above capacity; or a minimum size if the requested capacity is small.

        Parameters:
        capacity - Capacity.
    • Method Detail

      • create

        static HashIndexSet create​(int capacity)
        Create an instance with size to store up to the specified capacity. The maximum supported capacity is 229.
        Parameters:
        capacity - Capacity.
        Returns:
        the hash index set
        Throws:
        java.lang.IllegalArgumentException - if the capacity is too large.
      • nextPow2

        private static int nextPow2​(int value)
        Returns the closest power-of-two number greater than or equal to value.

        Warning: This will return Integer.MIN_VALUE for any value above 1 << 30. This is the next power of 2 as an unsigned integer.

        See Bit Hacks: Rounding up to a power of 2

        Parameters:
        value - Value.
        Returns:
        the closest power-of-two number greater than or equal to value
      • add

        boolean add​(int index)
        Adds the index to the set.
        Parameters:
        index - Index.
        Returns:
        true if the set was modified by the operation
        Throws:
        java.lang.IndexOutOfBoundsException - if the index is negative
      • mix

        private static int mix​(int x)
        Mix the bits of an integer.

        This is the fast hash function used in the linear hash implementation in the Koloboke Collections.

        Parameters:
        x - Bits.
        Returns:
        the mixed bits