https://github.com/google/guava/guava: Guava is a suite of core and expanded libraries that include utility classes, google's collections, io classes, and much much more. 
/*
 * Copyright (C) 2007 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.CollectPreconditions.checkNonnegative;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.math.IntMath;
import com.google.common.primitives.Ints;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.errorprone.annotations.concurrent.LazyInit;
import com.google.j2objc.annotations.RetainedWith;
import java.io.Serializable;
import java.math.RoundingMode;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.EnumSet;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedSet;
import java.util.Spliterator;
import java.util.function.Consumer;
import java.util.stream.Collector;
import org.checkerframework.checker.nullness.qual.Nullable;


A Set whose contents will never change, with many other important properties detailed at ImmutableCollection. 
Since:2.0
/**
 * A {@link Set} whose contents will never change, with many other important properties detailed at
 * {@link ImmutableCollection}.
 *
 * @since 2.0
 */
@GwtCompatible(serializable = true, emulated = true)
@SuppressWarnings("serial") // we're overriding default serialization
public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> {
  static final int SPLITERATOR_CHARACTERISTICS =
      ImmutableCollection.SPLITERATOR_CHARACTERISTICS | Spliterator.DISTINCT;

  
Returns a Collector that accumulates the input elements into a new 
ImmutableSet. Elements appear in the resulting set in the encounter order of the stream; if the stream contains duplicates (according to Object.equals(Object)), only the first duplicate in encounter order will appear in the result. 
Since:21.0
/**
   * Returns a {@code Collector} that accumulates the input elements into a new {@code
   * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if
   * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first
   * duplicate in encounter order will appear in the result.
   *
   * @since 21.0
   */
  @Beta
  public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
    return CollectCollectors.toImmutableSet();
  }

  
Returns the empty immutable set. Preferred over Collections.emptySet for code consistency, and because the return type conveys the immutability guarantee. 
/**
   * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code
   * consistency, and because the return type conveys the immutability guarantee.
   */
  @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es)
  public static <E> ImmutableSet<E> of() {
    return (ImmutableSet<E>) RegularImmutableSet.EMPTY;
  }

  
Returns an immutable set containing element. Preferred over Collections.singleton for code consistency, null rejection, and because the return type conveys the immutability guarantee. 
/**
   * Returns an immutable set containing {@code element}. Preferred over {@link
   * Collections#singleton} for code consistency, {@code null} rejection, and because the return
   * type conveys the immutability guarantee.
   */
  public static <E> ImmutableSet<E> of(E element) {
    return new SingletonImmutableSet<E>(element);
  }

  
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored. 
/**
   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
   * the first are ignored.
   */
  public static <E> ImmutableSet<E> of(E e1, E e2) {
    return construct(2, e1, e2);
  }

  
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored. 
/**
   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
   * the first are ignored.
   */
  public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
    return construct(3, e1, e2, e3);
  }

  
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored. 
/**
   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
   * the first are ignored.
   */
  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
    return construct(4, e1, e2, e3, e4);
  }

  
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored. 
/**
   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
   * the first are ignored.
   */
  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
    return construct(5, e1, e2, e3, e4, e5);
  }

  
Returns an immutable set containing the given elements, minus duplicates, in the order each was first specified. That is, if multiple elements are equal, all except the first are ignored. 
The array others must not be longer than Integer.MAX_VALUE - 6. 
Since:3.0 (source-compatible since 2.0)
/**
   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
   * the first are ignored.
   *
   * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 6}.
   *
   * @since 3.0 (source-compatible since 2.0)
   */
  @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning.
  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
    checkArgument(
        others.length <= Integer.MAX_VALUE - 6,
        "the total number of elements must fit in an int");
    final int paramCount = 6;
    Object[] elements = new Object[paramCount + others.length];
    elements[0] = e1;
    elements[1] = e2;
    elements[2] = e3;
    elements[3] = e4;
    elements[4] = e5;
    elements[5] = e6;
    System.arraycopy(others, 0, elements, paramCount, others.length);
    return construct(elements.length, elements);
  }

  
