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    } else if (object instanceof ImmutableSet
314        && isHashCodeFast()
315        && ((ImmutableSet<?>) object).isHashCodeFast()
316        && hashCode() != object.hashCode()) {
317      return false;
318    }
319    return Sets.equalsImpl(this, object);
320  }
321
322  @Override
323  public int hashCode() {
324    return Sets.hashCodeImpl(this);
325  }
326
327  // This declaration is needed to make Set.iterator() and
328  // ImmutableCollection.iterator() consistent.
329  @Override
330  public abstract UnmodifiableIterator<E> iterator();
331
332  @LazyInit @RetainedWith private transient @Nullable ImmutableList<E> asList;
333
334  @Override
335  public ImmutableList<E> asList() {
336    ImmutableList<E> result = asList;
337    return (result == null) ? asList = createAsList() : result;
338  }
339
340  ImmutableList<E> createAsList() {
341    return new RegularImmutableAsList<E>(this, toArray());
342  }
343
344  abstract static class Indexed<E> extends ImmutableSet<E> {
345    abstract E get(int index);
346
347    @Override
348    public UnmodifiableIterator<E> iterator() {
349      return asList().iterator();
350    }
351
352    @Override
353    public Spliterator<E> spliterator() {
354      return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get);
355    }
356
357    @Override
358    public void forEach(Consumer<? super E> consumer) {
359      checkNotNull(consumer);
360      int n = size();
361      for (int i = 0; i < n; i++) {
362        consumer.accept(get(i));
363      }
364    }
365
366    @Override
367    int copyIntoArray(Object[] dst, int offset) {
368      return asList().copyIntoArray(dst, offset);
369    }
370
371    @Override
372    ImmutableList<E> createAsList() {
373      return new ImmutableAsList<E>() {
374        @Override
375        public E get(int index) {
376          return Indexed.this.get(index);
377        }
378
379        @Override
380        Indexed<E> delegateCollection() {
381          return Indexed.this;
382        }
383      };
384    }
385  }
386
387  /*
388   * This class is used to serialize all ImmutableSet instances, except for
389   * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
390   * captures their "logical contents" and they are reconstructed using public
391   * static factories. This is necessary to ensure that the existence of a
392   * particular implementation type is an implementation detail.
393   */
394  private static class SerializedForm implements Serializable {
395    final Object[] elements;
396
397    SerializedForm(Object[] elements) {
398      this.elements = elements;
399    }
400
401    Object readResolve() {
402      return copyOf(elements);
403    }
404
405    private static final long serialVersionUID = 0;
406  }
407
408  @Override
409  Object writeReplace() {
410    return new SerializedForm(toArray());
411  }
412
413  /**
414   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
415   * Builder} constructor.
416   */
417  public static <E> Builder<E> builder() {
418    return new Builder<E>();
419  }
420
421  /**
422   * Returns a new builder, expecting the specified number of distinct elements to be added.
423   *
424   * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder
425   * before {@link Builder#build} is called, the builder is likely to perform better than an unsized
426   * {@link #builder()} would have.
427   *
428   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
429   * but not exactly, the number of distinct elements added to the builder.
430   *
431   * @since 23.1
432   */
433  @Beta
434  public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
435    checkNonnegative(expectedSize, "expectedSize");
436    return new Builder<E>(expectedSize);
437  }
438
439  /** Builds a new open-addressed hash table from the first n objects in elements. */
440  static Object[] rebuildHashTable(int newTableSize, Object[] elements, int n) {
441    Object[] hashTable = new Object[newTableSize];
442    int mask = hashTable.length - 1;
443    for (int i = 0; i < n; i++) {
444      Object e = elements[i];
445      int j0 = Hashing.smear(e.hashCode());
446      for (int j = j0; ; j++) {
447        int index = j & mask;
448        if (hashTable[index] == null) {
449          hashTable[index] = e;
450          break;
451        }
452      }
453    }
454    return hashTable;
455  }
456
457  /**
458   * A builder for creating {@code ImmutableSet} instances. Example:
459   *
460   * <pre>{@code
461   * static final ImmutableSet<Color> GOOGLE_COLORS =
462   *     ImmutableSet.<Color>builder()
463   *         .addAll(WEBSAFE_COLORS)
464   *         .add(new Color(0, 191, 255))
465   *         .build();
466   * }</pre>
467   *
468   * <p>Elements appear in the resulting set in the same order they were first added to the builder.
469   *
470   * <p>Building does not change the state of the builder, so it is still possible to add more
471   * elements and to build again.
472   *
473   * @since 2.0
474   */
475  public static class Builder<E> extends ImmutableCollection.Builder<E> {
476    private SetBuilderImpl<E> impl;
477    boolean forceCopy;
478
479    public Builder() {
480      this(DEFAULT_INITIAL_CAPACITY);
481    }
482
483    Builder(int capacity) {
484      impl = new RegularSetBuilderImpl<E>(capacity);
485    }
486
487    Builder(@SuppressWarnings("unused") boolean subclass) {
488      this.impl = null; // unused
489    }
490
491    @VisibleForTesting
492    void forceJdk() {
493      this.impl = new JdkBackedSetBuilderImpl<E>(impl);
494    }
495
496    final void copyIfNecessary() {
497      if (forceCopy) {
498        copy();
499        forceCopy = false;
500      }
501    }
502
503    void copy() {
504      impl = impl.copy();
505    }
506
507    @Override
508    @CanIgnoreReturnValue
509    public Builder<E> add(E element) {
510      checkNotNull(element);
511      copyIfNecessary();
512      impl = impl.add(element);
513      return this;
514    }
515
516    @Override
517    @CanIgnoreReturnValue
518    public Builder<E> add(E... elements) {
519      super.add(elements);
520      return this;
521    }
522
523    @Override
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    @CanIgnoreReturnValue
533    public Builder<E> addAll(Iterable<? extends E> elements) {
534      super.addAll(elements);
535      return this;
536    }
537
538    @Override
539    @CanIgnoreReturnValue
540    public Builder<E> addAll(Iterator<? extends E> elements) {
541      super.addAll(elements);
542      return this;
543    }
544
545    Builder<E> combine(Builder<E> other) {
546      copyIfNecessary();
547      this.impl = this.impl.combine(other.impl);
548      return this;
549    }
550
551    @Override
552    public ImmutableSet<E> build() {
553      forceCopy = true;
554      impl = impl.review();
555      return impl.build();
556    }
557  }
558
559  /** Swappable internal implementation of an ImmutableSet.Builder. */
560  private abstract static class SetBuilderImpl<E> {
561    E[] dedupedElements;
562    int distinct;
563
564    @SuppressWarnings("unchecked")
565    SetBuilderImpl(int expectedCapacity) {
566      this.dedupedElements = (E[]) new Object[expectedCapacity];
567      this.distinct = 0;
568    }
569
570    /** Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. */
571    SetBuilderImpl(SetBuilderImpl<E> toCopy) {
572      this.dedupedElements = Arrays.copyOf(toCopy.dedupedElements, toCopy.dedupedElements.length);
573      this.distinct = toCopy.distinct;
574    }
575
576    /**
577     * Resizes internal data structures if necessary to store the specified number of distinct
578     * elements.
579     */
580    private void ensureCapacity(int minCapacity) {
581      if (minCapacity > dedupedElements.length) {
582        int newCapacity =
583            ImmutableCollection.Builder.expandedCapacity(dedupedElements.length, minCapacity);
584        dedupedElements = Arrays.copyOf(dedupedElements, newCapacity);
585      }
586    }
587
588    /** Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. */
589    final void addDedupedElement(E e) {
590      ensureCapacity(distinct + 1);
591      dedupedElements[distinct++] = e;
592    }
593
594    /**
595     * Adds e to this SetBuilderImpl, returning the updated result. Only use the returned
596     * SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected.
597     */
598    abstract SetBuilderImpl<E> add(E e);
599
600    /** Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. */
601    final SetBuilderImpl<E> combine(SetBuilderImpl<E> other) {
602      SetBuilderImpl<E> result = this;
603      for (int i = 0; i < other.distinct; i++) {
604        result = result.add(other.dedupedElements[i]);
605      }
606      return result;
607    }
608
609    /**
610     * Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not
611     * affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build().
612     */
613    abstract SetBuilderImpl<E> copy();
614
615    /**
616     * Call this before build(). Does a final check on the internal data structures, e.g. shrinking
617     * unnecessarily large structures or detecting previously unnoticed hash flooding.
618     */
619    SetBuilderImpl<E> review() {
620      return this;
621    }
622
623    abstract ImmutableSet<E> build();
624  }
625
626  // We use power-of-2 tables, and this is the highest int that's a power of 2
627  static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
628
629  // Represents how tightly we can pack things, as a maximum.
630  private static final double DESIRED_LOAD_FACTOR = 0.7;
631
632  // If the set has this many elements, it will "max out" the table size
633  private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
634
635  /**
636   * Returns an array size suitable for the backing array of a hash table that uses open addressing
637   * with linear probing in its implementation. The returned size is the smallest power of two that
638   * can hold setSize elements with the desired load factor. Always returns at least setSize + 2.
639   */
640  @VisibleForTesting
641  static int chooseTableSize(int setSize) {
642    setSize = Math.max(setSize, 2);
643    // Correct the size for open addressing to match desired load factor.
644    if (setSize < CUTOFF) {
645      // Round up to the next highest power of 2.
646      int tableSize = Integer.highestOneBit(setSize - 1) << 1;
647      while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
648        tableSize <<= 1;
649      }
650      return tableSize;
651    }
652
653    // The table can't be completely full or we'll get infinite reprobes
654    checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
655    return MAX_TABLE_SIZE;
656  }
657
658  /**
659   * We attempt to detect deliberate hash flooding attempts, and if one is detected, fall back to a
660   * wrapper around j.u.HashSet, which has built in flooding protection. HASH_FLOODING_FPP is the
661   * maximum allowed probability of falsely detecting a hash flooding attack if the input is
662   * randomly generated.
663   *
664   * <p>MAX_RUN_MULTIPLIER was determined experimentally to match this FPP.
665   */
666  static final double HASH_FLOODING_FPP = 0.001;
667
668  // NB: yes, this is surprisingly high, but that's what the experiments said was necessary
669  // The higher it is, the worse constant factors we are willing to accept.
670  static final int MAX_RUN_MULTIPLIER = 13;
671
672  /**
673   * Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n / log
674   * n) on average.
675   *
676   * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many exactly
677   * matching hash codes, which would cause construction to take O(n^2), but can't detect e.g. hash
678   * codes adversarially designed to go into ascending table locations, which keeps construction
679   * O(n) (as desired) but then can have O(n) queries later.
680   *
681   * <p>If this returns false, then no query can take more than O(log n).
682   *
683   * <p>Note that for a RegularImmutableSet with elements with truly random hash codes, contains
684   * operations take expected O(1) time but with high probability take O(log n) for at least some
685   * element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis)
686   *
687   * <p>This method may return {@code true} up to {@link #HASH_FLOODING_FPP} of the time even on
688   * truly random input.
689   *
690   * <p>If this method returns false, there are definitely no runs of length at least {@code
691   * maxRunBeforeFallback(hashTable.length)} nonnull elements. If there are no runs of length at
692   * least {@code maxRunBeforeFallback(hashTable.length) / 2} nonnull elements, this method
693   * definitely returns false. In between those constraints, the result of this method is undefined,
694   * subject to the above {@link #HASH_FLOODING_FPP} constraint.
695   */
696  static boolean hashFloodingDetected(Object[] hashTable) {
697    int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length);
698
699    // Test for a run wrapping around the end of the table of length at least maxRunBeforeFallback.
700    int endOfStartRun;
701    for (endOfStartRun = 0; endOfStartRun < hashTable.length; ) {
702      if (hashTable[endOfStartRun] == null) {
703        break;
704      }
705      endOfStartRun++;
706      if (endOfStartRun > maxRunBeforeFallback) {
707        return true;
708      }
709    }
710    int startOfEndRun;
711    for (startOfEndRun = hashTable.length - 1; startOfEndRun > endOfStartRun; startOfEndRun--) {
712      if (hashTable[startOfEndRun] == null) {
713        break;
714      }
715      if (endOfStartRun + (hashTable.length - 1 - startOfEndRun) > maxRunBeforeFallback) {
716        return true;
717      }
718    }
719
720    // Now, break the remainder of the table into blocks of maxRunBeforeFallback/2 elements and
721    // check that each has at least one null.
722    int testBlockSize = maxRunBeforeFallback / 2;
723    blockLoop:
724    for (int i = endOfStartRun + 1; i + testBlockSize <= startOfEndRun; i += testBlockSize) {
725      for (int j = 0; j < testBlockSize; j++) {
726        if (hashTable[i + j] == null) {
727          continue blockLoop;
728        }
729      }
730      return true;
731    }
732    return false;
733  }
734
735  /**
736   * If more than this many consecutive positions are filled in a table of the specified size,
737   * report probable hash flooding. ({@link #hashFloodingDetected} may also report hash flooding if
738   * fewer consecutive positions are filled; see that method for details.)
739   */
740  private static int maxRunBeforeFallback(int tableSize) {
741    return MAX_RUN_MULTIPLIER * IntMath.log2(tableSize, RoundingMode.UNNECESSARY);
742  }
743
744  /**
745   * Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash
746   * table and deduplicating elements as they come, so it only allocates O(max(distinct,
747   * expectedCapacity)) rather than O(calls to add).
748   *
749   * <p>This implementation attempts to detect hash flooding, and if it's identified, falls back to
750   * JdkBackedSetBuilderImpl.
751   */
752  private static final class RegularSetBuilderImpl<E> extends SetBuilderImpl<E> {
753    private Object[] hashTable;
754    private int maxRunBeforeFallback;
755    private int expandTableThreshold;
756    private int hashCode;
757
758    RegularSetBuilderImpl(int expectedCapacity) {
759      super(expectedCapacity);
760      int tableSize = chooseTableSize(expectedCapacity);
761      this.hashTable = new Object[tableSize];
762      this.maxRunBeforeFallback = maxRunBeforeFallback(tableSize);
763      this.expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * tableSize);
764    }
765
766    RegularSetBuilderImpl(RegularSetBuilderImpl<E> toCopy) {
767      super(toCopy);
768      this.hashTable = Arrays.copyOf(toCopy.hashTable, toCopy.hashTable.length);
769      this.maxRunBeforeFallback = toCopy.maxRunBeforeFallback;
770      this.expandTableThreshold = toCopy.expandTableThreshold;
771      this.hashCode = toCopy.hashCode;
772    }
773
774    void ensureTableCapacity(int minCapacity) {
775      if (minCapacity > expandTableThreshold && hashTable.length < MAX_TABLE_SIZE) {
776        int newTableSize = hashTable.length * 2;
777        hashTable = rebuildHashTable(newTableSize, dedupedElements, distinct);
778        maxRunBeforeFallback = maxRunBeforeFallback(newTableSize);
779        expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * newTableSize);
780      }
781    }
782
783    @Override
784    SetBuilderImpl<E> add(E e) {
785      checkNotNull(e);
786      int eHash = e.hashCode();
787      int i0 = Hashing.smear(eHash);
788      int mask = hashTable.length - 1;
789      for (int i = i0; i - i0 < maxRunBeforeFallback; i++) {
790        int index = i & mask;
791        Object tableEntry = hashTable[index];
792        if (tableEntry == null) {
793          addDedupedElement(e);
794          hashTable[index] = e;
795          hashCode += eHash;
796          ensureTableCapacity(distinct); // rebuilds table if necessary
797          return this;
798        } else if (tableEntry.equals(e)) { // not a new element, ignore
799          return this;
800        }
801      }
802      // we fell out of the loop due to a long run; fall back to JDK impl
803      return new JdkBackedSetBuilderImpl<E>(this).add(e);
804    }
805
806    @Override
807    SetBuilderImpl<E> copy() {
808      return new RegularSetBuilderImpl<E>(this);
809    }
810
811    @Override
812    SetBuilderImpl<E> review() {
813      int targetTableSize = chooseTableSize(distinct);
814      if (targetTableSize * 2 < hashTable.length) {
815        hashTable = rebuildHashTable(targetTableSize, dedupedElements, distinct);
816      }
817      return hashFloodingDetected(hashTable) ? new JdkBackedSetBuilderImpl<E>(this) : this;
818    }
819
820    @Override
821    ImmutableSet<E> build() {
822      switch (distinct) {
823        case 0:
824          return of();
825        case 1:
826          return of(dedupedElements[0]);
827        default:
828          Object[] elements =
829              (distinct == dedupedElements.length)
830                  ? dedupedElements
831                  : Arrays.copyOf(dedupedElements, distinct);
832          return new RegularImmutableSet<E>(elements, hashCode, hashTable, hashTable.length - 1);
833      }
834    }
835  }
836
837  /**
838   * SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection.
839   */
840  private static final class JdkBackedSetBuilderImpl<E> extends SetBuilderImpl<E> {
841    private final Set<Object> delegate;
842
843    JdkBackedSetBuilderImpl(SetBuilderImpl<E> toCopy) {
844      super(toCopy); // initializes dedupedElements and distinct
845      delegate = Sets.newHashSetWithExpectedSize(distinct);
846      for (int i = 0; i < distinct; i++) {
847        delegate.add(dedupedElements[i]);
848      }
849    }
850
851    @Override
852    SetBuilderImpl<E> add(E e) {
853      checkNotNull(e);
854      if (delegate.add(e)) {
855        addDedupedElement(e);
856      }
857      return this;
858    }
859
860    @Override
861    SetBuilderImpl<E> copy() {
862      return new JdkBackedSetBuilderImpl<>(this);
863    }
864
865    @Override
866    ImmutableSet<E> build() {
867      switch (distinct) {
868        case 0:
869          return of();
870        case 1:
871          return of(dedupedElements[0]);
872        default:
873          return new JdkBackedImmutableSet<E>(
874              delegate, ImmutableList.asImmutableList(dedupedElements, distinct));
875      }
876    }
877  }
878}