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
Pointer to the first node in the linked list, orENDPOINT
if there are no entries.private int
lastEntry
Pointer to the last node in the linked list, orENDPOINT
if there are no entries.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
DEFAULT_SIZE, elements, 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.(package private) void
allocArrays()
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(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()
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)
Creates a fresh entry with the specified object at the specified position in the entry arrays.(package private) void
moveLastEntry(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.private void
setPredecessor(int entry, int pred)
private void
setSucceeds(int pred, int succ)
private void
setSuccessor(int entry, int succ)
java.util.Spliterator<E>
spliterator()
java.lang.Object[]
toArray()
<T> T[]
toArray(T[] a)
-
Methods inherited from class com.google.common.collect.CompactHashSet
add, contains, forEach, isEmpty, iterator, needsAllocArrays, 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
Pointer to the first node in the linked list, orENDPOINT
if there are no entries.
-
lastEntry
private transient int lastEntry
Pointer to the last node in the linked list, orENDPOINT
if there are no entries.
-
-
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)
Description copied from class:CompactHashSet
Pseudoconstructor for serialization support.- Overrides:
init
in classCompactHashSet<E>
-
allocArrays
void allocArrays()
Description copied from class:CompactHashSet
Handle lazy allocation of arrays.- Overrides:
allocArrays
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
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>
-
moveLastEntry
void moveLastEntry(int dstIndex)
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
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>
-
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>
-
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>
-
-