Package org.agrona.collections
Class LongHashSet
Open-addressing with linear-probing expandable hash set. Allocation free in steady state use when expanded.
By storing elements as long primitives this significantly reduces memory consumption compared with Java's builtin
HashSet<Long>
. It implements Set<Long>
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionfinal class
Iterator which supports unboxed access to the values viaLongHashSet.LongIterator.nextValue()
. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate boolean
static final int
The initial capacity used when none is specified in the constructor.private LongHashSet.LongIterator
private final float
(package private) static final long
private int
private final boolean
private int
private long[]
-
Constructor Summary
ConstructorsConstructorDescriptionConstruct a hash set withDEFAULT_INITIAL_CAPACITY
,Hashing.DEFAULT_LOAD_FACTOR
, iterator caching support and0
as a missing value.LongHashSet
(int proposedCapacity) Construct a hash set with a proposed capacity,Hashing.DEFAULT_LOAD_FACTOR
, iterator caching support and0
as a missing value.LongHashSet
(int proposedCapacity, float loadFactor) Construct a hash set with a proposed initial capacity, load factor, iterator caching support and0
as a missing value.LongHashSet
(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
Modifier and TypeMethodDescriptionboolean
add
(long value) Primitive specialised overload of {this#add(Long)}.boolean
boolean
addAll
(Collection<? extends Long> coll) boolean
addAll
(LongHashSet coll) Alias foraddAll(Collection)
for the specialized case when adding another LongHashSet, 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
(long value) Contains method that does not box values.boolean
boolean
containsAll
(LongHashSet coll) LongHashSet specialised variant of {this#containsAll(Collection)}.void
copy
(LongHashSet that) Copy values from anotherLongHashSet
longo this one.private void
copyValues
(Object[] arrayCopy) difference
(LongHashSet other) Fast Path set difference for comparison with another LongHashSet.boolean
void
forEachLong
(LongConsumer action) Iterate over the collection without boxing.int
hashCode()
private void
boolean
isEmpty()
iterator()
float
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
(long value) Specialised version of {this#remove(Object)} for long.boolean
boolean
removeAll
(Collection<?> coll) boolean
removeAll
(LongHashSet coll) Alias forremoveAll(Collection)
for the specialized case when removing another LongHashSet, avoids boxing and allocations.boolean
boolean
removeIfLong
(LongPredicate filter) Removes all the elements of this collection that satisfy the given predicate.int
Get the actual threshold which when reached the map will resize.boolean
retainAll
(Collection<?> coll) boolean
retainAll
(LongHashSet coll) Alias forretainAll(Collection)
for the specialized case when retaining on another LongHashSet, avoids boxing and allocations.int
size()
Object[]
toArray()
<T> T[]
toArray
(T[] a) toString()
Methods inherited from class java.util.AbstractCollection
containsAll
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, stream, toArray
Methods inherited from interface java.util.Set
containsAll, spliterator
-
Field Details
-
DEFAULT_INITIAL_CAPACITY
public static final int DEFAULT_INITIAL_CAPACITYThe initial capacity used when none is specified in the constructor.- See Also:
-
MISSING_VALUE
static final long MISSING_VALUE- See Also:
-
shouldAvoidAllocation
private final boolean shouldAvoidAllocation -
containsMissingValue
private boolean containsMissingValue -
loadFactor
private final float loadFactor -
resizeThreshold
private int resizeThreshold -
sizeOfArrayValues
private int sizeOfArrayValues -
values
private long[] values -
iterator
-
-
Constructor Details
-
LongHashSet
public LongHashSet()Construct a hash set withDEFAULT_INITIAL_CAPACITY
,Hashing.DEFAULT_LOAD_FACTOR
, iterator caching support and0
as a missing value. -
LongHashSet
public LongHashSet(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.
-
LongHashSet
public LongHashSet(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.
-
LongHashSet
public LongHashSet(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 Details
-
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
- Specified by:
add
in interfaceCollection<Long>
- Specified by:
add
in interfaceSet<Long>
- Overrides:
add
in classAbstractCollection<Long>
-
add
public boolean add(long value) Primitive specialised overload of {this#add(Long)}.- 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
- Specified by:
remove
in interfaceCollection<Long>
- Specified by:
remove
in interfaceSet<Long>
- Overrides:
remove
in classAbstractCollection<Long>
-
remove
public boolean remove(long value) Specialised version of {this#remove(Object)} for long.- 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
- Specified by:
contains
in interfaceCollection<Long>
- Specified by:
contains
in interfaceSet<Long>
- Overrides:
contains
in classAbstractCollection<Long>
-
contains
public boolean contains(long 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:
-
size
public int size()- Specified by:
size
in interfaceCollection<Long>
- Specified by:
size
in interfaceSet<Long>
- Specified by:
size
in classAbstractCollection<Long>
-
isEmpty
public boolean isEmpty()- Specified by:
isEmpty
in interfaceCollection<Long>
- Specified by:
isEmpty
in interfaceSet<Long>
- Overrides:
isEmpty
in classAbstractCollection<Long>
-
clear
public void clear()- Specified by:
clear
in interfaceCollection<Long>
- Specified by:
clear
in interfaceSet<Long>
- Overrides:
clear
in classAbstractCollection<Long>
-
addAll
- Specified by:
addAll
in interfaceCollection<Long>
- Specified by:
addAll
in interfaceSet<Long>
- Overrides:
addAll
in classAbstractCollection<Long>
-
addAll
Alias foraddAll(Collection)
for the specialized case when adding another LongHashSet, 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
LongHashSet specialised variant of {this#containsAll(Collection)}.- Parameters:
coll
- long hash set to compare against.- Returns:
- true if every element in other is in this.
-
difference
Fast Path set difference for comparison with another LongHashSet.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
-
removeIfLong
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
- Specified by:
removeAll
in interfaceCollection<Long>
- Specified by:
removeAll
in interfaceSet<Long>
- Overrides:
removeAll
in classAbstractSet<Long>
-
removeAll
Alias forremoveAll(Collection)
for the specialized case when removing another LongHashSet, 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
- Specified by:
retainAll
in interfaceCollection<Long>
- Specified by:
retainAll
in interfaceSet<Long>
- Overrides:
retainAll
in classAbstractCollection<Long>
-
retainAll
Alias forretainAll(Collection)
for the specialized case when retaining on another LongHashSet, 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
-
forEachLong
Iterate over the collection without boxing.- Parameters:
action
- to be taken for each element.
-
copy
Copy values from anotherLongHashSet
longo this one.- Parameters:
that
- set to copy values from.
-
toString
- Overrides:
toString
in classAbstractCollection<Long>
-
toArray
public <T> T[] toArray(T[] a) - Specified by:
toArray
in interfaceCollection<Long>
- Specified by:
toArray
in interfaceSet<Long>
- Overrides:
toArray
in classAbstractCollection<Long>
-
toArray
- Specified by:
toArray
in interfaceCollection<Long>
- Specified by:
toArray
in interfaceSet<Long>
- Overrides:
toArray
in classAbstractCollection<Long>
-
copyValues
-
equals
- Specified by:
equals
in interfaceCollection<Long>
- Specified by:
equals
in interfaceSet<Long>
- Overrides:
equals
in classAbstractSet<Long>
-
hashCode
public int hashCode()- Specified by:
hashCode
in interfaceCollection<Long>
- Specified by:
hashCode
in interfaceSet<Long>
- Overrides:
hashCode
in classAbstractSet<Long>
-