com.google.common.collect

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, 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.

Field Summary

Fields

Modifier and Type	Field and 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 and Description
CompactLinkedHashSet()
CompactLinkedHashSet(int expectedSize)

Method Summary

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.
void	clear()
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()
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 into dstIndex, 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

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.Set

addAll, containsAll, retainAll

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

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

Constructor Detail

CompactLinkedHashSet

CompactLinkedHashSet()

CompactLinkedHashSet

CompactLinkedHashSet(int expectedSize)

Method Detail

create

public static <E> CompactLinkedHashSet<E> create()

Creates an empty CompactLinkedHashSet instance.

create

public 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.

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 a CompactLinkedHashSet 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 a CompactLinkedHashSet instance, with a high enough "initial capacity" that it should hold expectedSize 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 hold expectedSize elements without resizing

Throws:

java.lang.IllegalArgumentException - if expectedSize is negative

init

void init(int expectedSize,
          float loadFactor)

Description copied from class: CompactHashSet

Pseudoconstructor for serialization support.

Overrides:

init in class CompactHashSet<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 class CompactHashSet<E>

moveEntry

void moveEntry(int dstIndex)

Description copied from class: CompactHashSet

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

Overrides:

moveEntry in class CompactHashSet<E>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<E>

Specified by:

clear in interface java.util.Set<E>

Overrides:

clear in class CompactHashSet<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 class CompactHashSet<E>

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.Set<E>

Overrides:

toArray in class CompactHashSet<E>

toArray

public <T> T[] toArray(T[] a)

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.Set<E>

Overrides:

toArray in class CompactHashSet<E>

firstEntryIndex

int firstEntryIndex()

Overrides:

firstEntryIndex in class CompactHashSet<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 class CompactHashSet<E>

getSuccessor

int getSuccessor(int entryIndex)

Overrides:

getSuccessor in class CompactHashSet<E>

spliterator

public java.util.Spliterator<E> spliterator()

Specified by:

spliterator in interface java.lang.Iterable<E>

Specified by:

spliterator in interface java.util.Collection<E>

Specified by:

spliterator in interface java.util.Set<E>

Overrides:

spliterator in class CompactHashSet<E>

forEach

public void forEach(java.util.function.Consumer<? super E> action)

Specified by:

forEach in interface java.lang.Iterable<E>

Overrides:

forEach in class CompactHashSet<E>