}
    }
  }

  /**
   * Returns the bucket (in either the K-to-V or V-to-K tables) where elements with the specified
   * hash could be found, if present, or could be inserted.
   */
  private int bucket(int hash) {
    return hash & (hashTableKToV.length - 1);
  }

  /** Given a key, returns the index of the entry in the tables, or ABSENT if not found. */

 * amortized) constant time operations. Expected in the hashtable sense (depends on the hash
 * function doing a good job of distributing the elements to the buckets to a distribution not far
 * from uniform), and amortized since some operations can trigger a hash table resize.
 *
 * <p>As compared with {@link java.util.LinkedHashMap}, this structure places significantly reduced

import static org.junit.Assert.assertThrows;

import com.google.common.base.Charsets;
import com.google.common.base.Optional;
import com.google.common.collect.ImmutableList;
import com.google.common.hash.HashCode;
import com.google.common.hash.Hashing;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

   * objects per entry.  Instead we use an open-addressed hash table.  This design is basically
   * equivalent to RegularImmutableSet, save that instead of having a hash table containing the
   * elements directly and null for empty positions, we store indices of the keys in the hash table,
   * and ABSENT for empty positions.  We then look up the keys in alternatingKeysAndValues.
   *

/**
 * Implementation of ImmutableMap backed by a JDK HashMap, which has smartness protecting against
 * hash flooding.
 */
@GwtCompatible(emulated = true)
@ElementTypesAreNonnullByDefault
final class JdkBackedImmutableMap<K, V> extends ImmutableMap<K, V> {
  /**
   * Creates an {@code ImmutableMap} backed by a JDK HashMap. Used when probable hash flooding is

      }
    }
    return true;
  }

  /** Returns an unspecified hash code for the contents of this immutable array. */
  @Override
  public int hashCode() {
    int hash = 1;
    for (int i = start; i < end; i++) {
      hash *= 31;
      hash += Ints.hashCode(array[i]);
    }
    return hash;
  }

  /**
   * Returns a string representation of this array in the same form as {@link

  }

  /** Returns an unspecified hash code for the contents of this immutable array. */
  @Override
  public int hashCode() {
    int hash = 1;
    for (int i = start; i < end; i++) {
      hash *= 31;
      hash += Doubles.hashCode(array[i]);
    }
    return hash;
  }

  /**
   * Returns a string representation of this array in the same form as {@link

import com.google.common.annotations.GwtCompatible;
import com.google.common.collect.testing.SampleElements.Colliders;
import java.util.List;

/**
 * A generator using sample elements whose hash codes all collide badly.
 *
 * @author Kevin Bourrillion
 */
@GwtCompatible
@ElementTypesAreNonnullByDefault
public abstract class TestCollidingSetGenerator implements TestSetGenerator<Object> {
  @Override

  @Override
  boolean equals(@CheckForNull Object obj);

  /**
   * Returns the hash code for this multimap.
   *
   * <p>The hash code of a multimap is defined as the hash code of the map view, as returned by
   * {@link Multimap#asMap}.
   *
   * <p>In general, two multimaps with identical key-value mappings may or may not have the same
   * hash codes, depending on the implementation. For example, two {@link SetMultimap} instances

    for (int i = 0; i < length; i++) {
      Object key = new Object();
      // TODO(b/145386688): This access should be guarded by 'this.segment', which is not currently
      // held
      chain = segment.newEntry(key, cache.hash(key), chain);
      if (i == 0) {
        head = chain;
      }
    }
  }

  @SuppressWarnings("GuardedBy")
  @Benchmark
  int time(int reps) {
    int dummy = 0;
    for (int i = 0; i < reps; i++) {