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

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

extends AbstractSet<E extends @Nullable Object>
implements Serializable
Class Inheritance
All Implemented Interfaces
java.io.Serializable
Known Direct Subclasses
com.google.common.collect.CompactLinkedHashSet
Annotations
@GwtIncompatible
@ElementTypesAreNonnullByDefault
Static Imports
com.google.common.base.Preconditions.checkNotNull, com.google.common.collect.CollectPreconditions.checkRemove, .CompactHashing.UNSET, .Hashing.smearedHash, java.util.Objects.requireNonNull
CompactHashSet is an implementation of a Set. All optional operations (adding and removing) are supported. The elements can be any objects.

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.

Unlike java.util.HashSet, iteration is only proportional to the actual size(), which is optimal, and not the size of the internal hashtable, which could be much larger than size(). Furthermore, this structure only depends on a fixed number of arrays; add(x) operations do not create objects for the garbage collector to deal with, and for every element added, the garbage collector will have to traverse 1.5 references on average, in the marking phase, not 5.0 as in java.util.HashSet.

If there are no removals, then iteration order is the same as insertion order. Any removal invalidates any ordering guarantees.

This class should not be assumed to be universally superior to java.util.HashSet. 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.

Authors
Dimitris Andreou, Jon Noack

Field Summary

Modifier and TypeField and Description
pack-priv transient @Nullable Object[]
elements

The elements contained in the set, in the range of [0, size()).

private transient int[]
entries

Contains the logical entries, in the range of [0, size()).

pack-priv static final double
HASH_FLOODING_FPP

Maximum allowed false positive probability of detecting a hash flooding attack given random input.

private static final int
MAX_HASH_BUCKET_LENGTH

Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashSet based implementation.

private transient int
metadata

Keeps track of metadata like the number of hash table bits and modifications of this data structure (to make it possible to throw ConcurrentModificationException in the iterator).

private transient int
size

The number of elements contained in the set.

private transient Object
table

The hashtable object.

Constructor Summary

AccessConstructor and Description
pack-priv
CompactHashSet()

Constructs a new empty instance of CompactHashSet.

pack-priv
CompactHashSet(int
the initial capacity of this CompactHashSet.
expectedSize)

Constructs a new instance of CompactHashSet with the specified capacity.

Method Summary

Modifier and TypeMethod and Description
public boolean
add(E
element to be added to this set
object)

Overrides java.util.AbstractCollection.add.

Implements java.util.Set.add, java.util.Collection.add.

Adds the specified element to this set if it is not already present (optional operation).
pack-priv 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.

pack-priv int
allocArrays()

Handle lazy allocation of arrays.

public void
clear()

Overrides java.util.AbstractCollection.clear.

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

Removes all of the elements from this set (optional operation).
public boolean
contains(Object
element whose presence in this set is to be tested
object)

Overrides java.util.AbstractCollection.contains.

Implements java.util.Set.contains, java.util.Collection.contains.

Returns true if this set contains the specified element.
pack-priv Set<E>
convertToHashFloodingResistantImplementation()

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

Creates an empty CompactHashSet instance.

public static <E extends @Nullable Object> CompactHashSet<E>

Returns:

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

Creates a mutable CompactHashSet instance containing the elements of the given collection in unspecified order.

public static <E extends @Nullable Object> CompactHashSet<E>

Returns:

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

Creates a mutable CompactHashSet instance containing the given elements in unspecified order.

private Set<E>
createHashFloodingResistantDelegate(int tableSize)

public static <E extends @Nullable Object> CompactHashSet<E>

Returns:

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

Creates a CompactHashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth.

pack-priv Set<E>
delegateOrNull()

private E
element(int i)

private int
entry(int i)

pack-priv int
firstEntryIndex()

public void
forEach(Consumer<? super E>
The action to be performed for each element
action)

Overrides default java.lang.Iterable.forEach.

Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception.
pack-priv int
getSuccessor(int entryIndex)

