@GwtCompatible(serializable=true, emulated=true) public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements java.util.Set<E>
Set
whose contents will never change, with many other important properties detailed at
ImmutableCollection
.Modifier and Type | Class and Description |
---|---|
static class |
ImmutableSet.Builder<E>
A builder for creating
ImmutableSet 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.
|
Modifier and Type | Field and 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 and Description |
---|
ImmutableSet() |
Modifier and Type | Method and Description |
---|---|
ImmutableList<E> |
asList()
Returns an
ImmutableList 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,
java.lang.Object... elements)
Constructs an
ImmutableSet from the first n elements of the specified array. |
static <E> ImmutableSet<E> |
copyOf(java.util.Collection<? extends E> elements)
Returns an immutable set containing each of
elements , minus duplicates, in the order
each appears first in the source collection. |
static <E> ImmutableSet<E> |
copyOf(E[] elements)
Returns an immutable set containing each of
elements , 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 of
elements , minus duplicates, in the order
each appears first in the source iterable. |
static <E> ImmutableSet<E> |
copyOf(java.util.Iterator<? extends E> elements)
Returns an immutable set containing each of
elements , 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()
Returns
true if the hashCode() method runs quickly. |
abstract UnmodifiableIterator<E> |
iterator()
Returns an unmodifiable iterator across the elements in this collection.
|
(package 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 containing
element . |
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 a
Collector that accumulates the input elements into a new ImmutableSet . |
(package private) java.lang.Object |
writeReplace() |
add, addAll, clear, contains, copyIntoArray, isPartialView, remove, removeAll, removeIf, retainAll, spliterator, toArray, toArray
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
static final int SPLITERATOR_CHARACTERISTICS
private transient ImmutableList<E> asList
static final int MAX_TABLE_SIZE
private static final double DESIRED_LOAD_FACTOR
private static final int CUTOFF
static final double HASH_FLOODING_FPP
MAX_RUN_MULTIPLIER was determined experimentally to match this FPP.
static final int MAX_RUN_MULTIPLIER
@Beta public static <E> java.util.stream.Collector<E,?,ImmutableSet<E>> toImmutableSet()
Collector
that accumulates the input elements into a new ImmutableSet
. Elements appear in the resulting set in the encounter order of the stream; if
the stream contains duplicates (according to Object.equals(Object)
), only the first
duplicate in encounter order will appear in the result.public static <E> ImmutableSet<E> of()
Collections.emptySet()
for code
consistency, and because the return type conveys the immutability guarantee.public static <E> ImmutableSet<E> of(E element)
element
. Preferred over Collections.singleton(T)
for code consistency, null
rejection, and because the return
type conveys the immutability guarantee.public static <E> ImmutableSet<E> of(E e1, E e2)
public static <E> ImmutableSet<E> of(E e1, E e2, E e3)
public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4)
public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5)
@SafeVarargs public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others)
The array others
must not be longer than Integer.MAX_VALUE - 6
.
private static <E> ImmutableSet<E> construct(int n, java.lang.Object... elements)
ImmutableSet
from the first n
elements of the specified array. If
k
is the size of the returned ImmutableSet
, then the unique elements of elements
will be in the first k
positions, and elements[i] == null
for k <= i < n
.
This may modify elements
. Additionally, if n == elements.length
and elements
contains no duplicates, elements
may be used without copying in the returned
ImmutableSet
, in which case it may no longer be modified.
elements
may contain only values of type E
.
java.lang.NullPointerException
- if any of the first n
elements of elements
is nullpublic static <E> ImmutableSet<E> copyOf(java.util.Collection<? extends E> elements)
elements
, 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.
java.lang.NullPointerException
- if any of elements
is nullpublic static <E> ImmutableSet<E> copyOf(java.lang.Iterable<? extends E> elements)
elements
, minus duplicates, in the order
each appears first in the source iterable. This method iterates over elements
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.
java.lang.NullPointerException
- if any of elements
is nullpublic static <E> ImmutableSet<E> copyOf(java.util.Iterator<? extends E> elements)
elements
, minus duplicates, in the order
each appears first in the source iterator.java.lang.NullPointerException
- if any of elements
is nullpublic static <E> ImmutableSet<E> copyOf(E[] elements)
elements
, minus duplicates, in the order
each appears first in the source array.java.lang.NullPointerException
- if any of elements
is nullprivate static ImmutableSet copyOfEnumSet(java.util.EnumSet enumSet)
boolean isHashCodeFast()
true
if the hashCode()
method runs quickly.public boolean equals(java.lang.Object object)
public int hashCode()
public abstract UnmodifiableIterator<E> iterator()
ImmutableCollection
public ImmutableList<E> asList()
ImmutableCollection
ImmutableList
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.
asList
in class ImmutableCollection<E>
ImmutableList<E> createAsList()
java.lang.Object writeReplace()
writeReplace
in class ImmutableCollection<E>
public static <E> ImmutableSet.Builder<E> builder()
ImmutableSet.Builder
constructor.@Beta public static <E> ImmutableSet.Builder<E> builderWithExpectedSize(int expectedSize)
If expectedSize
is exactly the number of distinct elements added to the builder
before ImmutableSet.Builder.build()
is called, the builder is likely to perform better than an unsized
builder()
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.
static java.lang.Object[] rebuildHashTable(int newTableSize, java.lang.Object[] elements, int n)
static int chooseTableSize(int setSize)
static boolean hashFloodingDetected(java.lang.Object[] hashTable)
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)
static int maxRunBeforeFallback(int tableSize)