Top Description Fields Constructors Methods
com.google.common.collect

pack-priv Class CompactLinkedHashSet<E extends @Nullable Object>

extends CompactHashSet<E extends @Nullable Object>
Class Inheritance
Annotations
@GwtIncompatible
@ElementTypesAreNonnullByDefault
Static Imports
java.util.Objects.requireNonNull
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, including 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.

Author
Louis Wasserman

Field Summary

Modifier and TypeField and Description
private static final int
ENDPOINT

private transient int
firstEntry

Pointer to the first node in the linked list, or ENDPOINT if there are no entries.

private transient int
lastEntry

Pointer to the last node in the linked list, or ENDPOINT if there are no entries.

private transient int[]
predecessor

Pointer to the predecessor of an entry in insertion order.

private transient int[]
successor

Pointer to the successor of an entry in insertion order.

Inherited from com.google.common.collect.CompactHashSet:
elementsHASH_FLOODING_FPP

Constructor Summary

AccessConstructor and Description
pack-priv
CompactLinkedHashSet()

pack-priv
CompactLinkedHashSet(int expectedSize)

Method Summary

Modifier and TypeMethod and Description
pack-priv int
adjustAfterRemove(int indexBeforeRemove, int indexRemoved)

Overrides com.google.common.collect.CompactHashSet.adjustAfterRemove.

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.
pack-priv int
allocArrays()

Overrides com.google.common.collect.CompactHashSet.allocArrays.

Handle lazy allocation of arrays.
public void
clear()

Overrides com.google.common.collect.CompactHashSet.clear.

Implements java.util.Set.clear, java.util.Collection.clear.

Removes all of the elements from this set (optional operation).
pack-priv Set<E>
convertToHashFloodingResistantImplementation()

Overrides com.google.common.collect.CompactHashSet.convertToHashFloodingResistantImplementation.

public static <E extends @Nullable Object> CompactLinkedHashSet<E>
create()

Hides com.google.common.collect.CompactHashSet.create.

Creates an empty CompactLinkedHashSet instance.
public static <E extends @Nullable Object> CompactLinkedHashSet<E>

Returns:

a new CompactLinkedHashSet containing those elements (minus duplicates)
create(Collection<? extends E>
the elements that the set should contain
collection)

Hides com.google.common.collect.CompactHashSet.create.

Creates a mutable CompactLinkedHashSet instance containing the elements of the given collection in the order returned by the collection's iterator.
public static <E extends @Nullable Object> CompactLinkedHashSet<E>

Returns:

a new CompactLinkedHashSet containing those elements (minus duplicates)
create(E...
the elements that the set should contain
elements)

Hides com.google.common.collect.CompactHashSet.create.

Creates a CompactLinkedHashSet instance containing the given elements in unspecified order.
public static <E extends @Nullable Object> CompactLinkedHashSet<E>

Returns:

a new, empty CompactLinkedHashSet with enough capacity to hold expectedSize elements without resizing
createWithExpectedSize(int
the number of elements you expect to add to the returned set
expectedSize)

Hides com.google.common.collect.CompactHashSet.createWithExpectedSize.

Creates a CompactLinkedHashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without rebuilding internal data structures.
pack-priv int
firstEntryIndex()

Overrides com.google.common.collect.CompactHashSet.firstEntryIndex.

private int
getPredecessor(int entry)

pack-priv int
getSuccessor(int entry)

Overrides com.google.common.collect.CompactHashSet.getSuccessor.

pack-priv void
init(int expectedSize)

Overrides com.google.common.collect.CompactHashSet.init.

Pseudoconstructor for serialization support.
pack-priv void
insertEntry(int entryIndex, E object, int hash, int mask)

Overrides com.google.common.collect.CompactHashSet.insertEntry.

Creates a fresh entry with the specified object at the specified position in the entry arrays.
pack-priv void
moveLastEntry(int dstIndex, int mask)

Overrides com.google.common.collect.CompactHashSet.moveLastEntry.

Moves the last entry in the entry array into dstIndex, and nulls out its old position.
private int[]
requirePredecessors()

private int[]
requireSuccessors()

pack-priv void
resizeEntries(int newCapacity)

Overrides com.google.common.collect.CompactHashSet.resizeEntries.

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)

