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 Details

    • hashTable

      @CheckForNull private 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:
  • Constructor Details

  • 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 class ImmutableSet.SetBuilderImpl<E>
    • insertInHashTable

      private ImmutableSet.SetBuilderImpl<E> insertInHashTable(E 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 class 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 class ImmutableSet.SetBuilderImpl<E>
    • build

      ImmutableSet<E> build()
      Specified by:
      build in class ImmutableSet.SetBuilderImpl<E>
    • rebuildHashTable

      static Object[] rebuildHashTable(int newTableSize, 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(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, but ImmutableSetTest 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.)