}

    @CheckForNull
    abstract V getValue(int keyIndex);

    @Override
    ImmutableSet<K> createKeySet() {
      return isFull() ? keyToIndex().keySet() : super.createKeySet();
    }

    @Override
    public int size() {
      return size;
    }

    @Override
    @CheckForNull
    public V get(@CheckForNull Object key) {

  private static final class Listener {
    static final Listener TOMBSTONE = new Listener();
    @CheckForNull // null only for TOMBSTONE
    final Runnable task;
    @CheckForNull // null only for TOMBSTONE
    final Executor executor;

    // writes to next are made visible by subsequent CAS's on the listeners field
    @CheckForNull Listener next;

    Listener(Runnable task, Executor executor) {
      this.task = task;

  private static final class Listener {
    static final Listener TOMBSTONE = new Listener();
    @CheckForNull // null only for TOMBSTONE
    final Runnable task;
    @CheckForNull // null only for TOMBSTONE
    final Executor executor;

    // writes to next are made visible by subsequent CAS's on the listeners field
    @CheckForNull Listener next;

    Listener(Runnable task, Executor executor) {
      this.task = task;

  // See the note about volatile in the superclass.
  @CheckForNull private transient volatile CacheEntry<K, V> cacheEntry1;
  @CheckForNull private transient volatile CacheEntry<K, V> cacheEntry2;

  MapRetrievalCache(Map<K, V> backingMap) {
    super(backingMap);
  }

  @SuppressWarnings("unchecked") // Safe because we only cast if key is found in map.
  @Override
  @CheckForNull
  V get(Object key) {
    checkNotNull(key);

    @CheckForNull Segment<K, V, E, S> currentSegment;
    @CheckForNull AtomicReferenceArray<E> currentTable;
    @CheckForNull E nextEntry;
    @CheckForNull WriteThroughEntry nextExternal;
    @CheckForNull WriteThroughEntry lastReturned;

    HashIterator() {
      nextSegmentIndex = segments.length - 1;
      nextTableIndex = -1;
      advance();
    }

    @Override

        header);
  }

  private static final class Reference<T> {
    @CheckForNull private T value;

    @CheckForNull
    public T get() {
      return value;
    }

    public void checkAndSet(@CheckForNull T expected, @CheckForNull T newValue) {
      if (value != expected) {
        throw new ConcurrentModificationException();
      }
      value = newValue;

   *
   * @since 23.1 (varargs overload since 17.0)
   */
  public static void verify(
      boolean expression,
      String errorMessageTemplate,
      @CheckForNull Object p1,
      @CheckForNull Object p2,
      @CheckForNull Object p3,
      @CheckForNull Object p4) {
    if (!expression) {
      throw new VerifyException(lenientFormat(errorMessageTemplate, p1, p2, p3, p4));
    }
  }

  /*

@ElementTypesAreNonnullByDefault
final class AllEqualOrdering extends Ordering<@Nullable Object> implements Serializable {
  static final AllEqualOrdering INSTANCE = new AllEqualOrdering();

  @Override
  public int compare(@CheckForNull Object left, @CheckForNull Object right) {
    return 0;
  }

  @Override
  public <E extends @Nullable Object> List<E> sortedCopy(Iterable<E> iterable) {
    return Lists.newArrayList(iterable);
  }

  @Override

@ElementTypesAreNonnullByDefault
final class AllEqualOrdering extends Ordering<@Nullable Object> implements Serializable {
  static final AllEqualOrdering INSTANCE = new AllEqualOrdering();

  @Override
  public int compare(@CheckForNull Object left, @CheckForNull Object right) {
    return 0;
  }

  @Override
  public <E extends @Nullable Object> List<E> sortedCopy(Iterable<E> iterable) {
    return Lists.newArrayList(iterable);
  }

  @Override

    return (index >= 0 && get(index).equals(target)) ? index : -1;
  }

  @GwtIncompatible // ImmutableSortedSet.indexOf
  @Override
  public int lastIndexOf(@CheckForNull Object target) {
    return indexOf(target);
  }

  @Override
  public boolean contains(@CheckForNull Object target) {
    // Necessary for ISS's with comparators inconsistent with equals.
    return indexOf(target) >= 0;
  }