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