001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.collect.CollectPreconditions.checkNonnegative;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.VisibleForTesting;
026import com.google.common.math.IntMath;
027import com.google.common.primitives.Ints;
028import com.google.errorprone.annotations.CanIgnoreReturnValue;
029import com.google.errorprone.annotations.concurrent.LazyInit;
030import com.google.j2objc.annotations.RetainedWith;
031import java.io.Serializable;
032import java.math.RoundingMode;
033import java.util.Arrays;
034import java.util.Collection;
035import java.util.Collections;
036import java.util.EnumSet;
037import java.util.Iterator;
038import java.util.Set;
039import java.util.SortedSet;
040import java.util.Spliterator;
041import java.util.function.Consumer;
042import java.util.stream.Collector;
043import org.checkerframework.checker.nullness.qual.Nullable;
044
045/**
046 * A {@link Set} whose contents will never change, with many other important properties detailed at
047 * {@link ImmutableCollection}.
048 *
049 * @since 2.0
050 */
051@GwtCompatible(serializable = true, emulated = true)
052@SuppressWarnings("serial") // we're overriding default serialization
053public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> {
054  static final int SPLITERATOR_CHARACTERISTICS =
055      ImmutableCollection.SPLITERATOR_CHARACTERISTICS | Spliterator.DISTINCT;
056
057  /**
058   * Returns a {@code Collector} that accumulates the input elements into a new {@code
059   * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if
060   * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first
061   * duplicate in encounter order will appear in the result.
062   *
063   * @since 21.0
064   */
065  public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
066    return CollectCollectors.toImmutableSet();
067  }
068
069  /**
070   * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code
071   * consistency, and because the return type conveys the immutability guarantee.
072   */
073  @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es)
074  public static <E> ImmutableSet<E> of() {
075    return (ImmutableSet<E>) RegularImmutableSet.EMPTY;
076  }
077
078  /**
079   * Returns an immutable set containing {@code element}. Preferred over {@link
080   * Collections#singleton} for code consistency, {@code null} rejection, and because the return
081   * type conveys the immutability guarantee.
082   */
083  public static <E> ImmutableSet<E> of(E element) {
084    return new SingletonImmutableSet<E>(element);
085  }
086
087  /**
088   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
089   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
090   * the first are ignored.
091   */
092  public static <E> ImmutableSet<E> of(E e1, E e2) {
093    return construct(2, e1, e2);
094  }
095
096  /**
097   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
098   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
099   * the first are ignored.
100   */
101  public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
102    return construct(3, e1, e2, e3);
103  }
104
105  /**
106   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
107   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
108   * the first are ignored.
109   */
110  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
111    return construct(4, e1, e2, e3, e4);
112  }
113
114  /**
115   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
116   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
117   * the first are ignored.
118   */
119  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
120    return construct(5, e1, e2, e3, e4, e5);
121  }
122
123  /**
124   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
125   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
126   * the first are ignored.
127   *
128   * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 6}.
129   *
130   * @since 3.0 (source-compatible since 2.0)
131   */
132  @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning.
133  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
134    checkArgument(
135        others.length <= Integer.MAX_VALUE - 6, "the total number of elements must fit in an int");
136    final int paramCount = 6;
137    Object[] elements = new Object[paramCount + others.length];
138    elements[0] = e1;
139    elements[1] = e2;
140    elements[2] = e3;
141    elements[3] = e4;
142    elements[4] = e5;
143    elements[5] = e6;
144    System.arraycopy(others, 0, elements, paramCount, others.length);
145    return construct(elements.length, elements);
146  }
147
148  /**
149   * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. If
150   * {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of {@code
151   * elements} will be in the first {@code k} positions, and {@code elements[i] == null} for {@code
152   * k <= i < n}.
153   *
154   * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code
155   * elements} contains no duplicates, {@code elements} may be used without copying in the returned
156   * {@code ImmutableSet}, in which case it may no longer be modified.
157   *
158   * <p>{@code elements} may contain only values of type {@code E}.
159   *
160   * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null
161   */
162  private static <E> ImmutableSet<E> construct(int n, Object... elements) {
163    switch (n) {
164      case 0:
165        return of();
166      case 1:
167        @SuppressWarnings("unchecked") // safe; elements contains only E's
168        E elem = (E) elements[0];
169        return of(elem);
170      default:
171        SetBuilderImpl<E> builder =
172            new RegularSetBuilderImpl<E>(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
173        for (int i = 0; i < n; i++) {
174          @SuppressWarnings("unchecked")
175          E e = (E) checkNotNull(elements[i]);
176          builder = builder.add(e);
177        }
178        return builder.review().build();
179    }
180  }
181
182  /**
183   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
184   * each appears first in the source collection.
185   *
186   * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
187   * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once.
188   * This reduces the expense of habitually making defensive copies at API boundaries. However, the
189   * precise conditions for skipping the copy operation are undefined.
190   *
191   * @throws NullPointerException if any of {@code elements} is null
192   * @since 7.0 (source-compatible since 2.0)
193   */
194  public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) {
195    /*
196     * TODO(lowasser): consider checking for ImmutableAsList here
197     * TODO(lowasser): consider checking for Multiset here
198     */
199    // Don't refer to ImmutableSortedSet by name so it won't pull in all that code
200    if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) {
201      @SuppressWarnings("unchecked") // all supported methods are covariant
202      ImmutableSet<E> set = (ImmutableSet<E>) elements;
203      if (!set.isPartialView()) {
204        return set;
205      }
206    } else if (elements instanceof EnumSet) {
207      return copyOfEnumSet((EnumSet) elements);
208    }
209    Object[] array = elements.toArray();
210    return construct(array.length, array);
211  }
212
213  /**
214   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
215   * each appears first in the source iterable. This method iterates over {@code elements} only
216   * once.
217   *
218   * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
219   * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only
220   * once. This reduces the expense of habitually making defensive copies at API boundaries.
221   * However, the precise conditions for skipping the copy operation are undefined.
222   *
223   * @throws NullPointerException if any of {@code elements} is null
224   */
225  public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
226    return (elements instanceof Collection)
227        ? copyOf((Collection<? extends E>) elements)
228        : copyOf(elements.iterator());
229  }
230
231  /**
232   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
233   * each appears first in the source iterator.
234   *
235   * @throws NullPointerException if any of {@code elements} is null
236   */
237  public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
238    // We special-case for 0 or 1 elements, but anything further is madness.
239    if (!elements.hasNext()) {
240      return of();
241    }
242    E first = elements.next();
243    if (!elements.hasNext()) {
244      return of(first);
245    } else {
246      return new ImmutableSet.Builder<E>().add(first).addAll(elements).build();
247    }
248  }
249
250  /**
251   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
252   * each appears first in the source array.
253   *
254   * @throws NullPointerException if any of {@code elements} is null
255   * @since 3.0
256   */
257  public static <E> ImmutableSet<E> copyOf(E[] elements) {
258    switch (elements.length) {
259      case 0:
260        return of();
261      case 1:
262        return of(elements[0]);
263      default:
264        return construct(elements.length, elements.clone());
265    }
266  }
267
268  @SuppressWarnings("rawtypes") // necessary to compile against Java 8
269  private static ImmutableSet copyOfEnumSet(EnumSet enumSet) {
270    return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet));
271  }
272
273  ImmutableSet() {}
274
275  /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
276  boolean isHashCodeFast() {
277    return false;
278  }
279
280  @Override
281  public boolean equals(@Nullable Object object) {
282    if (object == this) {
283      return true;
284    } else if (object instanceof ImmutableSet
285        && isHashCodeFast()
286        && ((ImmutableSet<?>) object).isHashCodeFast()
287        && hashCode() != object.hashCode()) {
288      return false;
289    }
290    return Sets.equalsImpl(this, object);
291  }
292
293  @Override
294  public int hashCode() {
295    return Sets.hashCodeImpl(this);
296  }
297
298  // This declaration is needed to make Set.iterator() and
299  // ImmutableCollection.iterator() consistent.
300  @Override
301  public abstract UnmodifiableIterator<E> iterator();
302
303  @LazyInit @RetainedWith private transient @Nullable ImmutableList<E> asList;
304
305  @Override
306  public ImmutableList<E> asList() {
307    ImmutableList<E> result = asList;
308    return (result == null) ? asList = createAsList() : result;
309  }
310
311  ImmutableList<E> createAsList() {
312    return new RegularImmutableAsList<E>(this, toArray());
313  }
314
315  abstract static class Indexed<E> extends ImmutableSet<E> {
316    abstract E get(int index);
317
318    @Override
319    public UnmodifiableIterator<E> iterator() {
320      return asList().iterator();
321    }
322
323    @Override
324    public Spliterator<E> spliterator() {
325      return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get);
326    }
327
328    @Override
329    public void forEach(Consumer<? super E> consumer) {
330      checkNotNull(consumer);
331      int n = size();
332      for (int i = 0; i < n; i++) {
333        consumer.accept(get(i));
334      }
335    }
336
337    @Override
338    int copyIntoArray(Object[] dst, int offset) {
339      return asList().copyIntoArray(dst, offset);
340    }
341
342    @Override
343    ImmutableList<E> createAsList() {
344      return new ImmutableAsList<E>() {
345        @Override
346        public E get(int index) {
347          return Indexed.this.get(index);
348        }
349
350        @Override
351        Indexed<E> delegateCollection() {
352          return Indexed.this;
353        }
354      };
355    }
356  }
357
358  /*
359   * This class is used to serialize all ImmutableSet instances, except for
360   * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
361   * captures their "logical contents" and they are reconstructed using public
362   * static factories. This is necessary to ensure that the existence of a
363   * particular implementation type is an implementation detail.
364   */
365  private static class SerializedForm implements Serializable {
366    final Object[] elements;
367
368    SerializedForm(Object[] elements) {
369      this.elements = elements;
370    }
371
372    Object readResolve() {
373      return copyOf(elements);
374    }
375
376    private static final long serialVersionUID = 0;
377  }
378
379  @Override
380  Object writeReplace() {
381    return new SerializedForm(toArray());
382  }
383
384  /**
385   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
386   * Builder} constructor.
387   */
388  public static <E> Builder<E> builder() {
389    return new Builder<E>();
390  }
391
392  /**
393   * Returns a new builder, expecting the specified number of distinct elements to be added.
394   *
395   * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder
396   * before {@link Builder#build} is called, the builder is likely to perform better than an unsized
397   * {@link #builder()} would have.
398   *
399   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
400   * but not exactly, the number of distinct elements added to the builder.
401   *
402   * @since 23.1
403   */
404  @Beta
405  public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
406    checkNonnegative(expectedSize, "expectedSize");
407    return new Builder<E>(expectedSize);
408  }
409
410  /** Builds a new open-addressed hash table from the first n objects in elements. */
411  static Object[] rebuildHashTable(int newTableSize, Object[] elements, int n) {
412    Object[] hashTable = new Object[newTableSize];
413    int mask = hashTable.length - 1;
414    for (int i = 0; i < n; i++) {
415      Object e = elements[i];
416      int j0 = Hashing.smear(e.hashCode());
417      for (int j = j0; ; j++) {
418        int index = j & mask;
419        if (hashTable[index] == null) {
420          hashTable[index] = e;
421          break;
422        }
423      }
424    }
425    return hashTable;
426  }
427
428  /**
429   * A builder for creating {@code ImmutableSet} instances. Example:
430   *
431   * <pre>{@code
432   * static final ImmutableSet<Color> GOOGLE_COLORS =
433   *     ImmutableSet.<Color>builder()
434   *         .addAll(WEBSAFE_COLORS)
435   *         .add(new Color(0, 191, 255))
436   *         .build();
437   * }</pre>
438   *
439   * <p>Elements appear in the resulting set in the same order they were first added to the builder.
440   *
441   * <p>Building does not change the state of the builder, so it is still possible to add more
442   * elements and to build again.
443   *
444   * @since 2.0
445   */
446  public static class Builder<E> extends ImmutableCollection.Builder<E> {
447    private SetBuilderImpl<E> impl;
448    boolean forceCopy;
449
450    public Builder() {
451      this(DEFAULT_INITIAL_CAPACITY);
452    }
453
454    Builder(int capacity) {
455      impl = new RegularSetBuilderImpl<E>(capacity);
456    }
457
458    Builder(@SuppressWarnings("unused") boolean subclass) {
459      this.impl = null; // unused
460    }
461
462    @VisibleForTesting
463    void forceJdk() {
464      this.impl = new JdkBackedSetBuilderImpl<E>(impl);
465    }
466
467    final void copyIfNecessary() {
468      if (forceCopy) {
469        copy();
470        forceCopy = false;
471      }
472    }
473
474    void copy() {
475      impl = impl.copy();
476    }
477
478    @Override
479    @CanIgnoreReturnValue
480    public Builder<E> add(E element) {
481      checkNotNull(element);
482      copyIfNecessary();
483      impl = impl.add(element);
484      return this;
485    }
486
487    @Override
488    @CanIgnoreReturnValue
489    public Builder<E> add(E... elements) {
490      super.add(elements);
491      return this;
492    }
493
494    @Override
495    /**
496     * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate
497     * elements (only the first duplicate element is added).
498     *
499     * @param elements the elements to add
500     * @return this {@code Builder} object
501     * @throws NullPointerException if {@code elements} is null or contains a null element
502     */
503    @CanIgnoreReturnValue
504    public Builder<E> addAll(Iterable<? extends E> elements) {
505      super.addAll(elements);
506      return this;
507    }
508
509    @Override
510    @CanIgnoreReturnValue
511    public Builder<E> addAll(Iterator<? extends E> elements) {
512      super.addAll(elements);
513      return this;
514    }
515
516    Builder<E> combine(Builder<E> other) {
517      copyIfNecessary();
518      this.impl = this.impl.combine(other.impl);
519      return this;
520    }
521
522    @Override
523    public ImmutableSet<E> build() {
524      forceCopy = true;
525      impl = impl.review();
526      return impl.build();
527    }
528  }
529
530  /** Swappable internal implementation of an ImmutableSet.Builder. */
531  private abstract static class SetBuilderImpl<E> {
532    E[] dedupedElements;
533    int distinct;
534
535    @SuppressWarnings("unchecked")
536    SetBuilderImpl(int expectedCapacity) {
537      this.dedupedElements = (E[]) new Object[expectedCapacity];
538      this.distinct = 0;
539    }
540
541    /** Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. */
542    SetBuilderImpl(SetBuilderImpl<E> toCopy) {
543      this.dedupedElements = Arrays.copyOf(toCopy.dedupedElements, toCopy.dedupedElements.length);
544      this.distinct = toCopy.distinct;
545    }
546
547    /**
548     * Resizes internal data structures if necessary to store the specified number of distinct
549     * elements.
550     */
551    private void ensureCapacity(int minCapacity) {
552      if (minCapacity > dedupedElements.length) {
553        int newCapacity =
554            ImmutableCollection.Builder.expandedCapacity(dedupedElements.length, minCapacity);
555        dedupedElements = Arrays.copyOf(dedupedElements, newCapacity);
556      }
557    }
558
559    /** Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. */
560    final void addDedupedElement(E e) {
561      ensureCapacity(distinct + 1);
562      dedupedElements[distinct++] = e;
563    }
564
565    /**
566     * Adds e to this SetBuilderImpl, returning the updated result. Only use the returned
567     * SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected.
568     */
569    abstract SetBuilderImpl<E> add(E e);
570
571    /** Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. */
572    final SetBuilderImpl<E> combine(SetBuilderImpl<E> other) {
573      SetBuilderImpl<E> result = this;
574      for (int i = 0; i < other.distinct; i++) {
575        result = result.add(other.dedupedElements[i]);
576      }
577      return result;
578    }
579
580    /**
581     * Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not
582     * affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build().
583     */
584    abstract SetBuilderImpl<E> copy();
585
586    /**
587     * Call this before build(). Does a final check on the internal data structures, e.g. shrinking
588     * unnecessarily large structures or detecting previously unnoticed hash flooding.
589     */
590    SetBuilderImpl<E> review() {
591      return this;
592    }
593
594    abstract ImmutableSet<E> build();
595  }
596
597  // We use power-of-2 tables, and this is the highest int that's a power of 2
598  static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
599
600  // Represents how tightly we can pack things, as a maximum.
601  private static final double DESIRED_LOAD_FACTOR = 0.7;
602
603  // If the set has this many elements, it will "max out" the table size
604  private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
605
606  /**
607   * Returns an array size suitable for the backing array of a hash table that uses open addressing
608   * with linear probing in its implementation. The returned size is the smallest power of two that
609   * can hold setSize elements with the desired load factor. Always returns at least setSize + 2.
610   */
611  @VisibleForTesting
612  static int chooseTableSize(int setSize) {
613    setSize = Math.max(setSize, 2);
614    // Correct the size for open addressing to match desired load factor.
615    if (setSize < CUTOFF) {
616      // Round up to the next highest power of 2.
617      int tableSize = Integer.highestOneBit(setSize - 1) << 1;
618      while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
619        tableSize <<= 1;
620      }
621      return tableSize;
622    }
623
624    // The table can't be completely full or we'll get infinite reprobes
625    checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
626    return MAX_TABLE_SIZE;
627  }
628
629  /**
630   * We attempt to detect deliberate hash flooding attempts, and if one is detected, fall back to a
631   * wrapper around j.u.HashSet, which has built in flooding protection. HASH_FLOODING_FPP is the
632   * maximum allowed probability of falsely detecting a hash flooding attack if the input is
633   * randomly generated.
634   *
635   * <p>MAX_RUN_MULTIPLIER was determined experimentally to match this FPP.
636   */
637  static final double HASH_FLOODING_FPP = 0.001;
638
639  // NB: yes, this is surprisingly high, but that's what the experiments said was necessary
640  // The higher it is, the worse constant factors we are willing to accept.
641  static final int MAX_RUN_MULTIPLIER = 13;
642
643  /**
644   * Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n / log
645   * n) on average.
646   *
647   * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many exactly
648   * matching hash codes, which would cause construction to take O(n^2), but can't detect e.g. hash
649   * codes adversarially designed to go into ascending table locations, which keeps construction
650   * O(n) (as desired) but then can have O(n) queries later.
651   *
652   * <p>If this returns false, then no query can take more than O(log n).
653   *
654   * <p>Note that for a RegularImmutableSet with elements with truly random hash codes, contains
655   * operations take expected O(1) time but with high probability take O(log n) for at least some
656   * element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis)
657   *
658   * <p>This method may return {@code true} up to {@link #HASH_FLOODING_FPP} of the time even on
659   * truly random input.
660   *
661   * <p>If this method returns false, there are definitely no runs of length at least {@code
662   * maxRunBeforeFallback(hashTable.length)} nonnull elements. If there are no runs of length at
663   * least {@code maxRunBeforeFallback(hashTable.length) / 2} nonnull elements, this method
664   * definitely returns false. In between those constraints, the result of this method is undefined,
665   * subject to the above {@link #HASH_FLOODING_FPP} constraint.
666   */
667  static boolean hashFloodingDetected(Object[] hashTable) {
668    int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length);
669
670    // Test for a run wrapping around the end of the table of length at least maxRunBeforeFallback.
671    int endOfStartRun;
672    for (endOfStartRun = 0; endOfStartRun < hashTable.length; ) {
673      if (hashTable[endOfStartRun] == null) {
674        break;
675      }
676      endOfStartRun++;
677      if (endOfStartRun > maxRunBeforeFallback) {
678        return true;
679      }
680    }
681    int startOfEndRun;
682    for (startOfEndRun = hashTable.length - 1; startOfEndRun > endOfStartRun; startOfEndRun--) {
683      if (hashTable[startOfEndRun] == null) {
684        break;
685      }
686      if (endOfStartRun + (hashTable.length - 1 - startOfEndRun) > maxRunBeforeFallback) {
687        return true;
688      }
689    }
690
691    // Now, break the remainder of the table into blocks of maxRunBeforeFallback/2 elements and
692    // check that each has at least one null.
693    int testBlockSize = maxRunBeforeFallback / 2;
694    blockLoop:
695    for (int i = endOfStartRun + 1; i + testBlockSize <= startOfEndRun; i += testBlockSize) {
696      for (int j = 0; j < testBlockSize; j++) {
697        if (hashTable[i + j] == null) {
698          continue blockLoop;
699        }
700      }
701      return true;
702    }
703    return false;
704  }
705
706  /**
707   * If more than this many consecutive positions are filled in a table of the specified size,
708   * report probable hash flooding. ({@link #hashFloodingDetected} may also report hash flooding if
709   * fewer consecutive positions are filled; see that method for details.)
710   */
711  private static int maxRunBeforeFallback(int tableSize) {
712    return MAX_RUN_MULTIPLIER * IntMath.log2(tableSize, RoundingMode.UNNECESSARY);
713  }
714
715  /**
716   * Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash
717   * table and deduplicating elements as they come, so it only allocates O(max(distinct,
718   * expectedCapacity)) rather than O(calls to add).
719   *
720   * <p>This implementation attempts to detect hash flooding, and if it's identified, falls back to
721   * JdkBackedSetBuilderImpl.
722   */
723  private static final class RegularSetBuilderImpl<E> extends SetBuilderImpl<E> {
724    private Object[] hashTable;
725    private int maxRunBeforeFallback;
726    private int expandTableThreshold;
727    private int hashCode;
728
729    RegularSetBuilderImpl(int expectedCapacity) {
730      super(expectedCapacity);
731      int tableSize = chooseTableSize(expectedCapacity);
732      this.hashTable = new Object[tableSize];
733      this.maxRunBeforeFallback = maxRunBeforeFallback(tableSize);
734      this.expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * tableSize);
735    }
736
737    RegularSetBuilderImpl(RegularSetBuilderImpl<E> toCopy) {
738      super(toCopy);
739      this.hashTable = Arrays.copyOf(toCopy.hashTable, toCopy.hashTable.length);
740      this.maxRunBeforeFallback = toCopy.maxRunBeforeFallback;
741      this.expandTableThreshold = toCopy.expandTableThreshold;
742      this.hashCode = toCopy.hashCode;
743    }
744
745    void ensureTableCapacity(int minCapacity) {
746      if (minCapacity > expandTableThreshold && hashTable.length < MAX_TABLE_SIZE) {
747        int newTableSize = hashTable.length * 2;
748        hashTable = rebuildHashTable(newTableSize, dedupedElements, distinct);
749        maxRunBeforeFallback = maxRunBeforeFallback(newTableSize);
750        expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * newTableSize);
751      }
752    }
753
754    @Override
755    SetBuilderImpl<E> add(E e) {
756      checkNotNull(e);
757      int eHash = e.hashCode();
758      int i0 = Hashing.smear(eHash);
759      int mask = hashTable.length - 1;
760      for (int i = i0; i - i0 < maxRunBeforeFallback; i++) {
761        int index = i & mask;
762        Object tableEntry = hashTable[index];
763        if (tableEntry == null) {
764          addDedupedElement(e);
765          hashTable[index] = e;
766          hashCode += eHash;
767          ensureTableCapacity(distinct); // rebuilds table if necessary
768          return this;
769        } else if (tableEntry.equals(e)) { // not a new element, ignore
770          return this;
771        }
772      }
773      // we fell out of the loop due to a long run; fall back to JDK impl
774      return new JdkBackedSetBuilderImpl<E>(this).add(e);
775    }
776
777    @Override
778    SetBuilderImpl<E> copy() {
779      return new RegularSetBuilderImpl<E>(this);
780    }
781
782    @Override
783    SetBuilderImpl<E> review() {
784      int targetTableSize = chooseTableSize(distinct);
785      if (targetTableSize * 2 < hashTable.length) {
786        hashTable = rebuildHashTable(targetTableSize, dedupedElements, distinct);
787      }
788      return hashFloodingDetected(hashTable) ? new JdkBackedSetBuilderImpl<E>(this) : this;
789    }
790
791    @Override
792    ImmutableSet<E> build() {
793      switch (distinct) {
794        case 0:
795          return of();
796        case 1:
797          return of(dedupedElements[0]);
798        default:
799          Object[] elements =
800              (distinct == dedupedElements.length)
801                  ? dedupedElements
802                  : Arrays.copyOf(dedupedElements, distinct);
803          return new RegularImmutableSet<E>(elements, hashCode, hashTable, hashTable.length - 1);
804      }
805    }
806  }
807
808  /**
809   * SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection.
810   */
811  private static final class JdkBackedSetBuilderImpl<E> extends SetBuilderImpl<E> {
812    private final Set<Object> delegate;
813
814    JdkBackedSetBuilderImpl(SetBuilderImpl<E> toCopy) {
815      super(toCopy); // initializes dedupedElements and distinct
816      delegate = Sets.newHashSetWithExpectedSize(distinct);
817      for (int i = 0; i < distinct; i++) {
818        delegate.add(dedupedElements[i]);
819      }
820    }
821
822    @Override
823    SetBuilderImpl<E> add(E e) {
824      checkNotNull(e);
825      if (delegate.add(e)) {
826        addDedupedElement(e);
827      }
828      return this;
829    }
830
831    @Override
832    SetBuilderImpl<E> copy() {
833      return new JdkBackedSetBuilderImpl<>(this);
834    }
835
836    @Override
837    ImmutableSet<E> build() {
838      switch (distinct) {
839        case 0:
840          return of();
841        case 1:
842          return of(dedupedElements[0]);
843        default:
844          return new JdkBackedImmutableSet<E>(
845              delegate, ImmutableList.asImmutableList(dedupedElements, distinct));
846      }
847    }
848  }
849}