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 int
private int
Pointer to the first node in the linked list, orENDPOINT
if there are no entries.private int
Pointer to the last node in the linked list, orENDPOINT
if 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) 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
Handle lazy allocation of arrays.void
clear()
static <E> CompactLinkedHashSet
<E> create()
Creates an emptyCompactLinkedHashSet
instance.static <E> CompactLinkedHashSet
<E> create
(E... elements) Creates aCompactLinkedHashSet
instance containing the given elements in unspecified order.static <E> CompactLinkedHashSet
<E> create
(Collection<? extends E> collection) Creates a mutableCompactLinkedHashSet
instance containing the elements of the given collection in the order returned by the collection's iterator.static <E> CompactLinkedHashSet
<E> createWithExpectedSize
(int expectedSize) Creates aCompactLinkedHashSet
instance, with a high enough "initial capacity" that it should holdexpectedSize
elements without rebuilding internal data structures.(package private) int
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 intodstIndex
, and nulls out its old position.private int[]
private int[]
(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) 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, trimToSize
Methods inherited from class java.util.AbstractSet
equals, hashCode, removeAll
Methods inherited from class java.util.AbstractCollection
addAll, containsAll, retainAll, toString
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray
Methods 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, orENDPOINT
if there are no entries. -
lastEntry
private transient int lastEntryPointer to the last node in the linked list, orENDPOINT
if there are no entries.
-
-
Constructor Details
-
CompactLinkedHashSet
CompactLinkedHashSet() -
CompactLinkedHashSet
CompactLinkedHashSet(int expectedSize)
-
-
Method Details
-
create
Creates an emptyCompactLinkedHashSet
instance. -
create
Creates a mutableCompactLinkedHashSet
instance 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
CompactLinkedHashSet
containing those elements (minus duplicates)
-
create
Creates aCompactLinkedHashSet
instance containing the given elements in unspecified order.- Parameters:
elements
- the elements that the set should contain- Returns:
- a new
CompactLinkedHashSet
containing those elements (minus duplicates)
-
createWithExpectedSize
Creates aCompactLinkedHashSet
instance, with a high enough "initial capacity" that it should holdexpectedSize
elements without rebuilding internal data structures.- Parameters:
expectedSize
- the number of elements you expect to add to the returned set- Returns:
- a new, empty
CompactLinkedHashSet
with enough capacity to holdexpectedSize
elements without resizing - Throws:
IllegalArgumentException
- ifexpectedSize
is negative
-
init
void init(int expectedSize) Description copied from class:CompactHashSet
Pseudoconstructor for serialization support.- Overrides:
init
in classCompactHashSet<E>
-
allocArrays
int allocArrays()Description copied from class:CompactHashSet
Handle lazy allocation of arrays.- Overrides:
allocArrays
in classCompactHashSet<E>
-
convertToHashFloodingResistantImplementation
- Overrides:
convertToHashFloodingResistantImplementation
in classCompactHashSet<E>
-
getPredecessor
private int getPredecessor(int entry) -
getSuccessor
int getSuccessor(int entry) - Overrides:
getSuccessor
in 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:CompactHashSet
Creates a fresh entry with the specified object at the specified position in the entry arrays.- Overrides:
insertEntry
in classCompactHashSet<E>
-
moveLastEntry
void moveLastEntry(int dstIndex, int mask) Description copied from class:CompactHashSet
Moves the last entry in the entry array intodstIndex
, and nulls out its old position.- Overrides:
moveLastEntry
in classCompactHashSet<E>
-
resizeEntries
void resizeEntries(int newCapacity) Description copied from class:CompactHashSet
Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.- Overrides:
resizeEntries
in classCompactHashSet<E>
-
firstEntryIndex
int firstEntryIndex()- Overrides:
firstEntryIndex
in classCompactHashSet<E>
-
adjustAfterRemove
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved) Description copied from class:CompactHashSet
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.- Overrides:
adjustAfterRemove
in classCompactHashSet<E>
-
toArray
- Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfaceSet<E>
- Overrides:
toArray
in classCompactHashSet<E>
-
toArray
public <T> T[] toArray(T[] a) - Specified by:
toArray
in interfaceCollection<E>
- Specified by:
toArray
in interfaceSet<E>
- Overrides:
toArray
in classCompactHashSet<E>
-
spliterator
- Specified by:
spliterator
in interfaceCollection<E>
- Specified by:
spliterator
in interfaceIterable<E>
- Specified by:
spliterator
in interfaceSet<E>
- Overrides:
spliterator
in classCompactHashSet<E>
-
clear
public void clear()- Specified by:
clear
in interfaceCollection<E>
- Specified by:
clear
in interfaceSet<E>
- Overrides:
clear
in classCompactHashSet<E>
-
requirePredecessors
private int[] requirePredecessors() -
requireSuccessors
private int[] requireSuccessors()
-