private int
hashTableMask()

Gets the hash table mask using the stored number of hash table bits.

pack-priv void
incrementModCount()

pack-priv void
init(int expectedSize)

Pseudoconstructor for serialization support.

pack-priv 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.

public boolean
isEmpty()

Overrides java.util.AbstractCollection.isEmpty.

Implements java.util.Set.isEmpty, java.util.Collection.isEmpty.

Returns true if this set contains no elements.
pack-priv boolean
isUsingHashFloodingResistance()

public Iterator<E>
iterator()

Implements abstract java.util.AbstractCollection.iterator.

Implements java.util.Set.iterator, java.util.Collection.iterator.

Returns an iterator over the elements in this set.
pack-priv void
moveLastEntry(int dstIndex, int mask)

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

pack-priv boolean
needsAllocArrays()

Returns whether arrays need to be allocated.

private void
readObject(ObjectInputStream stream)

public boolean
remove(Object
object to be removed from this set, if present
object)

Overrides java.util.AbstractCollection.remove.

Implements java.util.Set.remove, java.util.Collection.remove.

Removes the specified element from this set if it is present (optional operation).
private @Nullable Object[]
requireElements()

private int[]
requireEntries()

private Object
requireTable()

pack-priv 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
resizeMeMaybe(int newSize)

Resizes the entries storage if necessary.

private int
resizeTable(int oldMask, int newCapacity, int targetHash, int targetEntryIndex)

private void
setElement(int i, E value)

private void
setEntry(int i, int value)

private void
setHashTableMask(int mask)

Stores the hash table mask as the number of bits needed to represent an index.

public int
size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.Set.size, java.util.Collection.size.

Returns the number of elements in this set (its cardinality).
public Spliterator<E>
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 java.util.AbstractCollection.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 java.util.AbstractCollection.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.
public void
trimToSize()

Ensures that this CompactHashSet has the smallest representation in memory, given its current size.

private void
writeObject(ObjectOutputStream stream)

Inherited from java.util.AbstractSet:
equalshashCoderemoveAll

Field Detail

elementsback to summary
pack-priv transient @Nullable Object[] elements

The elements contained in the set, in the range of [0, size()). The elements in [size(), elements.length) are all null.

Annotations
@VisibleForTesting
@CheckForNull
entriesback to summary
private transient int[] entries

Contains the logical entries, in the range of [0, size()). The high bits of each int are the part of the smeared hash of the element not covered by the hashtable mask, whereas the low bits are the "next" pointer (pointing to the next entry in the bucket chain), which will always be less than or equal to the hashtable mask. 

hash  = aaaaaaaa
mask  = 00000fff
next  = 00000bbb
entry = aaaaabbb

The pointers in [size(), entries.length) are all "null" (UNSET).

Annotations
@CheckForNull
HASH_FLOODING_FPPback to summary
pack-priv static final double HASH_FLOODING_FPP

Maximum allowed false positive probability of detecting a hash flooding attack given random input.

Annotations
@VisibleForTesting
MAX_HASH_BUCKET_LENGTHback to summary
private static final int MAX_HASH_BUCKET_LENGTH

Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashSet based implementation. Experimentally determined.

metadataback to summary
private transient int metadata

Keeps track of metadata like the number of hash table bits and modifications of this data structure (to make it possible to throw ConcurrentModificationException in the iterator). Note that we choose not to make this volatile, so we do less of a "best effort" to track such errors, for better performance.

sizeback to summary
private transient int size

The number of elements contained in the set.

tableback to summary
private transient Object table

The hashtable object. This can be either:

  • a byte[], short[], or int[], with size a power of two, created by CompactHashing.createTable, whose values are either
    • UNSET, meaning "null pointer"
    • one plus an index into the entries and elements array
  • another java.util.Set delegate implementation. In most modern JDKs, normal java.util hash collections intelligently fall back to a binary search tree if hash table collisions are detected. Rather than going to all the trouble of reimplementing this ourselves, we simply switch over to use the JDK implementation wholesale if probable hash flooding is detected, sacrificing the compactness guarantee in very rare cases in exchange for much more reliable worst-case behavior.
  • null, if no entries have yet been added to the map
