Class CompactLinkedHashSet<E>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractSet<E>
-
- com.google.common.collect.CompactHashSet<E>
-
- com.google.common.collect.CompactLinkedHashSet<E>
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Iterable<E>
,java.util.Collection<E>
,java.util.Set<E>
@GwtIncompatible class CompactLinkedHashSet<E> extends CompactHashSet<E>
CompactLinkedHashSet is an implementation of a Set, which a predictable iteration order that matches the insertion order. All optional operations (adding and removing) are supported. All elements, includingnull
, are permitted.contains(x)
,add(x)
andremove(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 evenjava.util.HashSet
, and places considerably less load on the garbage collector. Likejava.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
Fields Modifier and Type Field 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.-
Fields inherited from class com.google.common.collect.CompactHashSet
elements, loadFactor, modCount, UNSET
-
-
Constructor Summary
Constructors Constructor Description CompactLinkedHashSet()
CompactLinkedHashSet(int expectedSize)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 emptyCompactLinkedHashSet
instance.static <E> CompactLinkedHashSet<E>
create(E... elements)
Creates aCompactLinkedHashSet
instance containing the given elements in unspecified order.static <E> CompactLinkedHashSet<E>
create(java.util.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
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 intodstIndex
, 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)
-
Methods inherited from class com.google.common.collect.CompactHashSet
add, contains, isEmpty, iterator, remove, size, trimToSize
-
-
-
-
Field Detail
-
ENDPOINT
private static final int ENDPOINT
- See Also:
- Constant Field Values
-
predecessor
private transient int[] predecessor
Pointer 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
private transient int[] successor
Pointer 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 firstEntry
-
lastEntry
private transient int lastEntry
-
-
Method Detail
-
create
public static <E> CompactLinkedHashSet<E> create()
Creates an emptyCompactLinkedHashSet
instance.
-
create
public static <E> CompactLinkedHashSet<E> create(java.util.Collection<? extends E> collection)
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
public static <E> CompactLinkedHashSet<E> create(E... elements)
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
public 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.- 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:
java.lang.IllegalArgumentException
- ifexpectedSize
is negative
-
init
void init(int expectedSize, float loadFactor)
Description copied from class:CompactHashSet
Pseudoconstructor for serialization support.- Overrides:
init
in classCompactHashSet<E>
-
succeeds
private void succeeds(int pred, int succ)
-
insertEntry
void insertEntry(int entryIndex, E object, int hash)
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>
-
moveEntry
void moveEntry(int dstIndex)
Description copied from class:CompactHashSet
Moves the last entry in the entry array intodstIndex
, and nulls out its old position.- Overrides:
moveEntry
in classCompactHashSet<E>
-
clear
public void clear()
- Specified by:
clear
in interfacejava.util.Collection<E>
- Specified by:
clear
in interfacejava.util.Set<E>
- Overrides:
clear
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>
-
toArray
public java.lang.Object[] toArray()
- Specified by:
toArray
in interfacejava.util.Collection<E>
- Specified by:
toArray
in interfacejava.util.Set<E>
- Overrides:
toArray
in classCompactHashSet<E>
-
toArray
public <T> T[] toArray(T[] a)
- Specified by:
toArray
in interfacejava.util.Collection<E>
- Specified by:
toArray
in interfacejava.util.Set<E>
- Overrides:
toArray
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>
-
getSuccessor
int getSuccessor(int entryIndex)
- Overrides:
getSuccessor
in classCompactHashSet<E>
-
spliterator
public java.util.Spliterator<E> spliterator()
- Specified by:
spliterator
in interfacejava.util.Collection<E>
- Specified by:
spliterator
in interfacejava.lang.Iterable<E>
- Specified by:
spliterator
in interfacejava.util.Set<E>
- Overrides:
spliterator
in classCompactHashSet<E>
-
forEach
public void forEach(java.util.function.Consumer<? super E> action)
- Specified by:
forEach
in interfacejava.lang.Iterable<E>
- Overrides:
forEach
in classCompactHashSet<E>
-
-