private static final class ImmutableSet.RegularSetBuilderImpl<E> extends ImmutableSet.SetBuilderImpl<E>
This implementation attempts to detect hash flooding, and if it's identified, falls back to JdkBackedSetBuilderImpl.
Modifier and Type | Field and 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 |
dedupedElements, distinct
Constructor and Description |
---|
RegularSetBuilderImpl(ImmutableSet.RegularSetBuilderImpl<E> toCopy) |
RegularSetBuilderImpl(int expectedCapacity) |
Modifier and Type | Method and 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().
|
addDedupedElement, combine
private java.lang.Object[] hashTable
private int maxRunBeforeFallback
private int expandTableThreshold
private int hashCode
static final int MAX_RUN_MULTIPLIER
RegularSetBuilderImpl(int expectedCapacity)
RegularSetBuilderImpl(ImmutableSet.RegularSetBuilderImpl<E> toCopy)
ImmutableSet.SetBuilderImpl<E> add(E e)
ImmutableSet.SetBuilderImpl
add
in class ImmutableSet.SetBuilderImpl<E>
private ImmutableSet.SetBuilderImpl<E> insertInHashTable(E e)
ImmutableSet.SetBuilderImpl<E> copy()
ImmutableSet.SetBuilderImpl
copy
in class ImmutableSet.SetBuilderImpl<E>
ImmutableSet.SetBuilderImpl<E> review()
ImmutableSet.SetBuilderImpl
review
in class ImmutableSet.SetBuilderImpl<E>
ImmutableSet<E> build()
build
in class ImmutableSet.SetBuilderImpl<E>
static java.lang.Object[] rebuildHashTable(int newTableSize, java.lang.Object[] elements, int n)
void ensureTableCapacity(int minCapacity)
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)
This method may return true
even on truly random input, but ImmutableSetTest
tests that the probability of that is low.
static int maxRunBeforeFallback(int tableSize)
hashFloodingDetected(java.lang.Object[])
may also report hash flooding
if fewer consecutive positions are filled; see that method for details.)