Class HashIndexSet
- java.lang.Object
-
- org.apache.commons.numbers.arrays.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 anIllegalStateException
.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 specifiedcapacity
.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) boolean
add(int index)
Adds theindex
to the set.(package private) static HashIndexSet
create(int capacity)
Create an instance with size to store up to the specifiedcapacity
.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 tovalue
.
-
-
-
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 specifiedcapacity
.The functional capacity (number of indices that can be stored) is the next power of 2 above
capacity
; or a minimum size if the requestedcapacity
is small.- Parameters:
capacity
- Capacity.
-
-
Method Detail
-
create
static HashIndexSet create(int capacity)
Create an instance with size to store up to the specifiedcapacity
. The maximum supportedcapacity
is 229.- Parameters:
capacity
- Capacity.- Returns:
- the hash index set
- Throws:
java.lang.IllegalArgumentException
- if thecapacity
is too large.
-
nextPow2
private static int nextPow2(int value)
Returns the closest power-of-two number greater than or equal tovalue
.Warning: This will return
Integer.MIN_VALUE
for anyvalue
above1 << 30
. This is the next power of 2 as an unsigned integer.- Parameters:
value
- Value.- Returns:
- the closest power-of-two number greater than or equal to value
-
add
boolean add(int index)
Adds theindex
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
-
-