Constructs an ImmutableSet from the first n elements of the specified array. If k is the size of the returned ImmutableSet, then the unique elements of 
elements will be in the first k positions, and elements[i] == null for 
k <= i < n. 
This may modify elements. Additionally, if n == elements.length and 
elements contains no duplicates, elements may be used without copying in the returned ImmutableSet, in which case it may no longer be modified. 
elements may contain only values of type E. 
Throws:
/**
   * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. If
   * {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of {@code
   * elements} will be in the first {@code k} positions, and {@code elements[i] == null} for {@code
   * k <= i < n}.
   *
   * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code
   * elements} contains no duplicates, {@code elements} may be used without copying in the returned
   * {@code ImmutableSet}, in which case it may no longer be modified.
   *
   * <p>{@code elements} may contain only values of type {@code E}.
   *
   * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null
   */
  private static <E> ImmutableSet<E> construct(int n, Object... elements) {
    switch (n) {
      case 0:
        return of();
      case 1:
        @SuppressWarnings("unchecked") // safe; elements contains only E's
        E elem = (E) elements[0];
        return of(elem);
      default:
        SetBuilderImpl<E> builder =
            new RegularSetBuilderImpl<E>(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
        for (int i = 0; i < n; i++) {
          @SuppressWarnings("unchecked")
          E e = (E) checkNotNull(elements[i]);
          builder = builder.add(e);
        }
        return builder.review().build();
    }
  }

  
Returns an immutable set containing each of elements, minus duplicates, in the order each appears first in the source collection. 
Performance note: This method will sometimes recognize that the actual copy operation is unnecessary; for example, copyOf(copyOf(anArrayList)) will copy the data only once. This reduces the expense of habitually making defensive copies at API boundaries. However, the precise conditions for skipping the copy operation are undefined. 
Throws:
Since:7.0 (source-compatible since 2.0)
/**
   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
   * each appears first in the source collection.
   *
   * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
   * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once.
   * This reduces the expense of habitually making defensive copies at API boundaries. However, the
   * precise conditions for skipping the copy operation are undefined.
   *
   * @throws NullPointerException if any of {@code elements} is null
   * @since 7.0 (source-compatible since 2.0)
   */
  public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) {
    /*
     * TODO(lowasser): consider checking for ImmutableAsList here
     * TODO(lowasser): consider checking for Multiset here
     */
    // Don't refer to ImmutableSortedSet by name so it won't pull in all that code
    if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) {
      @SuppressWarnings("unchecked") // all supported methods are covariant
      ImmutableSet<E> set = (ImmutableSet<E>) elements;
      if (!set.isPartialView()) {
        return set;
      }
    } else if (elements instanceof EnumSet) {
      return copyOfEnumSet((EnumSet) elements);
    }
    Object[] array = elements.toArray();
    return construct(array.length, array);
  }

  
Returns an immutable set containing each of elements, minus duplicates, in the order each appears first in the source iterable. This method iterates over elements only once. 
Performance note: This method will sometimes recognize that the actual copy operation is unnecessary; for example, copyOf(copyOf(anArrayList)) should copy the data only once. This reduces the expense of habitually making defensive copies at API boundaries. However, the precise conditions for skipping the copy operation are undefined. 
Throws:
/**
   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
   * each appears first in the source iterable. This method iterates over {@code elements} only
   * once.
   *
   * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
   * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only
   * once. This reduces the expense of habitually making defensive copies at API boundaries.
   * However, the precise conditions for skipping the copy operation are undefined.
   *
   * @throws NullPointerException if any of {@code elements} is null
   */
  public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
    return (elements instanceof Collection)
        ? copyOf((Collection<? extends E>) elements)
        : copyOf(elements.iterator());
  }

  
Returns an immutable set containing each of elements, minus duplicates, in the order each appears first in the source iterator. 
Throws:
/**
   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
   * each appears first in the source iterator.
   *
   * @throws NullPointerException if any of {@code elements} is null
   */
  public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
    // We special-case for 0 or 1 elements, but anything further is madness.
    if (!elements.hasNext()) {
      return of();
    }
    E first = elements.next();
    if (!elements.hasNext()) {
      return of(first);
    } else {
      return new ImmutableSet.Builder<E>().add(first).addAll(elements).build();
    }
  }

  
