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