@GwtIncompatible class CompactLinkedHashSet<E> extends CompactHashSet<E>
null
, are permitted.
contains(x)
, add(x)
and remove(x)
, are all (expected and amortized)
constant time operations. Expected in the hashtable sense (depends on the hash function doing a
good job of distributing the elements to the buckets to a distribution not far from uniform), and
amortized since some operations can trigger a hash table resize.
This implementation consumes significantly less memory than java.util.LinkedHashSet
or
even java.util.HashSet
, and places considerably less load on the garbage collector. Like
java.util.LinkedHashSet
, it offers insertion-order iteration, with identical behavior.
This class should not be assumed to be universally superior to java.util.LinkedHashSet
. Generally speaking, this class reduces object allocation and memory
consumption at the price of moderately increased constant factors of CPU. Only use this class
when there is a specific reason to prioritize memory over CPU.
Modifier and Type | Field and Description |
---|---|
private static int |
ENDPOINT |
private int |
firstEntry |
private int |
lastEntry |
private int[] |
predecessor
Pointer to the predecessor of an entry in insertion order.
|
private int[] |
successor
Pointer to the successor of an entry in insertion order.
|
elements, loadFactor, modCount, UNSET
Constructor and Description |
---|
CompactLinkedHashSet() |
CompactLinkedHashSet(int expectedSize) |
Modifier and Type | Method and Description |
---|---|
(package private) int |
adjustAfterRemove(int indexBeforeRemove,
int indexRemoved)
Updates the index an iterator is pointing to after a call to remove: returns the index of the
entry that should be looked at after a removal on indexRemoved, with indexBeforeRemove as the
index that *was* the next entry that would be looked at.
|
void |
clear() |
static <E> CompactLinkedHashSet<E> |
create()
Creates an empty
CompactLinkedHashSet instance. |
static <E> CompactLinkedHashSet<E> |
create(java.util.Collection<? extends E> collection)
Creates a mutable
CompactLinkedHashSet instance containing the elements
of the given collection in the order returned by the collection's iterator. |
static <E> CompactLinkedHashSet<E> |
create(E... elements)
Creates a
CompactLinkedHashSet instance containing the given elements in
unspecified order. |
static <E> CompactLinkedHashSet<E> |
createWithExpectedSize(int expectedSize)
Creates a
CompactLinkedHashSet instance, with a high enough "initial capacity"
that it should hold expectedSize elements without rebuilding internal
data structures. |
(package private) int |
firstEntryIndex() |
void |
forEach(java.util.function.Consumer<? super E> action) |
(package private) int |
getSuccessor(int entryIndex) |
(package private) void |
init(int expectedSize,
float loadFactor)
Pseudoconstructor for serialization support.
|
(package private) void |
insertEntry(int entryIndex,
E object,
int hash)
Creates a fresh entry with the specified object at the specified position in the entry arrays.
|
(package private) void |
moveEntry(int dstIndex)
Moves the last entry in the entry array into
dstIndex , and nulls out its old position. |
(package private) void |
resizeEntries(int newCapacity)
Resizes the internal entries array to the specified capacity, which may be greater or less than
the current capacity.
|
java.util.Spliterator<E> |
spliterator() |
private void |
succeeds(int pred,
int succ) |
java.lang.Object[] |
toArray() |
<T> T[] |
toArray(T[] a) |
add, contains, isEmpty, iterator, remove, size, trimToSize
private static final int ENDPOINT
private transient int[] predecessor
CompactHashSet.size()
are UNSET.private transient int[] successor
CompactHashSet.size()
are UNSET.private transient int firstEntry
private transient int lastEntry
CompactLinkedHashSet()
CompactLinkedHashSet(int expectedSize)
public static <E> CompactLinkedHashSet<E> create()
CompactLinkedHashSet
instance.public static <E> CompactLinkedHashSet<E> create(java.util.Collection<? extends E> collection)
CompactLinkedHashSet
instance containing the elements
of the given collection in the order returned by the collection's iterator.collection
- the elements that the set should containCompactLinkedHashSet
containing those elements (minus duplicates)public static <E> CompactLinkedHashSet<E> create(E... elements)
CompactLinkedHashSet
instance containing the given elements in
unspecified order.elements
- the elements that the set should containCompactLinkedHashSet
containing those elements (minus duplicates)public static <E> CompactLinkedHashSet<E> createWithExpectedSize(int expectedSize)
CompactLinkedHashSet
instance, with a high enough "initial capacity"
that it should hold expectedSize
elements without rebuilding internal
data structures.expectedSize
- the number of elements you expect to add to the returned setCompactLinkedHashSet
with enough capacity to hold expectedSize
elements without resizingjava.lang.IllegalArgumentException
- if expectedSize
is negativevoid init(int expectedSize, float loadFactor)
CompactHashSet
init
in class CompactHashSet<E>
private void succeeds(int pred, int succ)
void insertEntry(int entryIndex, E object, int hash)
CompactHashSet
insertEntry
in class CompactHashSet<E>
void moveEntry(int dstIndex)
CompactHashSet
dstIndex
, and nulls out its old position.moveEntry
in class CompactHashSet<E>
public void clear()
clear
in interface java.util.Collection<E>
clear
in interface java.util.Set<E>
clear
in class CompactHashSet<E>
void resizeEntries(int newCapacity)
CompactHashSet
resizeEntries
in class CompactHashSet<E>
public java.lang.Object[] toArray()
toArray
in interface java.util.Collection<E>
toArray
in interface java.util.Set<E>
toArray
in class CompactHashSet<E>
public <T> T[] toArray(T[] a)
toArray
in interface java.util.Collection<E>
toArray
in interface java.util.Set<E>
toArray
in class CompactHashSet<E>
int firstEntryIndex()
firstEntryIndex
in class CompactHashSet<E>
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
CompactHashSet
adjustAfterRemove
in class CompactHashSet<E>
int getSuccessor(int entryIndex)
getSuccessor
in class CompactHashSet<E>
public java.util.Spliterator<E> spliterator()
spliterator
in interface java.lang.Iterable<E>
spliterator
in interface java.util.Collection<E>
spliterator
in interface java.util.Set<E>
spliterator
in class CompactHashSet<E>
public void forEach(java.util.function.Consumer<? super E> action)
forEach
in interface java.lang.Iterable<E>
forEach
in class CompactHashSet<E>