Package org.agrona.collections
Class IntHashSet
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractSet<java.lang.Integer>
-
- org.agrona.collections.IntHashSet
-
- All Implemented Interfaces:
java.lang.Iterable<java.lang.Integer>
,java.util.Collection<java.lang.Integer>
,java.util.Set<java.lang.Integer>
public class IntHashSet extends java.util.AbstractSet<java.lang.Integer>
Open-addressing with linear-probing expandable hash set. Allocation free in steady state use when expanded.By storing elements as int primitives this significantly reduces memory consumption compared with Java's builtin
HashSet<Integer>
. It implementsSet<Integer>
for convenience, but calling functionality via those methods can add boxing overhead to your usage.This class is not Threadsafe.
This HashSet caches its iterator object by default, so nested iteration is not supported. You can override this behaviour at construction by indicating that the iterator should not be cached.
- See Also:
IntHashSet.IntIterator
,Set
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
IntHashSet.IntIterator
Iterator which supports unboxed access to the values viaIntHashSet.IntIterator.nextValue()
.
-
Field Summary
Fields Modifier and Type Field Description private boolean
containsMissingValue
static int
DEFAULT_INITIAL_CAPACITY
The initial capacity used when none is specified in the constructor.private IntHashSet.IntIterator
iterator
private float
loadFactor
(package private) static int
MISSING_VALUE
private int
resizeThreshold
private boolean
shouldAvoidAllocation
private int
sizeOfArrayValues
private int[]
values
-
Constructor Summary
Constructors Constructor Description IntHashSet()
Construct a hash set withDEFAULT_INITIAL_CAPACITY
,Hashing.DEFAULT_LOAD_FACTOR
, iterator caching support and0
as a missing value.IntHashSet(int proposedCapacity)
Construct a hash set with a proposed capacity,Hashing.DEFAULT_LOAD_FACTOR
, iterator caching support and0
as a missing value.IntHashSet(int proposedCapacity, float loadFactor)
Construct a hash set with a proposed initial capacity, load factor, iterator caching support and0
as a missing value.IntHashSet(int proposedCapacity, float loadFactor, boolean shouldAvoidAllocation)
Construct a hash set with a proposed initial capacity, load factor, iterator caching support and-1
as a missing value.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(int value)
Primitive specialised overload of {this#add(Integer)}.boolean
add(java.lang.Integer value)
boolean
addAll(java.util.Collection<? extends java.lang.Integer> coll)
boolean
addAll(IntHashSet coll)
Alias foraddAll(Collection)
for the specialized case when adding another IntHashSet, avoids boxing and allocations.int
capacity()
Get the total capacity for the set to which the load factor with be a fraction of.void
clear()
void
compact()
Compact the backing arrays by rehashing with a capacity just larger than current size and giving consideration to the load factor.(package private) void
compactChain(int deleteIndex)
boolean
contains(int value)
Contains method that does not box values.boolean
contains(java.lang.Object value)
boolean
containsAll(IntHashSet coll)
IntHashSet specialised variant of {this#containsAll(Collection)}.void
copy(IntHashSet that)
Copy values from anotherIntHashSet
into this one.private void
copyValues(java.lang.Object[] arrayCopy)
IntHashSet
difference(IntHashSet other)
Fast Path set difference for comparison with another IntHashSet.boolean
equals(java.lang.Object other)
void
forEachInt(java.util.function.IntConsumer action)
Iterate over the collection without boxing.int
hashCode()
private void
increaseCapacity()
boolean
isEmpty()
IntHashSet.IntIterator
iterator()
float
loadFactor()
Get the load factor beyond which the set will increase size.private static int
next(int index, int mask)
private void
rehash(int newCapacity)
boolean
remove(int value)
Specialised version of {this#remove(Object)} for int.boolean
remove(java.lang.Object value)
boolean
removeAll(java.util.Collection<?> coll)
boolean
removeAll(IntHashSet coll)
Alias forremoveAll(Collection)
for the specialized case when removing another IntHashSet, avoids boxing and allocations.boolean
removeIf(java.util.function.Predicate<? super java.lang.Integer> filter)
boolean
removeIfInt(java.util.function.IntPredicate filter)
Removes all the elements of this collection that satisfy the given predicate.int
resizeThreshold()
Get the actual threshold which when reached the map will resize.boolean
retainAll(java.util.Collection<?> coll)
boolean
retainAll(IntHashSet coll)
Alias forretainAll(Collection)
for the specialized case when retaining on another IntHashSet, avoids boxing and allocations.int
size()
java.lang.Object[]
toArray()
<T> T[]
toArray(T[] a)
java.lang.String
toString()
-
-
-
Field Detail
-
DEFAULT_INITIAL_CAPACITY
public static final int DEFAULT_INITIAL_CAPACITY
The initial capacity used when none is specified in the constructor.- See Also:
- Constant Field Values
-
MISSING_VALUE
static final int MISSING_VALUE
- See Also:
- Constant Field Values
-
shouldAvoidAllocation
private final boolean shouldAvoidAllocation
-
containsMissingValue
private boolean containsMissingValue
-
loadFactor
private final float loadFactor
-
resizeThreshold
private int resizeThreshold
-
sizeOfArrayValues
private int sizeOfArrayValues
-
values
private int[] values
-
iterator
private IntHashSet.IntIterator iterator
-
-
Constructor Detail
-
IntHashSet
public IntHashSet()
Construct a hash set withDEFAULT_INITIAL_CAPACITY
,Hashing.DEFAULT_LOAD_FACTOR
, iterator caching support and0
as a missing value.
-
IntHashSet
public IntHashSet(int proposedCapacity)
Construct a hash set with a proposed capacity,Hashing.DEFAULT_LOAD_FACTOR
, iterator caching support and0
as a missing value.- Parameters:
proposedCapacity
- for the initial capacity of the set.
-
IntHashSet
public IntHashSet(int proposedCapacity, float loadFactor)
Construct a hash set with a proposed initial capacity, load factor, iterator caching support and0
as a missing value.- Parameters:
proposedCapacity
- for the initial capacity of the set.loadFactor
- to be used for resizing.
-
IntHashSet
public IntHashSet(int proposedCapacity, float loadFactor, boolean shouldAvoidAllocation)
Construct a hash set with a proposed initial capacity, load factor, iterator caching support and-1
as a missing value.- Parameters:
proposedCapacity
- for the initial capacity of the set.loadFactor
- to be used for resizing.shouldAvoidAllocation
- should the iterator be cached to avoid further allocation.
-
-
Method Detail
-
loadFactor
public float loadFactor()
Get the load factor beyond which the set will increase size.- Returns:
- load factor for when the set should increase size.
-
capacity
public int capacity()
Get the total capacity for the set to which the load factor with be a fraction of.- Returns:
- the total capacity for the set.
-
resizeThreshold
public int resizeThreshold()
Get the actual threshold which when reached the map will resize. This is a function of the current capacity and load factor.- Returns:
- the threshold when the map will resize.
-
add
public boolean add(java.lang.Integer value)
- Specified by:
add
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
add
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
add
in classjava.util.AbstractCollection<java.lang.Integer>
-
add
public boolean add(int value)
Primitive specialised overload of {this#add(Integer)}.- Parameters:
value
- the value to add.- Returns:
- true if the collection has changed, false otherwise.
-
increaseCapacity
private void increaseCapacity()
-
rehash
private void rehash(int newCapacity)
-
remove
public boolean remove(java.lang.Object value)
- Specified by:
remove
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
remove
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
remove
in classjava.util.AbstractCollection<java.lang.Integer>
-
remove
public boolean remove(int value)
Specialised version of {this#remove(Object)} for int.- Parameters:
value
- the value to remove.- Returns:
- true if the value was present, false otherwise.
-
next
private static int next(int index, int mask)
-
compactChain
void compactChain(int deleteIndex)
-
compact
public void compact()
Compact the backing arrays by rehashing with a capacity just larger than current size and giving consideration to the load factor.
-
contains
public boolean contains(java.lang.Object value)
- Specified by:
contains
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
contains
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
contains
in classjava.util.AbstractCollection<java.lang.Integer>
-
contains
public boolean contains(int value)
Contains method that does not box values.- Parameters:
value
- to be checked for if the set contains it.- Returns:
- true if the value is contained in the set otherwise false.
- See Also:
Collection.contains(Object)
-
size
public int size()
- Specified by:
size
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
size
in interfacejava.util.Set<java.lang.Integer>
- Specified by:
size
in classjava.util.AbstractCollection<java.lang.Integer>
-
isEmpty
public boolean isEmpty()
- Specified by:
isEmpty
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
isEmpty
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
isEmpty
in classjava.util.AbstractCollection<java.lang.Integer>
-
clear
public void clear()
- Specified by:
clear
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
clear
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
clear
in classjava.util.AbstractCollection<java.lang.Integer>
-
addAll
public boolean addAll(java.util.Collection<? extends java.lang.Integer> coll)
- Specified by:
addAll
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
addAll
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
addAll
in classjava.util.AbstractCollection<java.lang.Integer>
-
addAll
public boolean addAll(IntHashSet coll)
Alias foraddAll(Collection)
for the specialized case when adding another IntHashSet, avoids boxing and allocations.- Parameters:
coll
- containing the values to be added.- Returns:
true
if this set changed as a result of the call.
-
containsAll
public boolean containsAll(IntHashSet coll)
IntHashSet specialised variant of {this#containsAll(Collection)}.- Parameters:
coll
- int hash set to compare against.- Returns:
- true if every element in other is in this.
-
difference
public IntHashSet difference(IntHashSet other)
Fast Path set difference for comparison with another IntHashSet.Note: garbage free in the identical case, allocates otherwise.
- Parameters:
other
- the other set to subtract.- Returns:
- null if identical, otherwise the set of differences.
-
removeIf
public boolean removeIf(java.util.function.Predicate<? super java.lang.Integer> filter)
-
removeIfInt
public boolean removeIfInt(java.util.function.IntPredicate filter)
Removes all the elements of this collection that satisfy the given predicate.NB: Renamed from removeIf to avoid overloading on parameter types of lambda expression, which doesn't play well with type inference in lambda expressions.
- Parameters:
filter
- which returnstrue
for elements to be removed.- Returns:
true
if any elements were removed.
-
removeAll
public boolean removeAll(java.util.Collection<?> coll)
- Specified by:
removeAll
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
removeAll
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
removeAll
in classjava.util.AbstractSet<java.lang.Integer>
-
removeAll
public boolean removeAll(IntHashSet coll)
Alias forremoveAll(Collection)
for the specialized case when removing another IntHashSet, avoids boxing and allocations.- Parameters:
coll
- containing the values to be removed.- Returns:
true
if this set changed as a result of the call.
-
retainAll
public boolean retainAll(java.util.Collection<?> coll)
- Specified by:
retainAll
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
retainAll
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
retainAll
in classjava.util.AbstractCollection<java.lang.Integer>
-
retainAll
public boolean retainAll(IntHashSet coll)
Alias forretainAll(Collection)
for the specialized case when retaining on another IntHashSet, avoids boxing and allocations.- Parameters:
coll
- containing elements to be retained in this set.- Returns:
true
if this set changed as a result of the call.
-
iterator
public IntHashSet.IntIterator iterator()
- Specified by:
iterator
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
iterator
in interfacejava.lang.Iterable<java.lang.Integer>
- Specified by:
iterator
in interfacejava.util.Set<java.lang.Integer>
- Specified by:
iterator
in classjava.util.AbstractCollection<java.lang.Integer>
-
forEachInt
public void forEachInt(java.util.function.IntConsumer action)
Iterate over the collection without boxing.- Parameters:
action
- to be taken for each element.
-
copy
public void copy(IntHashSet that)
Copy values from anotherIntHashSet
into this one.- Parameters:
that
- set to copy values from.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.util.AbstractCollection<java.lang.Integer>
-
toArray
public <T> T[] toArray(T[] a)
- Specified by:
toArray
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
toArray
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
toArray
in classjava.util.AbstractCollection<java.lang.Integer>
-
toArray
public java.lang.Object[] toArray()
- Specified by:
toArray
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
toArray
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
toArray
in classjava.util.AbstractCollection<java.lang.Integer>
-
copyValues
private void copyValues(java.lang.Object[] arrayCopy)
-
equals
public boolean equals(java.lang.Object other)
- Specified by:
equals
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
equals
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
equals
in classjava.util.AbstractSet<java.lang.Integer>
-
hashCode
public int hashCode()
- Specified by:
hashCode
in interfacejava.util.Collection<java.lang.Integer>
- Specified by:
hashCode
in interfacejava.util.Set<java.lang.Integer>
- Overrides:
hashCode
in classjava.util.AbstractSet<java.lang.Integer>
-
-