Annotations
@CheckForNull

Constructor Detail

CompactHashSetback to summary
pack-priv CompactHashSet()

Constructs a new empty instance of CompactHashSet.

CompactHashSetback to summary
pack-priv CompactHashSet(int expectedSize)

Constructs a new instance of CompactHashSet with the specified capacity.

Parameters
expectedSize:int

the initial capacity of this CompactHashSet.

Method Detail

addback to summary
public boolean add(E object)

Overrides java.util.AbstractCollection.add.

Implements java.util.Set.add, java.util.Collection.add.

Doc from java.util.Set.add.

Adds the specified element to this set if it is not already present (optional operation). More formally, adds the specified element e to this set if the set contains no element e2 such that Objects.equals(e, e2). If this set already contains the element, the call leaves the set unchanged and returns false. In combination with the restriction on constructors, this ensures that sets never contain duplicate elements.

The stipulation above does not imply that sets must accept all elements; sets may refuse to add any particular element, including null, and throw an exception, as described in the specification for Collection.add. Individual set implementations should clearly document any restrictions on the elements that they may contain.

Parameters
object:E

element to be added to this set

Returns:boolean

true if this set did not already contain the specified element

Annotations
@CanIgnoreReturnValue
@Override
adjustAfterRemoveback to summary
pack-priv 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.

allocArraysback to summary
pack-priv int allocArrays()

Handle lazy allocation of arrays.

Annotations
@CanIgnoreReturnValue
clearback to summary
public void clear()

Overrides java.util.AbstractCollection.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
containsback to summary
public boolean contains(Object object)

Overrides java.util.AbstractCollection.contains.

Implements java.util.Set.contains, java.util.Collection.contains.

Doc from java.util.Set.contains.

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that Objects.equals(o, e).

Parameters
object:Object

element whose presence in this set is to be tested

Returns:boolean

true if this set contains the specified element

Annotations
@Override
convertToHashFloodingResistantImplementationback to summary
pack-priv Set<E> convertToHashFloodingResistantImplementation()
Annotations
@VisibleForTesting
@CanIgnoreReturnValue
createback to summary
public static <E extends @Nullable Object> CompactHashSet<E> create()

Creates an empty CompactHashSet instance.

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

Creates a mutable CompactHashSet instance containing the elements of the given collection in unspecified order.

Parameters
collection:Collection<? extends E>

the elements that the set should contain

Returns:CompactHashSet<E>

a new CompactHashSet containing those elements (minus duplicates)

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

Creates a mutable CompactHashSet instance containing the given elements in unspecified order.

Parameters
elements:E[]

the elements that the set should contain

Returns:CompactHashSet<E>

a new CompactHashSet containing those elements (minus duplicates)

Annotations
@SafeVarargs
@SuppressWarnings:nullness
createHashFloodingResistantDelegateback to summary
private Set<E> createHashFloodingResistantDelegate(int tableSize)
createWithExpectedSizeback to summary
public static <E extends @Nullable Object> CompactHashSet<E> createWithExpectedSize(int expectedSize)

Creates a CompactHashSet instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth.

Parameters
expectedSize:int

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

Returns:CompactHashSet<E>

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

Exceptions
IllegalArgumentException:
if expectedSize is negative
delegateOrNullback to summary
pack-priv Set<E> delegateOrNull()
Annotations
@SuppressWarnings:unchecked
@VisibleForTesting
@CheckForNull
elementback to summary
private E element(int i)
Annotations
@SuppressWarnings:unchecked
entryback to summary
private int entry(int i)
firstEntryIndexback to summary
pack-priv int firstEntryIndex()
forEachback to summary
public void forEach(Consumer<? super E> action)

