Class ImmutableSet.RegularSetBuilderImpl<E>
- java.lang.Object
-
- com.google.common.collect.ImmutableSet.SetBuilderImpl<E>
-
- com.google.common.collect.ImmutableSet.RegularSetBuilderImpl<E>
-
- Enclosing class:
- ImmutableSet<E>
private static final class ImmutableSet.RegularSetBuilderImpl<E> extends ImmutableSet.SetBuilderImpl<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).This implementation attempts to detect hash flooding, and if it's identified, falls back to JdkBackedSetBuilderImpl.
-
-
Field Summary
Fields Modifier and Type Field Description private int
expandTableThreshold
private int
hashCode
private java.lang.Object[]
hashTable
(package private) static int
MAX_RUN_MULTIPLIER
We attempt to detect deliberate hash flooding attempts.private int
maxRunBeforeFallback
-
Fields inherited from class com.google.common.collect.ImmutableSet.SetBuilderImpl
dedupedElements, distinct
-
-
Constructor Summary
Constructors Constructor Description RegularSetBuilderImpl(int expectedCapacity)
RegularSetBuilderImpl(ImmutableSet.RegularSetBuilderImpl<E> toCopy)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) ImmutableSet.SetBuilderImpl<E>
add(E e)
Adds e to this SetBuilderImpl, returning the updated result.(package private) ImmutableSet<E>
build()
(package private) ImmutableSet.SetBuilderImpl<E>
copy()
Creates a new copy of this SetBuilderImpl.(package private) void
ensureTableCapacity(int minCapacity)
(package private) static boolean
hashFloodingDetected(java.lang.Object[] hashTable)
Checks the whole hash table for poor hash distribution.private ImmutableSet.SetBuilderImpl<E>
insertInHashTable(E e)
(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.(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.(package private) ImmutableSet.SetBuilderImpl<E>
review()
Call this before build().-
Methods inherited from class com.google.common.collect.ImmutableSet.SetBuilderImpl
addDedupedElement, combine
-
-
-
-
Field Detail
-
hashTable
private java.lang.Object[] hashTable
-
maxRunBeforeFallback
private int maxRunBeforeFallback
-
expandTableThreshold
private int expandTableThreshold
-
hashCode
private int hashCode
-
MAX_RUN_MULTIPLIER
static final int MAX_RUN_MULTIPLIER
We attempt to detect deliberate hash flooding attempts. If one is detected, we fall back to a wrapper around j.u.HashSet, which has built in flooding protection. MAX_RUN_MULTIPLIER was determined experimentally to match our desired probability of false positives.- See Also:
- Constant Field Values
-
-
Constructor Detail
-
RegularSetBuilderImpl
RegularSetBuilderImpl(int expectedCapacity)
-
RegularSetBuilderImpl
RegularSetBuilderImpl(ImmutableSet.RegularSetBuilderImpl<E> toCopy)
-
-
Method Detail
-
add
ImmutableSet.SetBuilderImpl<E> add(E e)
Description copied from class:ImmutableSet.SetBuilderImpl
Adds e to this SetBuilderImpl, returning the updated result. Only use the returned SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected.- Specified by:
add
in classImmutableSet.SetBuilderImpl<E>
-
insertInHashTable
private ImmutableSet.SetBuilderImpl<E> insertInHashTable(E e)
-
copy
ImmutableSet.SetBuilderImpl<E> copy()
Description copied from class:ImmutableSet.SetBuilderImpl
Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build().- Specified by:
copy
in classImmutableSet.SetBuilderImpl<E>
-
review
ImmutableSet.SetBuilderImpl<E> review()
Description copied from class:ImmutableSet.SetBuilderImpl
Call this before build(). Does a final check on the internal data structures, e.g. shrinking unnecessarily large structures or detecting previously unnoticed hash flooding.- Overrides:
review
in classImmutableSet.SetBuilderImpl<E>
-
build
ImmutableSet<E> build()
- Specified by:
build
in classImmutableSet.SetBuilderImpl<E>
-
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.
-
ensureTableCapacity
void ensureTableCapacity(int minCapacity)
-
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
even on truly random input, butImmutableSetTest
tests that the probability of that is low.
-
maxRunBeforeFallback
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.)
-
-