public Spliterator<E>
spliterator()

Overrides com.google.common.collect.CompactHashSet.spliterator.

Overrides default java.util.Set.spliterator, java.util.Collection.spliterator.

Creates a Spliterator over the elements in this set.
public @Nullable Object[]
toArray()

Overrides com.google.common.collect.CompactHashSet.toArray.

Implements java.util.Set.toArray, java.util.Collection.toArray.

Returns an array containing all of the elements in this set.
public <T extends @Nullable Object> T[]
toArray(T[]
the array into which the elements of this set are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
a)

Overrides com.google.common.collect.CompactHashSet.toArray.

Implements java.util.Set.toArray, java.util.Collection.toArray.

Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array.
Inherited from com.google.common.collect.CompactHashSet:
addcontainsdelegateOrNullforEachincrementModCountisEmptyisUsingHashFloodingResistanceiteratorneedsAllocArraysremovesizetrimToSize

Field Detail

ENDPOINTback to summary
private static final int ENDPOINT
firstEntryback to summary
private transient int firstEntry

Pointer to the first node in the linked list, or ENDPOINT if there are no entries.

lastEntryback to summary
private transient int lastEntry

Pointer to the last node in the linked list, or ENDPOINT if there are no entries.

predecessorback to summary
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 ≥ size() are UNSET.

Annotations
@CheckForNull
successorback to summary
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 ≥ size() are UNSET.

Annotations
@CheckForNull

Constructor Detail

CompactLinkedHashSetback to summary
pack-priv CompactLinkedHashSet()
CompactLinkedHashSetback to summary
pack-priv CompactLinkedHashSet(int expectedSize)

Method Detail

adjustAfterRemoveback to summary
pack-priv int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)

Overrides com.google.common.collect.CompactHashSet.adjustAfterRemove.

Doc from com.google.common.collect.CompactHashSet.adjustAfterRemove.

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.

Annotations
@Override
allocArraysback to summary
pack-priv int allocArrays()

Overrides com.google.common.collect.CompactHashSet.allocArrays.

Doc from com.google.common.collect.CompactHashSet.allocArrays.

Handle lazy allocation of arrays.

Annotations
@Override
clearback to summary
public void clear()

Overrides com.google.common.collect.CompactHashSet.clear.

Implements java.util.Set.clear, java.util.Collection.clear.

Doc from java.util.Set.clear.

Removes all of the elements from this set (optional operation). The set will be empty after this call returns.

Annotations
@Override
convertToHashFloodingResistantImplementationback to summary
pack-priv Set<E> convertToHashFloodingResistantImplementation()

Overrides com.google.common.collect.CompactHashSet.convertToHashFloodingResistantImplementation.

Annotations
@Override
@CanIgnoreReturnValue
createback to summary
public static <E extends @Nullable Object> CompactLinkedHashSet<E> create()

Hides com.google.common.collect.CompactHashSet.create.

Creates an empty CompactLinkedHashSet instance.

createback to summary
public static <E extends @Nullable Object> CompactLinkedHashSet<E> create(Collection<? extends E> collection)

Hides com.google.common.collect.CompactHashSet.create.

Creates a mutable CompactLinkedHashSet instance containing the elements of the given collection in the order returned by the collection's iterator.

Parameters
collection:Collection<? extends E>

the elements that the set should contain

Returns:CompactLinkedHashSet<E>

a new CompactLinkedHashSet containing those elements (minus duplicates)

createback to summary
public static <E extends @Nullable Object> CompactLinkedHashSet<E> create(E... elements)

Hides com.google.common.collect.CompactHashSet.create.

Creates a CompactLinkedHashSet instance containing the given elements in unspecified order.

Parameters
elements:E[]

the elements that the set should contain

Returns:CompactLinkedHashSet<E>

a new CompactLinkedHashSet containing those elements (minus duplicates)

Annotations
@SafeVarargs
createWithExpectedSizeback to summary
public static <E extends @Nullable Object> CompactLinkedHashSet<E> createWithExpectedSize(int expectedSize)

Hides com.google.common.collect.CompactHashSet.createWithExpectedSize.

Creates a CompactLinkedHashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without rebuilding internal data structures.