Returns an immutable set containing each of elements, minus duplicates, in the order each appears first in the source array. 
Throws:
Since:3.0
/**
   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
   * each appears first in the source array.
   *
   * @throws NullPointerException if any of {@code elements} is null
   * @since 3.0
   */
  public static <E> ImmutableSet<E> copyOf(E[] elements) {
    switch (elements.length) {
      case 0:
        return of();
      case 1:
        return of(elements[0]);
      default:
        return construct(elements.length, elements.clone());
    }
  }

  @SuppressWarnings("rawtypes") // necessary to compile against Java 8
  private static ImmutableSet copyOfEnumSet(EnumSet enumSet) {
    return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet));
  }

  ImmutableSet() {}

  
Returns true if the hashCode() method runs quickly. 
/** Returns {@code true} if the {@code hashCode()} method runs quickly. */
  boolean isHashCodeFast() {
    return false;
  }

  @Override
  public boolean equals(@Nullable Object object) {
    if (object == this) {
      return true;
    } else if (object instanceof ImmutableSet
        && isHashCodeFast()
        && ((ImmutableSet<?>) object).isHashCodeFast()
        && hashCode() != object.hashCode()) {
      return false;
    }
    return Sets.equalsImpl(this, object);
  }

  @Override
  public int hashCode() {
    return Sets.hashCodeImpl(this);
  }

  // This declaration is needed to make Set.iterator() and
  // ImmutableCollection.iterator() consistent.
  @Override
  public abstract UnmodifiableIterator<E> iterator();

  @LazyInit @RetainedWith private transient @Nullable ImmutableList<E> asList;

  @Override
  public ImmutableList<E> asList() {
    ImmutableList<E> result = asList;
    return (result == null) ? asList = createAsList() : result;
  }

  ImmutableList<E> createAsList() {
    return new RegularImmutableAsList<E>(this, toArray());
  }

  abstract static class Indexed<E> extends ImmutableSet<E> {
    abstract E get(int index);

    @Override
    public UnmodifiableIterator<E> iterator() {
      return asList().iterator();
    }

    @Override
    public Spliterator<E> spliterator() {
      return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get);
    }

    @Override
    public void forEach(Consumer<? super E> consumer) {
      checkNotNull(consumer);
      int n = size();
      for (int i = 0; i < n; i++) {
        consumer.accept(get(i));
      }
    }

    @Override
    int copyIntoArray(Object[] dst, int offset) {
      return asList().copyIntoArray(dst, offset);
    }

    @Override
    ImmutableList<E> createAsList() {
      return new ImmutableAsList<E>() {
        @Override
        public E get(int index) {
          return Indexed.this.get(index);
        }

        @Override
        Indexed<E> delegateCollection() {
          return Indexed.this;
        }
      };
    }
  }

  /*
   * This class is used to serialize all ImmutableSet instances, except for
   * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
   * captures their "logical contents" and they are reconstructed using public
   * static factories. This is necessary to ensure that the existence of a
   * particular implementation type is an implementation detail.
   */
  private static class SerializedForm implements Serializable {
    final Object[] elements;

    SerializedForm(Object[] elements) {
      this.elements = elements;
    }

    Object readResolve() {
      return copyOf(elements);
    }

    private static final long serialVersionUID = 0;
  }

  @Override
  Object writeReplace() {
    return new SerializedForm(toArray());
  }

  
Returns a new builder. The generated builder is equivalent to the builder created by the Builder constructor. 
/**
   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
   * Builder} constructor.
   */
  public static <E> Builder<E> builder() {
    return new Builder<E>();
  }

  
Returns a new builder, expecting the specified number of distinct elements to be added.