Overrides default java.lang.Iterable.forEach.

Doc from java.lang.Iterable.forEach.

Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.

The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy.

Parameters
action:Consumer<? super E>

The action to be performed for each element

Annotations
@Override
getSuccessorback to summary
pack-priv int getSuccessor(int entryIndex)
hashTableMaskback to summary
private int hashTableMask()

Gets the hash table mask using the stored number of hash table bits.

incrementModCountback to summary
pack-priv void incrementModCount()
initback to summary
pack-priv void init(int expectedSize)

Pseudoconstructor for serialization support.

insertEntryback to summary
pack-priv 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.

isEmptyback to summary
public boolean isEmpty()

Overrides java.util.AbstractCollection.isEmpty.

Implements java.util.Set.isEmpty, java.util.Collection.isEmpty.

Doc from java.util.Set.isEmpty.

Returns true if this set contains no elements.

Returns:boolean

true if this set contains no elements

Annotations
@Override
isUsingHashFloodingResistanceback to summary
pack-priv boolean isUsingHashFloodingResistance()
Annotations
@VisibleForTesting
iteratorback to summary
public Iterator<E> iterator()

Implements abstract java.util.AbstractCollection.iterator.

Implements java.util.Set.iterator, java.util.Collection.iterator.

Doc from java.util.Set.iterator.

Returns an iterator over the elements in this set. The elements are returned in no particular order (unless this set is an instance of some class that provides a guarantee).

Returns:Iterator<E>

an iterator over the elements in this set

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

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

needsAllocArraysback to summary
pack-priv boolean needsAllocArrays()

Returns whether arrays need to be allocated.

Annotations
@VisibleForTesting
readObjectback to summary
private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException
Annotations
@SuppressWarnings:unchecked
@J2ktIncompatible
removeback to summary
public boolean remove(Object object)

Overrides java.util.AbstractCollection.remove.

Implements java.util.Set.remove, java.util.Collection.remove.

Doc from java.util.Set.remove.

Removes the specified element from this set if it is present (optional operation). More formally, removes an element e such that Objects.equals(o, e), if this set contains such an element. Returns true if this set contained the element (or equivalently, if this set changed as a result of the call). (This set will not contain the element once the call returns.)

Parameters
object:Object

object to be removed from this set, if present

Returns:boolean

true if this set contained the specified element

Annotations
@CanIgnoreReturnValue
@Override
requireElementsback to summary
private @Nullable Object[] requireElements()
requireEntriesback to summary
private int[] requireEntries()
requireTableback to summary
private Object requireTable()
resizeEntriesback to summary
pack-priv void resizeEntries(int newCapacity)

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

resizeMeMaybeback to summary
private void resizeMeMaybe(int newSize)

Resizes the entries storage if necessary.

resizeTableback to summary
private int resizeTable(int oldMask, int newCapacity, int targetHash, int targetEntryIndex)
Annotations
@CanIgnoreReturnValue
setElementback to summary
private void setElement(int i, E value)
setEntryback to summary
private void setEntry(int i, int value)
setHashTableMaskback to summary
private void setHashTableMask(int mask)

Stores the hash table mask as the number of bits needed to represent an index.

sizeback to summary
public int size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.Set.size, java.util.Collection.size.

Doc from java.util.Set.size.

Returns the number of elements in this set (its cardinality). If this set contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Returns:int

the number of elements in this set (its cardinality)

Annotations
@Override
spliteratorback to summary
public Spliterator<E> 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 java.util.AbstractCollection.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 java.util.AbstractCollection.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
@CanIgnoreReturnValue
@Override
@SuppressWarnings:nullness
trimToSizeback to summary
public void trimToSize()

Ensures that this CompactHashSet has the smallest representation in memory, given its current size.

writeObjectback to summary
private void writeObject(ObjectOutputStream stream) throws IOException
Annotations
@J2ktIncompatible