Class HashIndexSet

java.lang.Object
org.apache.commons.numbers.arrays.HashIndexSet
final class HashIndexSet extends 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:

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final String
    INVALID_INDEX
    Message for an invalid index.
    private static final int
    MAX_CAPACITY
    The maximum capacity of the set.
    private static final int
    MIN_SIZE
    The minimum size of the backing array.
    private static final int
    PHI
    Unsigned 32-bit integer numerator of the golden ratio (0.618) with an assumed denominator of 2^32.
    private final 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

    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 Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • INVALID_INDEX

      private static final String INVALID_INDEX
      Message for an invalid index.
      See Also:

    • MAX_CAPACITY

      private static final int MAX_CAPACITY
      The maximum capacity of the set.
      See Also:

    • MIN_SIZE

      private static final int MIN_SIZE
      The minimum size of the backing array.
      See Also:

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

    • set

      private final int[] set
      The set.

    • size

      private int size
      The size.

  • Constructor Details

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

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