Class ImmutableSet.RegularSetBuilderImpl<E>
- Enclosing class:
ImmutableSet<E>
This implementation attempts to detect hash flooding, and if it's identified, falls back to JdkBackedSetBuilderImpl.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
private int
private Object[]
(package private) static final int
We attempt to detect deliberate hash flooding attempts.private int
Fields inherited from class com.google.common.collect.ImmutableSet.SetBuilderImpl
dedupedElements, distinct
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) ImmutableSet.SetBuilderImpl
<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
(Object[] hashTable) Checks the whole hash table for poor hash distribution.private ImmutableSet.SetBuilderImpl
<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 Object[]
rebuildHashTable
(int newTableSize, 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 Details
-
hashTable
-
maxRunBeforeFallback
private int maxRunBeforeFallback -
expandTableThreshold
private int expandTableThreshold -
hashCode
private int hashCode -
MAX_RUN_MULTIPLIER
static final int MAX_RUN_MULTIPLIERWe 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:
-
-
Constructor Details
-
RegularSetBuilderImpl
RegularSetBuilderImpl(int expectedCapacity) -
RegularSetBuilderImpl
RegularSetBuilderImpl(ImmutableSet.RegularSetBuilderImpl<E> toCopy)
-
-
Method Details
-
add
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
-
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
Builds a new open-addressed hash table from the first n objects in elements. -
ensureTableCapacity
void ensureTableCapacity(int minCapacity) -
hashFloodingDetected
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.)
-