Class HashIndexSet
java.lang.Object
org.apache.commons.numbers.arrays.HashIndexSet
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
FieldsModifier and TypeFieldDescriptionprivate static final String
Message for an invalid index.private static final int
The maximum capacity of the set.private static final int
The minimum size of the backing array.private static final int
Unsigned 32-bit integer numerator of the golden ratio (0.618) with an assumed denominator of 2^32.private final int[]
The set.private int
The size. -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
HashIndexSet
(int capacity) Create an instance with size to store up to the specifiedcapacity
. -
Method Summary
Modifier and TypeMethodDescription(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 Details
-
INVALID_INDEX
Message for an invalid index.- See Also:
-
MAX_CAPACITY
private static final int MAX_CAPACITYThe maximum capacity of the set.- See Also:
-
MIN_SIZE
private static final int MIN_SIZEThe minimum size of the backing array.- See Also:
-
PHI
private static final int PHIUnsigned 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[] setThe set. -
size
private int sizeThe size.
-
-
Constructor Details
-
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 Details
-
create
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:
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:
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
-