Class ImmutableSet<E>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- com.google.common.collect.ImmutableCollection<E>
-
- com.google.common.collect.ImmutableSet<E>
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Iterable<E>
,java.util.Collection<E>
,java.util.Set<E>
- Direct Known Subclasses:
ImmutableEnumSet
,ImmutableMapEntrySet
,ImmutableSet.Indexed
,ImmutableSetMultimap.EntrySet
,ImmutableSortedSetFauxverideShim
,IndexedImmutableSet
,RegularImmutableSet
,SingletonImmutableSet
public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements java.util.Set<E>
ASet
whose contents will never change, with many other important properties detailed atImmutableCollection
.- Since:
- 2.0
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
ImmutableSet.Builder<E>
A builder for creatingImmutableSet
instances.(package private) static class
ImmutableSet.Indexed<E>
private static class
ImmutableSet.JdkBackedSetBuilderImpl<E>
SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection.private static class
ImmutableSet.RegularSetBuilderImpl<E>
Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash table and deduplicating elements as they come, so it only allocates O(max(distinct, expectedCapacity)) rather than O(calls to add).private static class
ImmutableSet.SerializedForm
private static class
ImmutableSet.SetBuilderImpl<E>
Swappable internal implementation of an ImmutableSet.Builder.
-
Field Summary
Fields Modifier and Type Field Description private ImmutableList<E>
asList
private static int
CUTOFF
private static double
DESIRED_LOAD_FACTOR
(package private) static double
HASH_FLOODING_FPP
We attempt to detect deliberate hash flooding attempts, and if one is detected, fall back to a wrapper around j.u.HashSet, which has built in flooding protection.(package private) static int
MAX_RUN_MULTIPLIER
(package private) static int
MAX_TABLE_SIZE
(package private) static int
SPLITERATOR_CHARACTERISTICS
-
Constructor Summary
Constructors Constructor Description ImmutableSet()
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description ImmutableList<E>
asList()
Returns anImmutableList
containing the same elements, in the same order, as this collection.static <E> ImmutableSet.Builder<E>
builder()
Returns a new builder.static <E> ImmutableSet.Builder<E>
builderWithExpectedSize(int expectedSize)
Returns a new builder, expecting the specified number of distinct elements to be added.(package private) static int
chooseTableSize(int setSize)
Returns an array size suitable for the backing array of a hash table that uses open addressing with linear probing in its implementation.private static <E> ImmutableSet<E>
construct(int n, int expectedSize, java.lang.Object... elements)
Constructs anImmutableSet
from the firstn
elements of the specified array.private static <E> ImmutableSet<E>
constructUnknownDuplication(int n, java.lang.Object... elements)
Constructs anImmutableSet
from the firstn
elements of the specified array, which we have no particular reason to believe does or does not contain duplicates.static <E> ImmutableSet<E>
copyOf(E[] elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source array.static <E> ImmutableSet<E>
copyOf(java.lang.Iterable<? extends E> elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source iterable.static <E> ImmutableSet<E>
copyOf(java.util.Collection<? extends E> elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source collection.static <E> ImmutableSet<E>
copyOf(java.util.Iterator<? extends E> elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source iterator.private static ImmutableSet
copyOfEnumSet(java.util.EnumSet enumSet)
(package private) ImmutableList<E>
createAsList()
boolean
equals(java.lang.Object object)
int
hashCode()
(package private) static boolean
hashFloodingDetected(java.lang.Object[] hashTable)
Checks the whole hash table for poor hash distribution.(package private) boolean
isHashCodeFast()
Returnstrue
if thehashCode()
method runs quickly.abstract UnmodifiableIterator<E>
iterator()
Returns an unmodifiable iterator across the elements in this collection.private static int
maxRunBeforeFallback(int tableSize)
If more than this many consecutive positions are filled in a table of the specified size, report probable hash flooding.static <E> ImmutableSet<E>
of()
Returns the empty immutable set.static <E> ImmutableSet<E>
of(E element)
Returns an immutable set containingelement
.static <E> ImmutableSet<E>
of(E e1, E e2)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified.static <E> ImmutableSet<E>
of(E e1, E e2, E e3)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified.static <E> ImmutableSet<E>
of(E e1, E e2, E e3, E e4)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified.static <E> ImmutableSet<E>
of(E e1, E e2, E e3, E e4, E e5)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified.static <E> ImmutableSet<E>
of(E e1, E e2, E e3, E e4, E e5, E e6, E... others)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified.(package private) static java.lang.Object[]
rebuildHashTable(int newTableSize, java.lang.Object[] elements, int n)
Builds a new open-addressed hash table from the first n objects in elements.static <E> java.util.stream.Collector<E,?,ImmutableSet<E>>
toImmutableSet()
Returns aCollector
that accumulates the input elements into a newImmutableSet
.(package private) java.lang.Object
writeReplace()
-
Methods inherited from class com.google.common.collect.ImmutableCollection
add, addAll, clear, contains, copyIntoArray, internalArray, internalArrayEnd, internalArrayStart, isPartialView, remove, removeAll, removeIf, retainAll, spliterator, toArray, toArray
-
-
-
-
Field Detail
-
SPLITERATOR_CHARACTERISTICS
static final int SPLITERATOR_CHARACTERISTICS
- See Also:
- Constant Field Values
-
asList
private transient ImmutableList<E> asList
-
MAX_TABLE_SIZE
static final int MAX_TABLE_SIZE
- See Also:
- Constant Field Values
-
DESIRED_LOAD_FACTOR
private static final double DESIRED_LOAD_FACTOR
- See Also:
- Constant Field Values
-
CUTOFF
private static final int CUTOFF
- See Also:
- Constant Field Values
-
HASH_FLOODING_FPP
static final double HASH_FLOODING_FPP
We attempt to detect deliberate hash flooding attempts, and if one is detected, fall back to a wrapper around j.u.HashSet, which has built in flooding protection. HASH_FLOODING_FPP is the maximum allowed probability of falsely detecting a hash flooding attack if the input is randomly generated.MAX_RUN_MULTIPLIER was determined experimentally to match this FPP.
- See Also:
- Constant Field Values
-
MAX_RUN_MULTIPLIER
static final int MAX_RUN_MULTIPLIER
- See Also:
- Constant Field Values
-
-
Method Detail
-
toImmutableSet
public static <E> java.util.stream.Collector<E,?,ImmutableSet<E>> toImmutableSet()
Returns aCollector
that accumulates the input elements into a newImmutableSet
. Elements appear in the resulting set in the encounter order of the stream; if the stream contains duplicates (according toObject.equals(Object)
), only the first duplicate in encounter order will appear in the result.- Since:
- 21.0
-
of
public static <E> ImmutableSet<E> of()
Returns the empty immutable set. Preferred overCollections.emptySet()
for code consistency, and because the return type conveys the immutability guarantee.
-
of
public static <E> ImmutableSet<E> of(E element)
Returns an immutable set containingelement
. Preferred overCollections.singleton(T)
for code consistency,null
rejection, and because the return type conveys the immutability guarantee.
-
of
public static <E> ImmutableSet<E> of(E e1, E e2)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored.
-
of
public static <E> ImmutableSet<E> of(E e1, E e2, E e3)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored.
-
of
public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored.
-
of
public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored.
-
of
@SafeVarargs public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others)
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored.The array
others
must not be longer thanInteger.MAX_VALUE - 6
.- Since:
- 3.0 (source-compatible since 2.0)
-
constructUnknownDuplication
private static <E> ImmutableSet<E> constructUnknownDuplication(int n, java.lang.Object... elements)
Constructs anImmutableSet
from the firstn
elements of the specified array, which we have no particular reason to believe does or does not contain duplicates. Ifk
is the size of the returnedImmutableSet
, then the unique elements ofelements
will be in the firstk
positions, andelements[i] == null
fork <= i < n
.This may modify
elements
. Additionally, ifn == elements.length
andelements
contains no duplicates,elements
may be used without copying in the returnedImmutableSet
, in which case the caller must not modify it.elements
may contain only values of typeE
.- Throws:
java.lang.NullPointerException
- if any of the firstn
elements ofelements
is null
-
construct
private static <E> ImmutableSet<E> construct(int n, int expectedSize, java.lang.Object... elements)
Constructs anImmutableSet
from the firstn
elements of the specified array. Ifk
is the size of the returnedImmutableSet
, then the unique elements ofelements
will be in the firstk
positions, andelements[i] == null
fork <= i < n
.This may modify
elements
. Additionally, ifn == elements.length
andelements
contains no duplicates,elements
may be used without copying in the returnedImmutableSet
, in which case it may no longer be modified.elements
may contain only values of typeE
.- Throws:
java.lang.NullPointerException
- if any of the firstn
elements ofelements
is null
-
copyOf
public static <E> ImmutableSet<E> copyOf(java.util.Collection<? extends E> elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source collection.Performance note: This method will sometimes recognize that the actual copy operation is unnecessary; for example,
copyOf(copyOf(anArrayList))
will copy the data only once. This reduces the expense of habitually making defensive copies at API boundaries. However, the precise conditions for skipping the copy operation are undefined.- Throws:
java.lang.NullPointerException
- if any ofelements
is null- Since:
- 7.0 (source-compatible since 2.0)
-
copyOf
public static <E> ImmutableSet<E> copyOf(java.lang.Iterable<? extends E> elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source iterable. This method iterates overelements
only once.Performance note: This method will sometimes recognize that the actual copy operation is unnecessary; for example,
copyOf(copyOf(anArrayList))
should copy the data only once. This reduces the expense of habitually making defensive copies at API boundaries. However, the precise conditions for skipping the copy operation are undefined.- Throws:
java.lang.NullPointerException
- if any ofelements
is null
-
copyOf
public static <E> ImmutableSet<E> copyOf(java.util.Iterator<? extends E> elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source iterator.- Throws:
java.lang.NullPointerException
- if any ofelements
is null
-
copyOf
public static <E> ImmutableSet<E> copyOf(E[] elements)
Returns an immutable set containing each ofelements
, minus duplicates, in the order each appears first in the source array.- Throws:
java.lang.NullPointerException
- if any ofelements
is null- Since:
- 3.0
-
copyOfEnumSet
private static ImmutableSet copyOfEnumSet(java.util.EnumSet enumSet)
-
isHashCodeFast
boolean isHashCodeFast()
Returnstrue
if thehashCode()
method runs quickly.
-
equals
public boolean equals(java.lang.Object object)
-
hashCode
public int hashCode()
-
iterator
public abstract UnmodifiableIterator<E> iterator()
Description copied from class:ImmutableCollection
Returns an unmodifiable iterator across the elements in this collection.
-
asList
public ImmutableList<E> asList()
Description copied from class:ImmutableCollection
Returns anImmutableList
containing the same elements, in the same order, as this collection.Performance note: in most cases this method can return quickly without actually copying anything. The exact circumstances under which the copy is performed are undefined and subject to change.
- Overrides:
asList
in classImmutableCollection<E>
-
createAsList
ImmutableList<E> createAsList()
-
writeReplace
java.lang.Object writeReplace()
- Overrides:
writeReplace
in classImmutableCollection<E>
-
builder
public static <E> ImmutableSet.Builder<E> builder()
Returns a new builder. The generated builder is equivalent to the builder created by theImmutableSet.Builder
constructor.
-
builderWithExpectedSize
public static <E> ImmutableSet.Builder<E> builderWithExpectedSize(int expectedSize)
Returns a new builder, expecting the specified number of distinct elements to be added.If
expectedSize
is exactly the number of distinct elements added to the builder beforeImmutableSet.Builder.build()
is called, the builder is likely to perform better than an unsizedbuilder()
would have.It is not specified if any performance benefits apply if
expectedSize
is close to, but not exactly, the number of distinct elements added to the builder.- Since:
- 23.1
-
rebuildHashTable
static java.lang.Object[] rebuildHashTable(int newTableSize, java.lang.Object[] elements, int n)
Builds a new open-addressed hash table from the first n objects in elements.
-
chooseTableSize
static int chooseTableSize(int setSize)
Returns an array size suitable for the backing array of a hash table that uses open addressing with linear probing in its implementation. The returned size is the smallest power of two that can hold setSize elements with the desired load factor. Always returns at least setSize + 2.
-
hashFloodingDetected
static boolean hashFloodingDetected(java.lang.Object[] hashTable)
Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n / log n) on average.The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many exactly matching hash codes, which would cause construction to take O(n^2), but can't detect e.g. hash codes adversarially designed to go into ascending table locations, which keeps construction O(n) (as desired) but then can have O(n) queries later.
If this returns false, then no query can take more than O(log n).
Note that for a RegularImmutableSet with elements with truly random hash codes, contains operations take expected O(1) time but with high probability take O(log n) for at least some element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis)
This method may return
true
up toHASH_FLOODING_FPP
of the time even on truly random input.If this method returns false, there are definitely no runs of length at least
maxRunBeforeFallback(hashTable.length)
nonnull elements. If there are no runs of length at leastmaxRunBeforeFallback(hashTable.length) / 2
nonnull elements, this method definitely returns false. In between those constraints, the result of this method is undefined, subject to the aboveHASH_FLOODING_FPP
constraint.
-
maxRunBeforeFallback
private static int maxRunBeforeFallback(int tableSize)
If more than this many consecutive positions are filled in a table of the specified size, report probable hash flooding. (hashFloodingDetected(java.lang.Object[])
may also report hash flooding if fewer consecutive positions are filled; see that method for details.)
-
-