Class 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 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
    • Method Detail

      • 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, 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.)