If expectedSize is exactly the number of distinct elements added to the builder before Builder.build is called, the builder is likely to perform better than an unsized builder() would have. 
It is not specified if any performance benefits apply if expectedSize is close to, but not exactly, the number of distinct elements added to the builder. 
Since:23.1
/**
   * Returns a new builder, expecting the specified number of distinct elements to be added.
   *
   * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder
   * before {@link Builder#build} is called, the builder is likely to perform better than an unsized
   * {@link #builder()} would have.
   *
   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
   * but not exactly, the number of distinct elements added to the builder.
   *
   * @since 23.1
   */
  @Beta
  public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
    checkNonnegative(expectedSize, "expectedSize");
    return new Builder<E>(expectedSize);
  }

  
Builds a new open-addressed hash table from the first n objects in elements. 
/** Builds a new open-addressed hash table from the first n objects in elements. */
  static Object[] rebuildHashTable(int newTableSize, Object[] elements, int n) {
    Object[] hashTable = new Object[newTableSize];
    int mask = hashTable.length - 1;
    for (int i = 0; i < n; i++) {
      Object e = elements[i];
      int j0 = Hashing.smear(e.hashCode());
      for (int j = j0; ; j++) {
        int index = j & mask;
        if (hashTable[index] == null) {
          hashTable[index] = e;
          break;
        }
      }
    }
    return hashTable;
  }

  
A builder for creating ImmutableSet instances. Example: 

static final ImmutableSet<Color> GOOGLE_COLORS =
    ImmutableSet.<Color>builder()
        .addAll(WEBSAFE_COLORS)
        .add(new Color(0, 191, 255))
        .build();



Elements appear in the resulting set in the same order they were first added to the builder.

Building does not change the state of the builder, so it is still possible to add more
elements and to build again.

Since:2.0
/**
   * A builder for creating {@code ImmutableSet} instances. Example:
   *
   * <pre>{@code
   * static final ImmutableSet<Color> GOOGLE_COLORS =
   *     ImmutableSet.<Color>builder()
   *         .addAll(WEBSAFE_COLORS)
   *         .add(new Color(0, 191, 255))
   *         .build();
   * }</pre>
   *
   * <p>Elements appear in the resulting set in the same order they were first added to the builder.
   *
   * <p>Building does not change the state of the builder, so it is still possible to add more
   * elements and to build again.
   *
   * @since 2.0
   */
  public static class Builder<E> extends ImmutableCollection.Builder<E> {
    private SetBuilderImpl<E> impl;
    boolean forceCopy;

    public Builder() {
      this(DEFAULT_INITIAL_CAPACITY);
    }

    Builder(int capacity) {
      impl = new RegularSetBuilderImpl<E>(capacity);
    }

    Builder(@SuppressWarnings("unused") boolean subclass) {
      this.impl = null; // unused
    }

    @VisibleForTesting
    void forceJdk() {
      this.impl = new JdkBackedSetBuilderImpl<E>(impl);
    }

    final void copyIfNecessary() {
      if (forceCopy) {
        copy();
        forceCopy = false;
      }
    }

    void copy() {
      impl = impl.copy();
    }

    @Override
    @CanIgnoreReturnValue
    public Builder<E> add(E element) {
      checkNotNull(element);
      copyIfNecessary();
      impl = impl.add(element);
      return this;
    }

    @Override
    @CanIgnoreReturnValue
    public Builder<E> add(E... elements) {
      super.add(elements);
      return this;
    }

    @Override
    /**
     * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate
     * elements (only the first duplicate element is added).
     *
     * @param elements the elements to add
     * @return this {@code Builder} object
     * @throws NullPointerException if {@code elements} is null or contains a null element
     */
    @CanIgnoreReturnValue
    public Builder<E> addAll(Iterable<? extends E> elements) {
      super.addAll(elements);
      return this;
    }

    @Override
    @CanIgnoreReturnValue
    public Builder<E> addAll(Iterator<? extends E> elements) {
      super.addAll(elements);
      return this;
    }

    Builder<E> combine(Builder<E> other) {
      copyIfNecessary();
      this.impl = this.impl.combine(other.impl);
      return this;
    }

    @Override
    public ImmutableSet<E> build() {
      forceCopy = true;
      impl = impl.review();
      return impl.build();
    }
  }

  
