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, trimToSize
private 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)
CompactHashSet
init
in class CompactHashSet<E>
int allocArrays()
CompactHashSet
allocArrays
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)
CompactHashSet
insertEntry
in class CompactHashSet<E>
void moveLastEntry(int dstIndex, int mask)
CompactHashSet
dstIndex
, and nulls out its old position.moveLastEntry
in class CompactHashSet<E>
void resizeEntries(int newCapacity)
CompactHashSet
resizeEntries
in class CompactHashSet<E>
int firstEntryIndex()
firstEntryIndex
in class CompactHashSet<E>
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
CompactHashSet
adjustAfterRemove
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()