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
Pointer to the first node in the linked list, or
ENDPOINT if there are no entries. |
private int |
lastEntry
Pointer to the last node in the linked list, or
ENDPOINT if there are no entries. |
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, HASH_FLOODING_FPP| 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.
|
(package private) int |
allocArrays()
Handle lazy allocation of arrays.
|
void |
clear() |
(package private) java.util.Set<E> |
convertToHashFloodingResistantImplementation() |
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() |
private int |
getPredecessor(int entry) |
(package private) int |
getSuccessor(int entry) |
(package private) void |
init(int expectedSize)
Pseudoconstructor for serialization support.
|
(package private) void |
insertEntry(int entryIndex,
E object,
int hash,
int mask)
Creates a fresh entry with the specified object at the specified position in the entry arrays.
|
(package private) void |
moveLastEntry(int dstIndex,
int mask)
Moves the last entry in the entry array into
dstIndex, and nulls out its old position. |
private int[] |
requirePredecessors() |
private int[] |
requireSuccessors() |
(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.
|
private void |
setPredecessor(int entry,
int pred) |
private void |
setSucceeds(int pred,
int succ) |
private void |
setSuccessor(int entry,
int succ) |
java.util.Spliterator<E> |
spliterator() |
java.lang.Object[] |
toArray() |
<T> T[] |
toArray(T[] a) |
add, contains, delegateOrNull, forEach, incrementModCount, isEmpty, isUsingHashFloodingResistance, iterator, needsAllocArrays, remove, size, trimToSizeprivate static final int ENDPOINT
@CheckForNull private transient int[] predecessor
CompactHashSet.size() are UNSET.@CheckForNull private transient int[] successor
CompactHashSet.size() are UNSET.private transient int firstEntry
ENDPOINT if there are no entries.private transient int lastEntry
ENDPOINT if there are no entries.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)@SafeVarargs 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)
CompactHashSetinit in class CompactHashSet<E>int allocArrays()
CompactHashSetallocArrays in class CompactHashSet<E>java.util.Set<E> convertToHashFloodingResistantImplementation()
convertToHashFloodingResistantImplementation in class CompactHashSet<E>private int getPredecessor(int entry)
int getSuccessor(int entry)
getSuccessor in class CompactHashSet<E>private void setSuccessor(int entry,
int succ)
private void setPredecessor(int entry,
int pred)
private void setSucceeds(int pred,
int succ)
void insertEntry(int entryIndex,
E object,
int hash,
int mask)
CompactHashSetinsertEntry in class CompactHashSet<E>void moveLastEntry(int dstIndex,
int mask)
CompactHashSetdstIndex, and nulls out its old position.moveLastEntry in class CompactHashSet<E>void resizeEntries(int newCapacity)
CompactHashSetresizeEntries in class CompactHashSet<E>int firstEntryIndex()
firstEntryIndex in class CompactHashSet<E>int adjustAfterRemove(int indexBeforeRemove,
int indexRemoved)
CompactHashSetadjustAfterRemove 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>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 clear()
clear in interface java.util.Collection<E>clear in interface java.util.Set<E>clear in class CompactHashSet<E>private int[] requirePredecessors()
private int[] requireSuccessors()