Swappable internal implementation of an ImmutableSet.Builder. 
/** Swappable internal implementation of an ImmutableSet.Builder. */
  private abstract static class SetBuilderImpl<E> {
    E[] dedupedElements;
    int distinct;

    @SuppressWarnings("unchecked")
    SetBuilderImpl(int expectedCapacity) {
      this.dedupedElements = (E[]) new Object[expectedCapacity];
      this.distinct = 0;
    }

    
Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. 
/** Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. */
    SetBuilderImpl(SetBuilderImpl<E> toCopy) {
      this.dedupedElements = Arrays.copyOf(toCopy.dedupedElements, toCopy.dedupedElements.length);
      this.distinct = toCopy.distinct;
    }

    
Resizes internal data structures if necessary to store the specified number of distinct
elements.

/**
     * Resizes internal data structures if necessary to store the specified number of distinct
     * elements.
     */
    private void ensureCapacity(int minCapacity) {
      if (minCapacity > dedupedElements.length) {
        int newCapacity =
            ImmutableCollection.Builder.expandedCapacity(dedupedElements.length, minCapacity);
        dedupedElements = Arrays.copyOf(dedupedElements, newCapacity);
      }
    }

    
Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. 
/** Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. */
    final void addDedupedElement(E e) {
      ensureCapacity(distinct + 1);
      dedupedElements[distinct++] = e;
    }

    
Adds e to this SetBuilderImpl, returning the updated result. Only use the returned
SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected.

/**
     * Adds e to this SetBuilderImpl, returning the updated result. Only use the returned
     * SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected.
     */
    abstract SetBuilderImpl<E> add(E e);

    
Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. 
/** Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. */
    final SetBuilderImpl<E> combine(SetBuilderImpl<E> other) {
      SetBuilderImpl<E> result = this;
      for (int i = 0; i < other.distinct; i++) {
        result = result.add(other.dedupedElements[i]);
      }
      return result;
    }

    
Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not
affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build().

/**
     * Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not
     * affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build().
     */
    abstract SetBuilderImpl<E> copy();

    
Call this before build(). Does a final check on the internal data structures, e.g. shrinking
unnecessarily large structures or detecting previously unnoticed hash flooding.

/**
     * Call this before build(). Does a final check on the internal data structures, e.g. shrinking
     * unnecessarily large structures or detecting previously unnoticed hash flooding.
     */
    SetBuilderImpl<E> review() {
      return this;
    }

    abstract ImmutableSet<E> build();
  }

  // We use power-of-2 tables, and this is the highest int that's a power of 2
  static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;

  // Represents how tightly we can pack things, as a maximum.
  private static final double DESIRED_LOAD_FACTOR = 0.7;

  // If the set has this many elements, it will "max out" the table size
  private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);

  
Returns an array size suitable for the backing array of a hash table that uses open addressing
with linear probing in its implementation. The returned size is the smallest power of two that
can hold setSize elements with the desired load factor. Always returns at least setSize + 2.

/**
   * Returns an array size suitable for the backing array of a hash table that uses open addressing
   * with linear probing in its implementation. The returned size is the smallest power of two that
   * can hold setSize elements with the desired load factor. Always returns at least setSize + 2.
   */
  @VisibleForTesting
  static int chooseTableSize(int setSize) {
    setSize = Math.max(setSize, 2);
    // Correct the size for open addressing to match desired load factor.
    if (setSize < CUTOFF) {
      // Round up to the next highest power of 2.
      int tableSize = Integer.highestOneBit(setSize - 1) << 1;
      while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
        tableSize <<= 1;
      }
      return tableSize;
    }

    // The table can't be completely full or we'll get infinite reprobes
    checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
    return MAX_TABLE_SIZE;
  }

  
We attempt to detect deliberate hash flooding attempts, and if one is detected, fall back to a
wrapper around j.u.HashSet, which has built in flooding protection. HASH_FLOODING_FPP is the
maximum allowed probability of falsely detecting a hash flooding attack if the input is
randomly generated.