Parameters
expectedSize:int

the number of elements you expect to add to the returned set

Returns:CompactLinkedHashSet<E>

a new, empty CompactLinkedHashSet with enough capacity to hold expectedSize elements without resizing

Exceptions
IllegalArgumentException:
if expectedSize is negative
firstEntryIndexback to summary
pack-priv int firstEntryIndex()

Overrides com.google.common.collect.CompactHashSet.firstEntryIndex.

Annotations
@Override
getPredecessorback to summary
private int getPredecessor(int entry)
getSuccessorback to summary
pack-priv int getSuccessor(int entry)

Overrides com.google.common.collect.CompactHashSet.getSuccessor.

Annotations
@Override
initback to summary
pack-priv void init(int expectedSize)

Overrides com.google.common.collect.CompactHashSet.init.

Doc from com.google.common.collect.CompactHashSet.init.

Pseudoconstructor for serialization support.

Annotations
@Override
insertEntryback to summary
pack-priv void insertEntry(int entryIndex, E object, int hash, int mask)

Overrides com.google.common.collect.CompactHashSet.insertEntry.

Doc from com.google.common.collect.CompactHashSet.insertEntry.

Creates a fresh entry with the specified object at the specified position in the entry arrays.

Annotations
@Override
moveLastEntryback to summary
pack-priv void moveLastEntry(int dstIndex, int mask)

Overrides com.google.common.collect.CompactHashSet.moveLastEntry.

Doc from com.google.common.collect.CompactHashSet.moveLastEntry.

Moves the last entry in the entry array into dstIndex, and nulls out its old position.

Annotations
@Override
requirePredecessorsback to summary
private int[] requirePredecessors()
requireSuccessorsback to summary
private int[] requireSuccessors()
resizeEntriesback to summary
pack-priv void resizeEntries(int newCapacity)

Overrides com.google.common.collect.CompactHashSet.resizeEntries.

Doc from com.google.common.collect.CompactHashSet.resizeEntries.

Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.

Annotations
@Override
setPredecessorback to summary
private void setPredecessor(int entry, int pred)
setSucceedsback to summary
private void setSucceeds(int pred, int succ)
setSuccessorback to summary
private void setSuccessor(int entry, int succ)
spliteratorback to summary
public Spliterator<E> spliterator()

Overrides com.google.common.collect.CompactHashSet.spliterator.

Overrides default java.util.Set.spliterator, java.util.Collection.spliterator.

Doc from java.util.Set.spliterator.

Creates a Spliterator over the elements in this set.

The Spliterator reports Spliterator#DISTINCT. Implementations should document the reporting of additional characteristic values.

Returns:Spliterator<E>

a Spliterator over the elements in this set

Annotations
@Override
toArrayback to summary
public @Nullable Object[] toArray()

Overrides com.google.common.collect.CompactHashSet.toArray.

Implements java.util.Set.toArray, java.util.Collection.toArray.

Doc from java.util.Set.toArray.

Returns an array containing all of the elements in this set. If this set makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

The returned array will be "safe" in that no references to it are maintained by this set. (In other words, this method must allocate a new array even if this set is backed by an array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Returns:@Nullable Object[]

an array containing all the elements in this set

Annotations
@Override
toArrayback to summary
public <T extends @Nullable Object> T[] toArray(T[] a)

Overrides com.google.common.collect.CompactHashSet.toArray.

Implements java.util.Set.toArray, java.util.Collection.toArray.

Doc from java.util.Set.toArray.

Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array. If the set fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this set.

If this set fits in the specified array with room to spare (i.e., the array has more elements than this set), the element in the array immediately following the end of the set is set to null. (This is useful in determining the length of this set only if the caller knows that this set does not contain any null elements.)

If this set makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

Like the toArray() method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose x is a set known to contain only strings. The following code can be used to dump the set into a newly allocated array of String: 

    String[] y = x.toArray(new String[0]);
Note that toArray(new Object[0]) is identical in function to toArray().
Parameters
<T>

Doc from java.util.Collection.toArray. the component type of the array to contain the collection

a:T[]

the array into which the elements of this set are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.

Returns:T[]

an array containing all the elements in this set

Annotations
@Override
@SuppressWarnings:nullness