Class CompactLinkedHashSet<E>
- All Implemented Interfaces:
Serializable,Iterable<E>,Collection<E>,Set<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.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final intprivate intPointer to the first node in the linked list, orENDPOINTif there are no entries.private intPointer to the last node in the linked list, orENDPOINTif there are no entries.private int[]Pointer to the predecessor of an entry in insertion order.private int[]Pointer to the successor of an entry in insertion order.Fields inherited from class com.google.common.collect.CompactHashSet
elements, HASH_FLOODING_FPP -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) intadjustAfterRemove(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) intHandle lazy allocation of arrays.voidclear()static <E> CompactLinkedHashSet<E> create()Creates an emptyCompactLinkedHashSetinstance.static <E> CompactLinkedHashSet<E> create(E... elements) Creates aCompactLinkedHashSetinstance containing the given elements in unspecified order.static <E> CompactLinkedHashSet<E> create(Collection<? extends E> collection) Creates a mutableCompactLinkedHashSetinstance containing the elements of the given collection in the order returned by the collection's iterator.static <E> CompactLinkedHashSet<E> createWithExpectedSize(int expectedSize) Creates aCompactLinkedHashSetinstance, with a high enough "initial capacity" that it should holdexpectedSizeelements without rebuilding internal data structures.(package private) intprivate intgetPredecessor(int entry) (package private) intgetSuccessor(int entry) (package private) voidinit(int expectedSize) Pseudoconstructor for serialization support.(package private) voidinsertEntry(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) voidmoveLastEntry(int dstIndex, int mask) Moves the last entry in the entry array intodstIndex, and nulls out its old position.private int[]private int[](package private) voidresizeEntries(int newCapacity) Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.private voidsetPredecessor(int entry, int pred) private voidsetSucceeds(int pred, int succ) private voidsetSuccessor(int entry, int succ) Object[]toArray()<T> T[]toArray(T[] a) Methods inherited from class com.google.common.collect.CompactHashSet
add, contains, delegateOrNull, forEach, incrementModCount, isEmpty, isUsingHashFloodingResistance, iterator, needsAllocArrays, remove, size, trimToSizeMethods inherited from class java.util.AbstractSet
equals, hashCode, removeAllMethods inherited from class java.util.AbstractCollection
addAll, containsAll, retainAll, toStringMethods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, waitMethods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArrayMethods inherited from interface java.util.Set
addAll, containsAll, retainAll
-
Field Details
-
ENDPOINT
private static final int ENDPOINT- See Also:
-
predecessor
@CheckForNull private transient int[] predecessorPointer to the predecessor of an entry in insertion order. ENDPOINT indicates a node is the first node in insertion order; all values at indices ≥CompactHashSet.size()are UNSET. -
successor
@CheckForNull private transient int[] successorPointer to the successor of an entry in insertion order. ENDPOINT indicates a node is the last node in insertion order; all values at indices ≥CompactHashSet.size()are UNSET. -
firstEntry
private transient int firstEntryPointer to the first node in the linked list, orENDPOINTif there are no entries. -
lastEntry
private transient int lastEntryPointer to the last node in the linked list, orENDPOINTif there are no entries.
-
-
Constructor Details
-
CompactLinkedHashSet
CompactLinkedHashSet() -
CompactLinkedHashSet
CompactLinkedHashSet(int expectedSize)
-
-
Method Details
-
create
Creates an emptyCompactLinkedHashSetinstance. -
create
Creates a mutableCompactLinkedHashSetinstance containing the elements of the given collection in the order returned by the collection's iterator.- Parameters:
collection- the elements that the set should contain- Returns:
- a new
CompactLinkedHashSetcontaining those elements (minus duplicates)
-
create
Creates aCompactLinkedHashSetinstance containing the given elements in unspecified order.- Parameters:
elements- the elements that the set should contain- Returns:
- a new
CompactLinkedHashSetcontaining those elements (minus duplicates)
-
createWithExpectedSize
Creates aCompactLinkedHashSetinstance, with a high enough "initial capacity" that it should holdexpectedSizeelements without rebuilding internal data structures.- Parameters:
expectedSize- the number of elements you expect to add to the returned set- Returns:
- a new, empty
CompactLinkedHashSetwith enough capacity to holdexpectedSizeelements without resizing - Throws:
IllegalArgumentException- ifexpectedSizeis negative
-
init
void init(int expectedSize) Description copied from class:CompactHashSetPseudoconstructor for serialization support.- Overrides:
initin classCompactHashSet<E>
-
allocArrays
int allocArrays()Description copied from class:CompactHashSetHandle lazy allocation of arrays.- Overrides:
allocArraysin classCompactHashSet<E>
-
convertToHashFloodingResistantImplementation
- Overrides:
convertToHashFloodingResistantImplementationin classCompactHashSet<E>
-
getPredecessor
private int getPredecessor(int entry) -
getSuccessor
int getSuccessor(int entry) - Overrides:
getSuccessorin classCompactHashSet<E>
-
setSuccessor
private void setSuccessor(int entry, int succ) -
setPredecessor
private void setPredecessor(int entry, int pred) -
setSucceeds
private void setSucceeds(int pred, int succ) -
insertEntry
Description copied from class:CompactHashSetCreates a fresh entry with the specified object at the specified position in the entry arrays.- Overrides:
insertEntryin classCompactHashSet<E>
-
moveLastEntry
void moveLastEntry(int dstIndex, int mask) Description copied from class:CompactHashSetMoves the last entry in the entry array intodstIndex, and nulls out its old position.- Overrides:
moveLastEntryin classCompactHashSet<E>
-
resizeEntries
void resizeEntries(int newCapacity) Description copied from class:CompactHashSetResizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.- Overrides:
resizeEntriesin classCompactHashSet<E>
-
firstEntryIndex
int firstEntryIndex()- Overrides:
firstEntryIndexin classCompactHashSet<E>
-
adjustAfterRemove
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved) Description copied from class:CompactHashSetUpdates 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.- Overrides:
adjustAfterRemovein classCompactHashSet<E>
-
toArray
- Specified by:
toArrayin interfaceCollection<E>- Specified by:
toArrayin interfaceSet<E>- Overrides:
toArrayin classCompactHashSet<E>
-
toArray
public <T> T[] toArray(T[] a) - Specified by:
toArrayin interfaceCollection<E>- Specified by:
toArrayin interfaceSet<E>- Overrides:
toArrayin classCompactHashSet<E>
-
spliterator
- Specified by:
spliteratorin interfaceCollection<E>- Specified by:
spliteratorin interfaceIterable<E>- Specified by:
spliteratorin interfaceSet<E>- Overrides:
spliteratorin classCompactHashSet<E>
-
clear
public void clear()- Specified by:
clearin interfaceCollection<E>- Specified by:
clearin interfaceSet<E>- Overrides:
clearin classCompactHashSet<E>
-
requirePredecessors
private int[] requirePredecessors() -
requireSuccessors
private int[] requireSuccessors()
-