MAX_RUN_MULTIPLIER was determined experimentally to match this FPP.

/**
   * We attempt to detect deliberate hash flooding attempts, and if one is detected, fall back to a
   * wrapper around j.u.HashSet, which has built in flooding protection. HASH_FLOODING_FPP is the
   * maximum allowed probability of falsely detecting a hash flooding attack if the input is
   * randomly generated.
   *
   * <p>MAX_RUN_MULTIPLIER was determined experimentally to match this FPP.
   */
  static final double HASH_FLOODING_FPP = 0.001;

  // NB: yes, this is surprisingly high, but that's what the experiments said was necessary
  static final int MAX_RUN_MULTIPLIER = 12;

  
Checks the whole hash table for poor hash distribution. Takes O(n).

The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many exactly
matching hash codes, which would cause construction to take O(n^2), but can't detect e.g. hash
codes adversarially designed to go into ascending table locations, which keeps construction
O(n) (as desired) but then can have O(n) queries later.

If this returns false, then no query can take more than O(log n).

Note that for a RegularImmutableSet with elements with truly random hash codes, contains
operations take expected O(1) time but with high probability take O(log n) for at least some
element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis)

/**
   * Checks the whole hash table for poor hash distribution. Takes O(n).
   *
   * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many exactly
   * matching hash codes, which would cause construction to take O(n^2), but can't detect e.g. hash
   * codes adversarially designed to go into ascending table locations, which keeps construction
   * O(n) (as desired) but then can have O(n) queries later.
   *
   * <p>If this returns false, then no query can take more than O(log n).
   *
   * <p>Note that for a RegularImmutableSet with elements with truly random hash codes, contains
   * operations take expected O(1) time but with high probability take O(log n) for at least some
   * element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis)
   */
  static boolean hashFloodingDetected(Object[] hashTable) {
    int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length);

    // Test for a run wrapping around the end of the table, then check for runs in the middle.
    int endOfStartRun;
    for (endOfStartRun = 0; endOfStartRun < hashTable.length; ) {
      if (hashTable[endOfStartRun] == null) {
        break;
      }
      endOfStartRun++;
      if (endOfStartRun > maxRunBeforeFallback) {
        return true;
      }
    }
    int startOfEndRun;
    for (startOfEndRun = hashTable.length - 1; startOfEndRun > endOfStartRun; startOfEndRun--) {
      if (hashTable[startOfEndRun] == null) {
        break;
      }
      if (endOfStartRun + (hashTable.length - 1 - startOfEndRun) > maxRunBeforeFallback) {
        return true;
      }
    }
    for (int i = endOfStartRun + 1; i < startOfEndRun; i++) {
      for (int runLength = 0; i < startOfEndRun && hashTable[i] != null; i++) {
        runLength++;
        if (runLength > maxRunBeforeFallback) {
          return true;
        }
      }
    }
    return false;
  }

  
If more than this many consecutive positions are filled in a table of the specified size,
report probable hash flooding.

/**
   * If more than this many consecutive positions are filled in a table of the specified size,
   * report probable hash flooding.
   */
  static int maxRunBeforeFallback(int tableSize) {
    return MAX_RUN_MULTIPLIER * IntMath.log2(tableSize, RoundingMode.UNNECESSARY);
  }

  
Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash
table and deduplicating elements as they come, so it only allocates O(max(distinct,
expectedCapacity)) rather than O(calls to add).

This implementation attempts to detect hash flooding, and if it's identified, falls back to
JdkBackedSetBuilderImpl.

/**
   * Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash
   * table and deduplicating elements as they come, so it only allocates O(max(distinct,
   * expectedCapacity)) rather than O(calls to add).
   *
   * <p>This implementation attempts to detect hash flooding, and if it's identified, falls back to
   * JdkBackedSetBuilderImpl.
   */
  private static final class RegularSetBuilderImpl<E> extends SetBuilderImpl<E> {
    private Object[] hashTable;
    private int maxRunBeforeFallback;
    private int expandTableThreshold;
    private int hashCode;

    RegularSetBuilderImpl(int expectedCapacity) {
      super(expectedCapacity);
      int tableSize = chooseTableSize(expectedCapacity);
      this.hashTable = new Object[tableSize];
      this.maxRunBeforeFallback = maxRunBeforeFallback(tableSize);
      this.expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * tableSize);
    }

    RegularSetBuilderImpl(RegularSetBuilderImpl<E> toCopy) {
      super(toCopy);
      this.hashTable = Arrays.copyOf(toCopy.hashTable, toCopy.hashTable.length);
      this.maxRunBeforeFallback = toCopy.maxRunBeforeFallback;
      this.expandTableThreshold = toCopy.expandTableThreshold;
      this.hashCode = toCopy.hashCode;
    }

    void ensureTableCapacity(int minCapacity) {
      if (minCapacity > expandTableThreshold && hashTable.length < MAX_TABLE_SIZE) {
        int newTableSize = hashTable.length * 2;
        hashTable = rebuildHashTable(newTableSize, dedupedElements, distinct);
        maxRunBeforeFallback = maxRunBeforeFallback(newTableSize);
        expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * newTableSize);
      }
    }

    @Override
    SetBuilderImpl<E> add(E e) {
      checkNotNull(e);
      int eHash = e.hashCode();
      int i0 = Hashing.smear(eHash);
      int mask = hashTable.length - 1;
      for (int i = i0; i - i0 < maxRunBeforeFallback; i++) {
        int index = i & mask;
        Object tableEntry = hashTable[index];
        if (tableEntry == null) {
          addDedupedElement(e);
          hashTable[index] = e;
          hashCode += eHash;
          ensureTableCapacity(distinct); // rebuilds table if necessary
          return this;
        } else if (tableEntry.equals(e)) { // not a new element, ignore
          return this;
        }
      }
      // we fell out of the loop due to a long run; fall back to JDK impl
      return new JdkBackedSetBuilderImpl<E>(this).add(e);
    }

    @Override
    SetBuilderImpl<E> copy() {
      return new RegularSetBuilderImpl<E>(this);
    }

    @Override
    SetBuilderImpl<E> review() {
      int targetTableSize = chooseTableSize(distinct);
      if (targetTableSize * 2 < hashTable.length) {
        hashTable = rebuildHashTable(targetTableSize, dedupedElements, distinct);
      }
      return hashFloodingDetected(hashTable) ? new JdkBackedSetBuilderImpl<E>(this) : this;
    }

    @Override
    ImmutableSet<E> build() {
      switch (distinct) {
        case 0:
          return of();
        case 1:
          return of(dedupedElements[0]);
        default:
          Object[] elements =
              (distinct == dedupedElements.length)
                  ? dedupedElements
                  : Arrays.copyOf(dedupedElements, distinct);
          return new RegularImmutableSet<E>(elements, hashCode, hashTable, hashTable.length - 1);
      }
    }
  }

  
SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection.

/**
   * SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection.
   */
  private static final class JdkBackedSetBuilderImpl<E> extends SetBuilderImpl<E> {
    private final Set<Object> delegate;

    JdkBackedSetBuilderImpl(SetBuilderImpl<E> toCopy) {
      super(toCopy); // initializes dedupedElements and distinct
      delegate = Sets.newHashSetWithExpectedSize(distinct);
      for (int i = 0; i < distinct; i++) {
        delegate.add(dedupedElements[i]);
      }
    }

    @Override
    SetBuilderImpl<E> add(E e) {
      checkNotNull(e);
      if (delegate.add(e)) {
        addDedupedElement(e);
      }
      return this;
    }

    @Override
    SetBuilderImpl<E> copy() {
      return new JdkBackedSetBuilderImpl<>(this);
    }

    @Override
    ImmutableSet<E> build() {
      switch (distinct) {
        case 0:
          return of();
        case 1:
          return of(dedupedElements[0]);
        default:
          return new JdkBackedImmutableSet<E>(
              delegate, ImmutableList.asImmutableList(dedupedElements, distinct));
      }
    }
  }
}