Initial Jack import.

Change-Id: I953cf0a520195a7187d791b2885848ad0d5a9b43

1 files changed, 4081 insertions, 0 deletions

diff --git a/guava/src/com/google/common/collect/MapMakerInternalMap.java b/guava/src/com/google/common/collect/MapMakerInternalMap.java
new file mode 100644
index 0000000..ac7b371
--- /dev/null
+++ b/guava/src/com/google/common/collect/MapMakerInternalMap.java
@@ -0,0 +1,4081 @@
+/*
+ * Copyright (C) 2009 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.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Equivalence;
+import com.google.common.base.Ticker;
+import com.google.common.collect.GenericMapMaker.NullListener;
+import com.google.common.collect.MapMaker.RemovalCause;
+import com.google.common.collect.MapMaker.RemovalListener;
+import com.google.common.collect.MapMaker.RemovalNotification;
+import com.google.common.primitives.Ints;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.lang.ref.Reference;
+import java.lang.ref.ReferenceQueue;
+import java.lang.ref.SoftReference;
+import java.lang.ref.WeakReference;
+import java.util.AbstractCollection;
+import java.util.AbstractMap;
+import java.util.AbstractQueue;
+import java.util.AbstractSet;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Queue;
+import java.util.Set;
+import java.util.concurrent.CancellationException;
+import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReferenceArray;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+import javax.annotation.Nullable;
+import javax.annotation.concurrent.GuardedBy;
+
+/**
+ * The concurrent hash map implementation built by {@link MapMaker}.
+ *
+ * <p>This implementation is heavily derived from revision 1.96 of <a
+ * href="http://tinyurl.com/ConcurrentHashMap">ConcurrentHashMap.java</a>.
+ *
+ * @author Bob Lee
+ * @author Charles Fry
+ * @author Doug Lea ({@code ConcurrentHashMap})
+ */
+class MapMakerInternalMap<K, V>
+    extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {
+
+  /*
+   * The basic strategy is to subdivide the table among Segments, each of which itself is a
+   * concurrently readable hash table. The map supports non-blocking reads and concurrent writes
+   * across different segments.
+   *
+   * If a maximum size is specified, a best-effort bounding is performed per segment, using a
+   * page-replacement algorithm to determine which entries to evict when the capacity has been
+   * exceeded.
+   *
+   * The page replacement algorithm's data structures are kept casually consistent with the map. The
+   * ordering of writes to a segment is sequentially consistent. An update to the map and recording
+   * of reads may not be immediately reflected on the algorithm's data structures. These structures
+   * are guarded by a lock and operations are applied in batches to avoid lock contention. The
+   * penalty of applying the batches is spread across threads so that the amortized cost is slightly
+   * higher than performing just the operation without enforcing the capacity constraint.
+   *
+   * This implementation uses a per-segment queue to record a memento of the additions, removals,
+   * and accesses that were performed on the map. The queue is drained on writes and when it exceeds
+   * its capacity threshold.
+   *
+   * The Least Recently Used page replacement algorithm was chosen due to its simplicity, high hit
+   * rate, and ability to be implemented with O(1) time complexity. The initial LRU implementation
+   * operates per-segment rather than globally for increased implementation simplicity. We expect
+   * the cache hit rate to be similar to that of a global LRU algorithm.
+   */
+
+  // Constants
+
+  /**
+   * The maximum capacity, used if a higher value is implicitly specified by either of the
+   * constructors with arguments. MUST be a power of two <= 1<<30 to ensure that entries are
+   * indexable using ints.
+   */
+  static final int MAXIMUM_CAPACITY = Ints.MAX_POWER_OF_TWO;
+
+  /** The maximum number of segments to allow; used to bound constructor arguments. */
+  static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
+
+  /** Number of (unsynchronized) retries in the containsValue method. */
+  static final int CONTAINS_VALUE_RETRIES = 3;
+
+  /**
+   * Number of cache access operations that can be buffered per segment before the cache's recency
+   * ordering information is updated. This is used to avoid lock contention by recording a memento
+   * of reads and delaying a lock acquisition until the threshold is crossed or a mutation occurs.
+   *
+   * <p>This must be a (2^n)-1 as it is used as a mask.
+   */
+  static final int DRAIN_THRESHOLD = 0x3F;
+
+  /**
+   * Maximum number of entries to be drained in a single cleanup run. This applies independently to
+   * the cleanup queue and both reference queues.
+   */
+  // TODO(fry): empirically optimize this
+  static final int DRAIN_MAX = 16;
+
+  static final long CLEANUP_EXECUTOR_DELAY_SECS = 60;
+
+  // Fields
+
+  private static final Logger logger = Logger.getLogger(MapMakerInternalMap.class.getName());
+
+  /**
+   * Mask value for indexing into segments. The upper bits of a key's hash code are used to choose
+   * the segment.
+   */
+  final transient int segmentMask;
+
+  /**
+   * Shift value for indexing within segments. Helps prevent entries that end up in the same segment
+   * from also ending up in the same bucket.
+   */
+  final transient int segmentShift;
+
+  /** The segments, each of which is a specialized hash table. */
+  final transient Segment<K, V>[] segments;
+
+  /** The concurrency level. */
+  final int concurrencyLevel;
+
+  /** Strategy for comparing keys. */
+  final Equivalence<Object> keyEquivalence;
+
+  /** Strategy for comparing values. */
+  final Equivalence<Object> valueEquivalence;
+
+  /** Strategy for referencing keys. */
+  final Strength keyStrength;
+
+  /** Strategy for referencing values. */
+  final Strength valueStrength;
+
+  /** The maximum size of this map. MapMaker.UNSET_INT if there is no maximum. */
+  final int maximumSize;
+
+  /** How long after the last access to an entry the map will retain that entry. */
+  final long expireAfterAccessNanos;
+
+  /** How long after the last write to an entry the map will retain that entry. */
+  final long expireAfterWriteNanos;
+
+  /** Entries waiting to be consumed by the removal listener. */
+  // TODO(fry): define a new type which creates event objects and automates the clear logic
+  final Queue<RemovalNotification<K, V>> removalNotificationQueue;
+
+  /**
+   * A listener that is invoked when an entry is removed due to expiration or garbage collection of
+   * soft/weak entries.
+   */
+  final RemovalListener<K, V> removalListener;
+
+  /** Factory used to create new entries. */
+  final transient EntryFactory entryFactory;
+
+  /** Measures time in a testable way. */
+  final Ticker ticker;
+
+  /**
+   * Creates a new, empty map with the specified strategy, initial capacity and concurrency level.
+   */
+  MapMakerInternalMap(MapMaker builder) {
+    concurrencyLevel = Math.min(builder.getConcurrencyLevel(), MAX_SEGMENTS);
+
+    keyStrength = builder.getKeyStrength();
+    valueStrength = builder.getValueStrength();
+
+    keyEquivalence = builder.getKeyEquivalence();
+    valueEquivalence = valueStrength.defaultEquivalence();
+
+    maximumSize = builder.maximumSize;
+    expireAfterAccessNanos = builder.getExpireAfterAccessNanos();
+    expireAfterWriteNanos = builder.getExpireAfterWriteNanos();
+
+    entryFactory = EntryFactory.getFactory(keyStrength, expires(), evictsBySize());
+    ticker = builder.getTicker();
+
+    removalListener = builder.getRemovalListener();
+    removalNotificationQueue = (removalListener == NullListener.INSTANCE)
+        ? MapMakerInternalMap.<RemovalNotification<K, V>>discardingQueue()
+        : new ConcurrentLinkedQueue<RemovalNotification<K, V>>();
+
+    int initialCapacity = Math.min(builder.getInitialCapacity(), MAXIMUM_CAPACITY);
+    if (evictsBySize()) {
+      initialCapacity = Math.min(initialCapacity, maximumSize);
+    }
+
+    // Find power-of-two sizes best matching arguments. Constraints:
+    // (segmentCount <= maximumSize)
+    // && (concurrencyLevel > maximumSize || segmentCount > concurrencyLevel)
+    int segmentShift = 0;
+    int segmentCount = 1;
+    while (segmentCount < concurrencyLevel
+        && (!evictsBySize() || segmentCount * 2 <= maximumSize)) {
+      ++segmentShift;
+      segmentCount <<= 1;
+    }
+    this.segmentShift = 32 - segmentShift;
+    segmentMask = segmentCount - 1;
+
+    this.segments = newSegmentArray(segmentCount);
+
+    int segmentCapacity = initialCapacity / segmentCount;
+    if (segmentCapacity * segmentCount < initialCapacity) {
+      ++segmentCapacity;
+    }
+
+    int segmentSize = 1;
+    while (segmentSize < segmentCapacity) {
+      segmentSize <<= 1;
+    }
+
+    if (evictsBySize()) {
+      // Ensure sum of segment max sizes = overall max size
+      int maximumSegmentSize = maximumSize / segmentCount + 1;
+      int remainder = maximumSize % segmentCount;
+      for (int i = 0; i < this.segments.length; ++i) {
+        if (i == remainder) {
+          maximumSegmentSize--;
+        }
+        this.segments[i] =
+            createSegment(segmentSize, maximumSegmentSize);
+      }
+    } else {
+      for (int i = 0; i < this.segments.length; ++i) {
+        this.segments[i] =
+            createSegment(segmentSize, MapMaker.UNSET_INT);
+      }
+    }
+  }
+
+  boolean evictsBySize() {
+    return maximumSize != MapMaker.UNSET_INT;
+  }
+
+  boolean expires() {
+    return expiresAfterWrite() || expiresAfterAccess();
+  }
+
+  boolean expiresAfterWrite() {
+    return expireAfterWriteNanos > 0;
+  }
+
+  boolean expiresAfterAccess() {
+    return expireAfterAccessNanos > 0;
+  }
+
+  boolean usesKeyReferences() {
+    return keyStrength != Strength.STRONG;
+  }
+
+  boolean usesValueReferences() {
+    return valueStrength != Strength.STRONG;
+  }
+
+  enum Strength {
+    /*
+     * TODO(kevinb): If we strongly reference the value and aren't computing, we needn't wrap the
+     * value. This could save ~8 bytes per entry.
+     */
+
+    STRONG {
+      @Override
+      <K, V> ValueReference<K, V> referenceValue(
+          Segment<K, V> segment, ReferenceEntry<K, V> entry, V value) {
+        return new StrongValueReference<K, V>(value);
+      }
+
+      @Override
+      Equivalence<Object> defaultEquivalence() {
+        return Equivalence.equals();
+      }
+    },
+
+    SOFT {
+      @Override
+      <K, V> ValueReference<K, V> referenceValue(
+          Segment<K, V> segment, ReferenceEntry<K, V> entry, V value) {
+        return new SoftValueReference<K, V>(segment.valueReferenceQueue, value, entry);
+      }
+
+      @Override
+      Equivalence<Object> defaultEquivalence() {
+        return Equivalence.identity();
+      }
+    },
+
+    WEAK {
+      @Override
+      <K, V> ValueReference<K, V> referenceValue(
+          Segment<K, V> segment, ReferenceEntry<K, V> entry, V value) {
+        return new WeakValueReference<K, V>(segment.valueReferenceQueue, value, entry);
+      }
+
+      @Override
+      Equivalence<Object> defaultEquivalence() {
+        return Equivalence.identity();
+      }
+    };
+
+    /**
+     * Creates a reference for the given value according to this value strength.
+     */
+    abstract <K, V> ValueReference<K, V> referenceValue(
+        Segment<K, V> segment, ReferenceEntry<K, V> entry, V value);
+
+    /**
+     * Returns the default equivalence strategy used to compare and hash keys or values referenced
+     * at this strength. This strategy will be used unless the user explicitly specifies an
+     * alternate strategy.
+     */
+    abstract Equivalence<Object> defaultEquivalence();
+  }
+
+  /**
+   * Creates new entries.
+   */
+  enum EntryFactory {
+    STRONG {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new StrongEntry<K, V>(key, hash, next);
+      }
+    },
+    STRONG_EXPIRABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new StrongExpirableEntry<K, V>(key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyExpirableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+    STRONG_EVICTABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new StrongEvictableEntry<K, V>(key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyEvictableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+    STRONG_EXPIRABLE_EVICTABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new StrongExpirableEvictableEntry<K, V>(key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyExpirableEntry(original, newEntry);
+        copyEvictableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+
+    SOFT {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new SoftEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+    },
+    SOFT_EXPIRABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new SoftExpirableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyExpirableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+    SOFT_EVICTABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new SoftEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyEvictableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+    SOFT_EXPIRABLE_EVICTABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new SoftExpirableEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyExpirableEntry(original, newEntry);
+        copyEvictableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+
+    WEAK {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new WeakEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+    },
+    WEAK_EXPIRABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new WeakExpirableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyExpirableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+    WEAK_EVICTABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new WeakEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyEvictableEntry(original, newEntry);
+        return newEntry;
+      }
+    },
+    WEAK_EXPIRABLE_EVICTABLE {
+      @Override
+      <K, V> ReferenceEntry<K, V> newEntry(
+          Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+        return new WeakExpirableEvictableEntry<K, V>(segment.keyReferenceQueue, key, hash, next);
+      }
+
+      @Override
+      <K, V> ReferenceEntry<K, V> copyEntry(
+          Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+        ReferenceEntry<K, V> newEntry = super.copyEntry(segment, original, newNext);
+        copyExpirableEntry(original, newEntry);
+        copyEvictableEntry(original, newEntry);
+        return newEntry;
+      }
+    };
+
+    /**
+     * Masks used to compute indices in the following table.
+     */
+    static final int EXPIRABLE_MASK = 1;
+    static final int EVICTABLE_MASK = 2;
+
+    /**
+     * Look-up table for factories. First dimension is the reference type. The second dimension is
+     * the result of OR-ing the feature masks.
+     */
+    static final EntryFactory[][] factories = {
+      { STRONG, STRONG_EXPIRABLE, STRONG_EVICTABLE, STRONG_EXPIRABLE_EVICTABLE },
+      { SOFT, SOFT_EXPIRABLE, SOFT_EVICTABLE, SOFT_EXPIRABLE_EVICTABLE },
+      { WEAK, WEAK_EXPIRABLE, WEAK_EVICTABLE, WEAK_EXPIRABLE_EVICTABLE }
+    };
+
+    static EntryFactory getFactory(Strength keyStrength, boolean expireAfterWrite,
+        boolean evictsBySize) {
+      int flags = (expireAfterWrite ? EXPIRABLE_MASK : 0) | (evictsBySize ? EVICTABLE_MASK : 0);
+      return factories[keyStrength.ordinal()][flags];
+    }
+
+    /**
+     * Creates a new entry.
+     *
+     * @param segment to create the entry for
+     * @param key of the entry
+     * @param hash of the key
+     * @param next entry in the same bucket
+     */
+    abstract <K, V> ReferenceEntry<K, V> newEntry(
+        Segment<K, V> segment, K key, int hash, @Nullable ReferenceEntry<K, V> next);
+
+    /**
+     * Copies an entry, assigning it a new {@code next} entry.
+     *
+     * @param original the entry to copy
+     * @param newNext entry in the same bucket
+     */
+    @GuardedBy("Segment.this")
+    <K, V> ReferenceEntry<K, V> copyEntry(
+        Segment<K, V> segment, ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+      return newEntry(segment, original.getKey(), original.getHash(), newNext);
+    }
+
+    @GuardedBy("Segment.this")
+    <K, V> void copyExpirableEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newEntry) {
+      // TODO(fry): when we link values instead of entries this method can go
+      // away, as can connectExpirables, nullifyExpirable.
+      newEntry.setExpirationTime(original.getExpirationTime());
+
+      connectExpirables(original.getPreviousExpirable(), newEntry);
+      connectExpirables(newEntry, original.getNextExpirable());
+
+      nullifyExpirable(original);
+    }
+
+    @GuardedBy("Segment.this")
+    <K, V> void copyEvictableEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newEntry) {
+      // TODO(fry): when we link values instead of entries this method can go
+      // away, as can connectEvictables, nullifyEvictable.
+      connectEvictables(original.getPreviousEvictable(), newEntry);
+      connectEvictables(newEntry, original.getNextEvictable());
+
+      nullifyEvictable(original);
+    }
+  }
+
+  /**
+   * A reference to a value.
+   */
+  interface ValueReference<K, V> {
+    /**
+     * Gets the value. Does not block or throw exceptions.
+     */
+    V get();
+
+    /**
+     * Waits for a value that may still be computing. Unlike get(), this method can block (in the
+     * case of FutureValueReference).
+     *
+     * @throws ExecutionException if the computing thread throws an exception
+     */
+    V waitForValue() throws ExecutionException;
+
+    /**
+     * Returns the entry associated with this value reference, or {@code null} if this value
+     * reference is independent of any entry.
+     */
+    ReferenceEntry<K, V> getEntry();
+
+    /**
+     * Creates a copy of this reference for the given entry.
+     *
+     * <p>{@code value} may be null only for a loading reference.
+     */
+    ValueReference<K, V> copyFor(
+        ReferenceQueue<V> queue, @Nullable V value, ReferenceEntry<K, V> entry);
+
+    /**
+     * Clears this reference object.
+     *
+     * @param newValue the new value reference which will replace this one; this is only used during
+     *     computation to immediately notify blocked threads of the new value
+     */
+    void clear(@Nullable ValueReference<K, V> newValue);
+
+    /**
+     * Returns {@code true} if the value type is a computing reference (regardless of whether or not
+     * computation has completed). This is necessary to distiguish between partially-collected
+     * entries and computing entries, which need to be cleaned up differently.
+     */
+    boolean isComputingReference();
+  }
+
+  /**
+   * Placeholder. Indicates that the value hasn't been set yet.
+   */
+  static final ValueReference<Object, Object> UNSET = new ValueReference<Object, Object>() {
+    @Override
+    public Object get() {
+      return null;
+    }
+
+    @Override
+    public ReferenceEntry<Object, Object> getEntry() {
+      return null;
+    }
+
+    @Override
+    public ValueReference<Object, Object> copyFor(ReferenceQueue<Object> queue,
+        @Nullable Object value, ReferenceEntry<Object, Object> entry) {
+      return this;
+    }
+
+    @Override
+    public boolean isComputingReference() {
+      return false;
+    }
+
+    @Override
+    public Object waitForValue() {
+      return null;
+    }
+
+    @Override
+    public void clear(ValueReference<Object, Object> newValue) {}
+  };
+
+  /**
+   * Singleton placeholder that indicates a value is being computed.
+   */
+  @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
+  static <K, V> ValueReference<K, V> unset() {
+    return (ValueReference<K, V>) UNSET;
+  }
+
+  /**
+   * An entry in a reference map.
+   *
+   * Entries in the map can be in the following states:
+   *
+   * Valid:
+   * - Live: valid key/value are set
+   * - Computing: computation is pending
+   *
+   * Invalid:
+   * - Expired: time expired (key/value may still be set)
+   * - Collected: key/value was partially collected, but not yet cleaned up
+   */
+  interface ReferenceEntry<K, V> {
+    /**
+     * Gets the value reference from this entry.
+     */
+    ValueReference<K, V> getValueReference();
+
+    /**
+     * Sets the value reference for this entry.
+     */
+    void setValueReference(ValueReference<K, V> valueReference);
+
+    /**
+     * Gets the next entry in the chain.
+     */
+    ReferenceEntry<K, V> getNext();
+
+    /**
+     * Gets the entry's hash.
+     */
+    int getHash();
+
+    /**
+     * Gets the key for this entry.
+     */
+    K getKey();
+
+    /*
+     * Used by entries that are expirable. Expirable entries are maintained in a doubly-linked list.
+     * New entries are added at the tail of the list at write time; stale entries are expired from
+     * the head of the list.
+     */
+
+    /**
+     * Gets the entry expiration time in ns.
+     */
+    long getExpirationTime();
+
+    /**
+     * Sets the entry expiration time in ns.
+     */
+    void setExpirationTime(long time);
+
+    /**
+     * Gets the next entry in the recency list.
+     */
+    ReferenceEntry<K, V> getNextExpirable();
+
+    /**
+     * Sets the next entry in the recency list.
+     */
+    void setNextExpirable(ReferenceEntry<K, V> next);
+
+    /**
+     * Gets the previous entry in the recency list.
+     */
+    ReferenceEntry<K, V> getPreviousExpirable();
+
+    /**
+     * Sets the previous entry in the recency list.
+     */
+    void setPreviousExpirable(ReferenceEntry<K, V> previous);
+
+    /*
+     * Implemented by entries that are evictable. Evictable entries are maintained in a
+     * doubly-linked list. New entries are added at the tail of the list at write time and stale
+     * entries are expired from the head of the list.
+     */
+
+    /**
+     * Gets the next entry in the recency list.
+     */
+    ReferenceEntry<K, V> getNextEvictable();
+
+    /**
+     * Sets the next entry in the recency list.
+     */
+    void setNextEvictable(ReferenceEntry<K, V> next);
+
+    /**
+     * Gets the previous entry in the recency list.
+     */
+    ReferenceEntry<K, V> getPreviousEvictable();
+
+    /**
+     * Sets the previous entry in the recency list.
+     */
+    void setPreviousEvictable(ReferenceEntry<K, V> previous);
+  }
+
+  private enum NullEntry implements ReferenceEntry<Object, Object> {
+    INSTANCE;
+
+    @Override
+    public ValueReference<Object, Object> getValueReference() {
+      return null;
+    }
+
+    @Override
+    public void setValueReference(ValueReference<Object, Object> valueReference) {}
+
+    @Override
+    public ReferenceEntry<Object, Object> getNext() {
+      return null;
+    }
+
+    @Override
+    public int getHash() {
+      return 0;
+    }
+
+    @Override
+    public Object getKey() {
+      return null;
+    }
+
+    @Override
+    public long getExpirationTime() {
+      return 0;
+    }
+
+    @Override
+    public void setExpirationTime(long time) {}
+
+    @Override
+    public ReferenceEntry<Object, Object> getNextExpirable() {
+      return this;
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<Object, Object> next) {}
+
+    @Override
+    public ReferenceEntry<Object, Object> getPreviousExpirable() {
+      return this;
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<Object, Object> previous) {}
+
+    @Override
+    public ReferenceEntry<Object, Object> getNextEvictable() {
+      return this;
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<Object, Object> next) {}
+
+    @Override
+    public ReferenceEntry<Object, Object> getPreviousEvictable() {
+      return this;
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<Object, Object> previous) {}
+  }
+
+  abstract static class AbstractReferenceEntry<K, V> implements ReferenceEntry<K, V> {
+    @Override
+    public ValueReference<K, V> getValueReference() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setValueReference(ValueReference<K, V> valueReference) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNext() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public int getHash() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public K getKey() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getExpirationTime() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+  }
+
+  @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
+  static <K, V> ReferenceEntry<K, V> nullEntry() {
+    return (ReferenceEntry<K, V>) NullEntry.INSTANCE;
+  }
+
+  static final Queue<? extends Object> DISCARDING_QUEUE = new AbstractQueue<Object>() {
+    @Override
+    public boolean offer(Object o) {
+      return true;
+    }
+
+    @Override
+    public Object peek() {
+      return null;
+    }
+
+    @Override
+    public Object poll() {
+      return null;
+    }
+
+    @Override
+    public int size() {
+      return 0;
+    }
+
+    @Override
+    public Iterator<Object> iterator() {
+      return Iterators.emptyIterator();
+    }
+  };
+
+  /**
+   * Queue that discards all elements.
+   */
+  @SuppressWarnings("unchecked") // impl never uses a parameter or returns any non-null value
+  static <E> Queue<E> discardingQueue() {
+    return (Queue) DISCARDING_QUEUE;
+  }
+
+  /*
+   * Note: All of this duplicate code sucks, but it saves a lot of memory. If only Java had mixins!
+   * To maintain this code, make a change for the strong reference type. Then, cut and paste, and
+   * replace "Strong" with "Soft" or "Weak" within the pasted text. The primary difference is that
+   * strong entries store the key reference directly while soft and weak entries delegate to their
+   * respective superclasses.
+   */
+
+  /**
+   * Used for strongly-referenced keys.
+   */
+  static class StrongEntry<K, V> implements ReferenceEntry<K, V> {
+    final K key;
+
+    StrongEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      this.key = key;
+      this.hash = hash;
+      this.next = next;
+    }
+
+    @Override
+    public K getKey() {
+      return this.key;
+    }
+
+    // null expiration
+
+    @Override
+    public long getExpirationTime() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+
+    // null eviction
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+
+    // The code below is exactly the same for each entry type.
+
+    final int hash;
+    final ReferenceEntry<K, V> next;
+    volatile ValueReference<K, V> valueReference = unset();
+
+    @Override
+    public ValueReference<K, V> getValueReference() {
+      return valueReference;
+    }
+
+    @Override
+    public void setValueReference(ValueReference<K, V> valueReference) {
+      ValueReference<K, V> previous = this.valueReference;
+      this.valueReference = valueReference;
+      previous.clear(valueReference);
+    }
+
+    @Override
+    public int getHash() {
+      return hash;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNext() {
+      return next;
+    }
+  }
+
+  static final class StrongExpirableEntry<K, V> extends StrongEntry<K, V>
+      implements ReferenceEntry<K, V> {
+    StrongExpirableEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(key, hash, next);
+    }
+
+    // The code below is exactly the same for each expirable entry type.
+
+    volatile long time = Long.MAX_VALUE;
+
+    @Override
+    public long getExpirationTime() {
+      return time;
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      this.time = time;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      return nextExpirable;
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      this.nextExpirable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      return previousExpirable;
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      this.previousExpirable = previous;
+    }
+  }
+
+  static final class StrongEvictableEntry<K, V>
+      extends StrongEntry<K, V> implements ReferenceEntry<K, V> {
+    StrongEvictableEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(key, hash, next);
+    }
+
+    // The code below is exactly the same for each evictable entry type.
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      return nextEvictable;
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      this.nextEvictable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      return previousEvictable;
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      this.previousEvictable = previous;
+    }
+  }
+
+  static final class StrongExpirableEvictableEntry<K, V>
+      extends StrongEntry<K, V> implements ReferenceEntry<K, V> {
+    StrongExpirableEvictableEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(key, hash, next);
+    }
+
+    // The code below is exactly the same for each expirable entry type.
+
+    volatile long time = Long.MAX_VALUE;
+
+    @Override
+    public long getExpirationTime() {
+      return time;
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      this.time = time;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      return nextExpirable;
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      this.nextExpirable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      return previousExpirable;
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      this.previousExpirable = previous;
+    }
+
+    // The code below is exactly the same for each evictable entry type.
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      return nextEvictable;
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      this.nextEvictable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      return previousEvictable;
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      this.previousEvictable = previous;
+    }
+  }
+
+  /**
+   * Used for softly-referenced keys.
+   */
+  static class SoftEntry<K, V> extends SoftReference<K> implements ReferenceEntry<K, V> {
+    SoftEntry(ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(key, queue);
+      this.hash = hash;
+      this.next = next;
+    }
+
+    @Override
+    public K getKey() {
+      return get();
+    }
+
+    // null expiration
+    @Override
+    public long getExpirationTime() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+
+    // null eviction
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+
+    // The code below is exactly the same for each entry type.
+
+    final int hash;
+    final ReferenceEntry<K, V> next;
+    volatile ValueReference<K, V> valueReference = unset();
+
+    @Override
+    public ValueReference<K, V> getValueReference() {
+      return valueReference;
+    }
+
+    @Override
+    public void setValueReference(ValueReference<K, V> valueReference) {
+      ValueReference<K, V> previous = this.valueReference;
+      this.valueReference = valueReference;
+      previous.clear(valueReference);
+    }
+
+    @Override
+    public int getHash() {
+      return hash;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNext() {
+      return next;
+    }
+  }
+
+  static final class SoftExpirableEntry<K, V>
+      extends SoftEntry<K, V> implements ReferenceEntry<K, V> {
+    SoftExpirableEntry(
+        ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(queue, key, hash, next);
+    }
+
+    // The code below is exactly the same for each expirable entry type.
+
+    volatile long time = Long.MAX_VALUE;
+
+    @Override
+    public long getExpirationTime() {
+      return time;
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      this.time = time;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      return nextExpirable;
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      this.nextExpirable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      return previousExpirable;
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      this.previousExpirable = previous;
+    }
+  }
+
+  static final class SoftEvictableEntry<K, V>
+      extends SoftEntry<K, V> implements ReferenceEntry<K, V> {
+    SoftEvictableEntry(
+        ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(queue, key, hash, next);
+    }
+
+    // The code below is exactly the same for each evictable entry type.
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      return nextEvictable;
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      this.nextEvictable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      return previousEvictable;
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      this.previousEvictable = previous;
+    }
+  }
+
+  static final class SoftExpirableEvictableEntry<K, V>
+      extends SoftEntry<K, V> implements ReferenceEntry<K, V> {
+    SoftExpirableEvictableEntry(
+        ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(queue, key, hash, next);
+    }
+
+    // The code below is exactly the same for each expirable entry type.
+
+    volatile long time = Long.MAX_VALUE;
+
+    @Override
+    public long getExpirationTime() {
+      return time;
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      this.time = time;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      return nextExpirable;
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      this.nextExpirable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      return previousExpirable;
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      this.previousExpirable = previous;
+    }
+
+    // The code below is exactly the same for each evictable entry type.
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      return nextEvictable;
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      this.nextEvictable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      return previousEvictable;
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      this.previousEvictable = previous;
+    }
+  }
+
+  /**
+   * Used for weakly-referenced keys.
+   */
+  static class WeakEntry<K, V> extends WeakReference<K> implements ReferenceEntry<K, V> {
+    WeakEntry(ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(key, queue);
+      this.hash = hash;
+      this.next = next;
+    }
+
+    @Override
+    public K getKey() {
+      return get();
+    }
+
+    // null expiration
+
+    @Override
+    public long getExpirationTime() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+
+    // null eviction
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      throw new UnsupportedOperationException();
+    }
+
+    // The code below is exactly the same for each entry type.
+
+    final int hash;
+    final ReferenceEntry<K, V> next;
+    volatile ValueReference<K, V> valueReference = unset();
+
+    @Override
+    public ValueReference<K, V> getValueReference() {
+      return valueReference;
+    }
+
+    @Override
+    public void setValueReference(ValueReference<K, V> valueReference) {
+      ValueReference<K, V> previous = this.valueReference;
+      this.valueReference = valueReference;
+      previous.clear(valueReference);
+    }
+
+    @Override
+    public int getHash() {
+      return hash;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getNext() {
+      return next;
+    }
+  }
+
+  static final class WeakExpirableEntry<K, V>
+      extends WeakEntry<K, V> implements ReferenceEntry<K, V> {
+    WeakExpirableEntry(
+        ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(queue, key, hash, next);
+    }
+
+    // The code below is exactly the same for each expirable entry type.
+
+    volatile long time = Long.MAX_VALUE;
+
+    @Override
+    public long getExpirationTime() {
+      return time;
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      this.time = time;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      return nextExpirable;
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      this.nextExpirable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      return previousExpirable;
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      this.previousExpirable = previous;
+    }
+  }
+
+  static final class WeakEvictableEntry<K, V>
+      extends WeakEntry<K, V> implements ReferenceEntry<K, V> {
+    WeakEvictableEntry(
+        ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(queue, key, hash, next);
+    }
+
+    // The code below is exactly the same for each evictable entry type.
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      return nextEvictable;
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      this.nextEvictable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      return previousEvictable;
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      this.previousEvictable = previous;
+    }
+  }
+
+  static final class WeakExpirableEvictableEntry<K, V>
+      extends WeakEntry<K, V> implements ReferenceEntry<K, V> {
+    WeakExpirableEvictableEntry(
+        ReferenceQueue<K> queue, K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      super(queue, key, hash, next);
+    }
+
+    // The code below is exactly the same for each expirable entry type.
+
+    volatile long time = Long.MAX_VALUE;
+
+    @Override
+    public long getExpirationTime() {
+      return time;
+    }
+
+    @Override
+    public void setExpirationTime(long time) {
+      this.time = time;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextExpirable() {
+      return nextExpirable;
+    }
+
+    @Override
+    public void setNextExpirable(ReferenceEntry<K, V> next) {
+      this.nextExpirable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousExpirable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousExpirable() {
+      return previousExpirable;
+    }
+
+    @Override
+    public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+      this.previousExpirable = previous;
+    }
+
+    // The code below is exactly the same for each evictable entry type.
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> nextEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getNextEvictable() {
+      return nextEvictable;
+    }
+
+    @Override
+    public void setNextEvictable(ReferenceEntry<K, V> next) {
+      this.nextEvictable = next;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> previousEvictable = nullEntry();
+
+    @Override
+    public ReferenceEntry<K, V> getPreviousEvictable() {
+      return previousEvictable;
+    }
+
+    @Override
+    public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+      this.previousEvictable = previous;
+    }
+  }
+
+  /**
+   * References a weak value.
+   */
+  static final class WeakValueReference<K, V>
+      extends WeakReference<V> implements ValueReference<K, V> {
+    final ReferenceEntry<K, V> entry;
+
+    WeakValueReference(ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry) {
+      super(referent, queue);
+      this.entry = entry;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getEntry() {
+      return entry;
+    }
+
+    @Override
+    public void clear(ValueReference<K, V> newValue) {
+      clear();
+    }
+
+    @Override
+    public ValueReference<K, V> copyFor(
+        ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
+      return new WeakValueReference<K, V>(queue, value, entry);
+    }
+
+    @Override
+    public boolean isComputingReference() {
+      return false;
+    }
+
+    @Override
+    public V waitForValue() {
+      return get();
+    }
+  }
+
+  /**
+   * References a soft value.
+   */
+  static final class SoftValueReference<K, V>
+      extends SoftReference<V> implements ValueReference<K, V> {
+    final ReferenceEntry<K, V> entry;
+
+    SoftValueReference(ReferenceQueue<V> queue, V referent, ReferenceEntry<K, V> entry) {
+      super(referent, queue);
+      this.entry = entry;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getEntry() {
+      return entry;
+    }
+
+    @Override
+    public void clear(ValueReference<K, V> newValue) {
+      clear();
+    }
+
+    @Override
+    public ValueReference<K, V> copyFor(
+        ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
+      return new SoftValueReference<K, V>(queue, value, entry);
+    }
+
+    @Override
+    public boolean isComputingReference() {
+      return false;
+    }
+
+    @Override
+    public V waitForValue() {
+      return get();
+    }
+  }
+
+  /**
+   * References a strong value.
+   */
+  static final class StrongValueReference<K, V> implements ValueReference<K, V> {
+    final V referent;
+
+    StrongValueReference(V referent) {
+      this.referent = referent;
+    }
+
+    @Override
+    public V get() {
+      return referent;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> getEntry() {
+      return null;
+    }
+
+    @Override
+    public ValueReference<K, V> copyFor(
+        ReferenceQueue<V> queue, V value, ReferenceEntry<K, V> entry) {
+      return this;
+    }
+
+    @Override
+    public boolean isComputingReference() {
+      return false;
+    }
+
+    @Override
+    public V waitForValue() {
+      return get();
+    }
+
+    @Override
+    public void clear(ValueReference<K, V> newValue) {}
+  }
+
+  /**
+   * Applies a supplemental hash function to a given hash code, which defends against poor quality
+   * hash functions. This is critical when the concurrent hash map uses power-of-two length hash
+   * tables, that otherwise encounter collisions for hash codes that do not differ in lower or
+   * upper bits.
+   *
+   * @param h hash code
+   */
+  static int rehash(int h) {
+    // Spread bits to regularize both segment and index locations,
+    // using variant of single-word Wang/Jenkins hash.
+    // TODO(kevinb): use Hashing/move this to Hashing?
+    h += (h << 15) ^ 0xffffcd7d;
+    h ^= (h >>> 10);
+    h += (h << 3);
+    h ^= (h >>> 6);
+    h += (h << 2) + (h << 14);
+    return h ^ (h >>> 16);
+  }
+
+  /**
+   * This method is a convenience for testing. Code should call {@link Segment#newEntry} directly.
+   */
+  @GuardedBy("Segment.this")
+  @VisibleForTesting
+  ReferenceEntry<K, V> newEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+    return segmentFor(hash).newEntry(key, hash, next);
+  }
+
+  /**
+   * This method is a convenience for testing. Code should call {@link Segment#copyEntry} directly.
+   */
+  @GuardedBy("Segment.this")
+  @VisibleForTesting
+  ReferenceEntry<K, V> copyEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+    int hash = original.getHash();
+    return segmentFor(hash).copyEntry(original, newNext);
+  }
+
+  /**
+   * This method is a convenience for testing. Code should call {@link Segment#setValue} instead.
+   */
+  @GuardedBy("Segment.this")
+  @VisibleForTesting
+  ValueReference<K, V> newValueReference(ReferenceEntry<K, V> entry, V value) {
+    int hash = entry.getHash();
+    return valueStrength.referenceValue(segmentFor(hash), entry, value);
+  }
+
+  int hash(Object key) {
+    int h = keyEquivalence.hash(key);
+    return rehash(h);
+  }
+
+  void reclaimValue(ValueReference<K, V> valueReference) {
+    ReferenceEntry<K, V> entry = valueReference.getEntry();
+    int hash = entry.getHash();
+    segmentFor(hash).reclaimValue(entry.getKey(), hash, valueReference);
+  }
+
+  void reclaimKey(ReferenceEntry<K, V> entry) {
+    int hash = entry.getHash();
+    segmentFor(hash).reclaimKey(entry, hash);
+  }
+
+  /**
+   * This method is a convenience for testing. Code should call {@link Segment#getLiveValue}
+   * instead.
+   */
+  @VisibleForTesting
+  boolean isLive(ReferenceEntry<K, V> entry) {
+    return segmentFor(entry.getHash()).getLiveValue(entry) != null;
+  }
+
+  /**
+   * Returns the segment that should be used for a key with the given hash.
+   *
+   * @param hash the hash code for the key
+   * @return the segment
+   */
+  Segment<K, V> segmentFor(int hash) {
+    // TODO(fry): Lazily create segments?
+    return segments[(hash >>> segmentShift) & segmentMask];
+  }
+
+  Segment<K, V> createSegment(int initialCapacity, int maxSegmentSize) {
+    return new Segment<K, V>(this, initialCapacity, maxSegmentSize);
+  }
+
+  /**
+   * Gets the value from an entry. Returns {@code null} if the entry is invalid,
+   * partially-collected, computing, or expired. Unlike {@link Segment#getLiveValue} this method
+   * does not attempt to clean up stale entries.
+   */
+  V getLiveValue(ReferenceEntry<K, V> entry) {
+    if (entry.getKey() == null) {
+      return null;
+    }
+    V value = entry.getValueReference().get();
+    if (value == null) {
+      return null;
+    }
+
+    if (expires() && isExpired(entry)) {
+      return null;
+    }
+    return value;
+  }
+
+  // expiration
+
+  /**
+   * Returns {@code true} if the entry has expired.
+   */
+  boolean isExpired(ReferenceEntry<K, V> entry) {
+    return isExpired(entry, ticker.read());
+  }
+
+  /**
+   * Returns {@code true} if the entry has expired.
+   */
+  boolean isExpired(ReferenceEntry<K, V> entry, long now) {
+    // if the expiration time had overflowed, this "undoes" the overflow
+    return now - entry.getExpirationTime() > 0;
+  }
+
+  @GuardedBy("Segment.this")
+  static <K, V> void connectExpirables(ReferenceEntry<K, V> previous, ReferenceEntry<K, V> next) {
+    previous.setNextExpirable(next);
+    next.setPreviousExpirable(previous);
+  }
+
+  @GuardedBy("Segment.this")
+  static <K, V> void nullifyExpirable(ReferenceEntry<K, V> nulled) {
+    ReferenceEntry<K, V> nullEntry = nullEntry();
+    nulled.setNextExpirable(nullEntry);
+    nulled.setPreviousExpirable(nullEntry);
+  }
+
+  // eviction
+
+  /**
+   * Notifies listeners that an entry has been automatically removed due to expiration, eviction,
+   * or eligibility for garbage collection. This should be called every time expireEntries or
+   * evictEntry is called (once the lock is released).
+   */
+  void processPendingNotifications() {
+    RemovalNotification<K, V> notification;
+    while ((notification = removalNotificationQueue.poll()) != null) {
+      try {
+        removalListener.onRemoval(notification);
+      } catch (Exception e) {
+        logger.log(Level.WARNING, "Exception thrown by removal listener", e);
+      }
+    }
+  }
+
+  /** Links the evitables together. */
+  @GuardedBy("Segment.this")
+  static <K, V> void connectEvictables(ReferenceEntry<K, V> previous, ReferenceEntry<K, V> next) {
+    previous.setNextEvictable(next);
+    next.setPreviousEvictable(previous);
+  }
+
+  @GuardedBy("Segment.this")
+  static <K, V> void nullifyEvictable(ReferenceEntry<K, V> nulled) {
+    ReferenceEntry<K, V> nullEntry = nullEntry();
+    nulled.setNextEvictable(nullEntry);
+    nulled.setPreviousEvictable(nullEntry);
+  }
+
+  @SuppressWarnings("unchecked")
+  final Segment<K, V>[] newSegmentArray(int ssize) {
+    return new Segment[ssize];
+  }
+
+  // Inner Classes
+
+  /**
+   * Segments are specialized versions of hash tables. This subclass inherits from ReentrantLock
+   * opportunistically, just to simplify some locking and avoid separate construction.
+   */
+  @SuppressWarnings("serial") // This class is never serialized.
+  static class Segment<K, V> extends ReentrantLock {
+
+    /*
+     * TODO(fry): Consider copying variables (like evictsBySize) from outer class into this class.
+     * It will require more memory but will reduce indirection.
+     */
+
+    /*
+     * Segments maintain a table of entry lists that are ALWAYS kept in a consistent state, so can
+     * be read without locking. Next fields of nodes are immutable (final). All list additions are
+     * performed at the front of each bin. This makes it easy to check changes, and also fast to
+     * traverse. When nodes would otherwise be changed, new nodes are created to replace them. This
+     * works well for hash tables since the bin lists tend to be short. (The average length is less
+     * than two.)
+     *
+     * Read operations can thus proceed without locking, but rely on selected uses of volatiles to
+     * ensure that completed write operations performed by other threads are noticed. For most
+     * purposes, the "count" field, tracking the number of elements, serves as that volatile
+     * variable ensuring visibility. This is convenient because this field needs to be read in many
+     * read operations anyway:
+     *
+     * - All (unsynchronized) read operations must first read the "count" field, and should not
+     * look at table entries if it is 0.
+     *
+     * - All (synchronized) write operations should write to the "count" field after structurally
+     * changing any bin. The operations must not take any action that could even momentarily
+     * cause a concurrent read operation to see inconsistent data. This is made easier by the
+     * nature of the read operations in Map. For example, no operation can reveal that the table
+     * has grown but the threshold has not yet been updated, so there are no atomicity requirements
+     * for this with respect to reads.
+     *
+     * As a guide, all critical volatile reads and writes to the count field are marked in code
+     * comments.
+     */
+
+    final MapMakerInternalMap<K, V> map;
+
+    /**
+     * The number of live elements in this segment's region. This does not include unset elements
+     * which are awaiting cleanup.
+     */
+    volatile int count;
+
+    /**
+     * Number of updates that alter the size of the table. This is used during bulk-read methods to
+     * make sure they see a consistent snapshot: If modCounts change during a traversal of segments
+     * computing size or checking containsValue, then we might have an inconsistent view of state
+     * so (usually) must retry.
+     */
+    int modCount;
+
+    /**
+     * The table is expanded when its size exceeds this threshold. (The value of this field is
+     * always {@code (int)(capacity * 0.75)}.)
+     */
+    int threshold;
+
+    /**
+     * The per-segment table.
+     */
+    volatile AtomicReferenceArray<ReferenceEntry<K, V>> table;
+
+    /**
+     * The maximum size of this map. MapMaker.UNSET_INT if there is no maximum.
+     */
+    final int maxSegmentSize;
+
+    /**
+     * The key reference queue contains entries whose keys have been garbage collected, and which
+     * need to be cleaned up internally.
+     */
+    final ReferenceQueue<K> keyReferenceQueue;
+
+    /**
+     * The value reference queue contains value references whose values have been garbage collected,
+     * and which need to be cleaned up internally.
+     */
+    final ReferenceQueue<V> valueReferenceQueue;
+
+    /**
+     * The recency queue is used to record which entries were accessed for updating the eviction
+     * list's ordering. It is drained as a batch operation when either the DRAIN_THRESHOLD is
+     * crossed or a write occurs on the segment.
+     */
+    final Queue<ReferenceEntry<K, V>> recencyQueue;
+
+    /**
+     * A counter of the number of reads since the last write, used to drain queues on a small
+     * fraction of read operations.
+     */
+    final AtomicInteger readCount = new AtomicInteger();
+
+    /**
+     * A queue of elements currently in the map, ordered by access time. Elements are added to the
+     * tail of the queue on access/write.
+     */
+    @GuardedBy("Segment.this")
+    final Queue<ReferenceEntry<K, V>> evictionQueue;
+
+    /**
+     * A queue of elements currently in the map, ordered by expiration time (either access or write
+     * time). Elements are added to the tail of the queue on access/write.
+     */
+    @GuardedBy("Segment.this")
+    final Queue<ReferenceEntry<K, V>> expirationQueue;
+
+    Segment(MapMakerInternalMap<K, V> map, int initialCapacity, int maxSegmentSize) {
+      this.map = map;
+      this.maxSegmentSize = maxSegmentSize;
+      initTable(newEntryArray(initialCapacity));
+
+      keyReferenceQueue = map.usesKeyReferences()
+           ? new ReferenceQueue<K>() : null;
+
+      valueReferenceQueue = map.usesValueReferences()
+           ? new ReferenceQueue<V>() : null;
+
+      recencyQueue = (map.evictsBySize() || map.expiresAfterAccess())
+          ? new ConcurrentLinkedQueue<ReferenceEntry<K, V>>()
+          : MapMakerInternalMap.<ReferenceEntry<K, V>>discardingQueue();
+
+      evictionQueue = map.evictsBySize()
+          ? new EvictionQueue<K, V>()
+          : MapMakerInternalMap.<ReferenceEntry<K, V>>discardingQueue();
+
+      expirationQueue = map.expires()
+          ? new ExpirationQueue<K, V>()
+          : MapMakerInternalMap.<ReferenceEntry<K, V>>discardingQueue();
+    }
+
+    AtomicReferenceArray<ReferenceEntry<K, V>> newEntryArray(int size) {
+      return new AtomicReferenceArray<ReferenceEntry<K, V>>(size);
+    }
+
+    void initTable(AtomicReferenceArray<ReferenceEntry<K, V>> newTable) {
+      this.threshold = newTable.length() * 3 / 4; // 0.75
+      if (this.threshold == maxSegmentSize) {
+        // prevent spurious expansion before eviction
+        this.threshold++;
+      }
+      this.table = newTable;
+    }
+
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> newEntry(K key, int hash, @Nullable ReferenceEntry<K, V> next) {
+      return map.entryFactory.newEntry(this, key, hash, next);
+    }
+
+    /**
+     * Copies {@code original} into a new entry chained to {@code newNext}. Returns the new entry,
+     * or {@code null} if {@code original} was already garbage collected.
+     */
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> copyEntry(ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) {
+      if (original.getKey() == null) {
+        // key collected
+        return null;
+      }
+
+      ValueReference<K, V> valueReference = original.getValueReference();
+      V value = valueReference.get();
+      if ((value == null) && !valueReference.isComputingReference()) {
+        // value collected
+        return null;
+      }
+
+      ReferenceEntry<K, V> newEntry = map.entryFactory.copyEntry(this, original, newNext);
+      newEntry.setValueReference(valueReference.copyFor(this.valueReferenceQueue, value, newEntry));
+      return newEntry;
+    }
+
+    /**
+     * Sets a new value of an entry. Adds newly created entries at the end of the expiration queue.
+     */
+    @GuardedBy("Segment.this")
+    void setValue(ReferenceEntry<K, V> entry, V value) {
+      ValueReference<K, V> valueReference = map.valueStrength.referenceValue(this, entry, value);
+      entry.setValueReference(valueReference);
+      recordWrite(entry);
+    }
+
+    // reference queues, for garbage collection cleanup
+
+    /**
+     * Cleanup collected entries when the lock is available.
+     */
+    void tryDrainReferenceQueues() {
+      if (tryLock()) {
+        try {
+          drainReferenceQueues();
+        } finally {
+          unlock();
+        }
+      }
+    }
+
+    /**
+     * Drain the key and value reference queues, cleaning up internal entries containing garbage
+     * collected keys or values.
+     */
+    @GuardedBy("Segment.this")
+    void drainReferenceQueues() {
+      if (map.usesKeyReferences()) {
+        drainKeyReferenceQueue();
+      }
+      if (map.usesValueReferences()) {
+        drainValueReferenceQueue();
+      }
+    }
+
+    @GuardedBy("Segment.this")
+    void drainKeyReferenceQueue() {
+      Reference<? extends K> ref;
+      int i = 0;
+      while ((ref = keyReferenceQueue.poll()) != null) {
+        @SuppressWarnings("unchecked")
+        ReferenceEntry<K, V> entry = (ReferenceEntry<K, V>) ref;
+        map.reclaimKey(entry);
+        if (++i == DRAIN_MAX) {
+          break;
+        }
+      }
+    }
+
+    @GuardedBy("Segment.this")
+    void drainValueReferenceQueue() {
+      Reference<? extends V> ref;
+      int i = 0;
+      while ((ref = valueReferenceQueue.poll()) != null) {
+        @SuppressWarnings("unchecked")
+        ValueReference<K, V> valueReference = (ValueReference<K, V>) ref;
+        map.reclaimValue(valueReference);
+        if (++i == DRAIN_MAX) {
+          break;
+        }
+      }
+    }
+
+    /**
+     * Clears all entries from the key and value reference queues.
+     */
+    void clearReferenceQueues() {
+      if (map.usesKeyReferences()) {
+        clearKeyReferenceQueue();
+      }
+      if (map.usesValueReferences()) {
+        clearValueReferenceQueue();
+      }
+    }
+
+    void clearKeyReferenceQueue() {
+      while (keyReferenceQueue.poll() != null) {}
+    }
+
+    void clearValueReferenceQueue() {
+      while (valueReferenceQueue.poll() != null) {}
+    }
+
+    // recency queue, shared by expiration and eviction
+
+    /**
+     * Records the relative order in which this read was performed by adding {@code entry} to the
+     * recency queue. At write-time, or when the queue is full past the threshold, the queue will
+     * be drained and the entries therein processed.
+     *
+     * <p>Note: locked reads should use {@link #recordLockedRead}.
+     */
+    void recordRead(ReferenceEntry<K, V> entry) {
+      if (map.expiresAfterAccess()) {
+        recordExpirationTime(entry, map.expireAfterAccessNanos);
+      }
+      recencyQueue.add(entry);
+    }
+
+    /**
+     * Updates the eviction metadata that {@code entry} was just read. This currently amounts to
+     * adding {@code entry} to relevant eviction lists.
+     *
+     * <p>Note: this method should only be called under lock, as it directly manipulates the
+     * eviction queues. Unlocked reads should use {@link #recordRead}.
+     */
+    @GuardedBy("Segment.this")
+    void recordLockedRead(ReferenceEntry<K, V> entry) {
+      evictionQueue.add(entry);
+      if (map.expiresAfterAccess()) {
+        recordExpirationTime(entry, map.expireAfterAccessNanos);
+        expirationQueue.add(entry);
+      }
+    }
+
+    /**
+     * Updates eviction metadata that {@code entry} was just written. This currently amounts to
+     * adding {@code entry} to relevant eviction lists.
+     */
+    @GuardedBy("Segment.this")
+    void recordWrite(ReferenceEntry<K, V> entry) {
+      // we are already under lock, so drain the recency queue immediately
+      drainRecencyQueue();
+      evictionQueue.add(entry);
+      if (map.expires()) {
+        // currently MapMaker ensures that expireAfterWrite and
+        // expireAfterAccess are mutually exclusive
+        long expiration = map.expiresAfterAccess()
+            ? map.expireAfterAccessNanos
+            : map.expireAfterWriteNanos;
+        recordExpirationTime(entry, expiration);
+        expirationQueue.add(entry);
+      }
+    }
+
+    /**
+     * Drains the recency queue, updating eviction metadata that the entries therein were read in
+     * the specified relative order. This currently amounts to adding them to relevant eviction
+     * lists (accounting for the fact that they could have been removed from the map since being
+     * added to the recency queue).
+     */
+    @GuardedBy("Segment.this")
+    void drainRecencyQueue() {
+      ReferenceEntry<K, V> e;
+      while ((e = recencyQueue.poll()) != null) {
+        // An entry may be in the recency queue despite it being removed from
+        // the map . This can occur when the entry was concurrently read while a
+        // writer is removing it from the segment or after a clear has removed
+        // all of the segment's entries.
+        if (evictionQueue.contains(e)) {
+          evictionQueue.add(e);
+        }
+        if (map.expiresAfterAccess() && expirationQueue.contains(e)) {
+          expirationQueue.add(e);
+        }
+      }
+    }
+
+    // expiration
+
+    void recordExpirationTime(ReferenceEntry<K, V> entry, long expirationNanos) {
+      // might overflow, but that's okay (see isExpired())
+      entry.setExpirationTime(map.ticker.read() + expirationNanos);
+    }
+
+    /**
+     * Cleanup expired entries when the lock is available.
+     */
+    void tryExpireEntries() {
+      if (tryLock()) {
+        try {
+          expireEntries();
+        } finally {
+          unlock();
+          // don't call postWriteCleanup as we're in a read
+        }
+      }
+    }
+
+    @GuardedBy("Segment.this")
+    void expireEntries() {
+      drainRecencyQueue();
+
+      if (expirationQueue.isEmpty()) {
+        // There's no point in calling nanoTime() if we have no entries to
+        // expire.
+        return;
+      }
+      long now = map.ticker.read();
+      ReferenceEntry<K, V> e;
+      while ((e = expirationQueue.peek()) != null && map.isExpired(e, now)) {
+        if (!removeEntry(e, e.getHash(), RemovalCause.EXPIRED)) {
+          throw new AssertionError();
+        }
+      }
+    }
+
+    // eviction
+
+    void enqueueNotification(ReferenceEntry<K, V> entry, RemovalCause cause) {
+      enqueueNotification(entry.getKey(), entry.getHash(), entry.getValueReference().get(), cause);
+    }
+
+    void enqueueNotification(@Nullable K key, int hash, @Nullable V value, RemovalCause cause) {
+      if (map.removalNotificationQueue != DISCARDING_QUEUE) {
+        RemovalNotification<K, V> notification = new RemovalNotification<K, V>(key, value, cause);
+        map.removalNotificationQueue.offer(notification);
+      }
+    }
+
+    /**
+     * Performs eviction if the segment is full. This should only be called prior to adding a new
+     * entry and increasing {@code count}.
+     *
+     * @return {@code true} if eviction occurred
+     */
+    @GuardedBy("Segment.this")
+    boolean evictEntries() {
+      if (map.evictsBySize() && count >= maxSegmentSize) {
+        drainRecencyQueue();
+
+        ReferenceEntry<K, V> e = evictionQueue.remove();
+        if (!removeEntry(e, e.getHash(), RemovalCause.SIZE)) {
+          throw new AssertionError();
+        }
+        return true;
+      }
+      return false;
+    }
+
+    /**
+     * Returns first entry of bin for given hash.
+     */
+    ReferenceEntry<K, V> getFirst(int hash) {
+      // read this volatile field only once
+      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+      return table.get(hash & (table.length() - 1));
+    }
+
+    // Specialized implementations of map methods
+
+    ReferenceEntry<K, V> getEntry(Object key, int hash) {
+      if (count != 0) { // read-volatile
+        for (ReferenceEntry<K, V> e = getFirst(hash); e != null; e = e.getNext()) {
+          if (e.getHash() != hash) {
+            continue;
+          }
+
+          K entryKey = e.getKey();
+          if (entryKey == null) {
+            tryDrainReferenceQueues();
+            continue;
+          }
+
+          if (map.keyEquivalence.equivalent(key, entryKey)) {
+            return e;
+          }
+        }
+      }
+
+      return null;
+    }
+
+    ReferenceEntry<K, V> getLiveEntry(Object key, int hash) {
+      ReferenceEntry<K, V> e = getEntry(key, hash);
+      if (e == null) {
+        return null;
+      } else if (map.expires() && map.isExpired(e)) {
+        tryExpireEntries();
+        return null;
+      }
+      return e;
+    }
+
+    V get(Object key, int hash) {
+      try {
+        ReferenceEntry<K, V> e = getLiveEntry(key, hash);
+        if (e == null) {
+          return null;
+        }
+
+        V value = e.getValueReference().get();
+        if (value != null) {
+          recordRead(e);
+        } else {
+          tryDrainReferenceQueues();
+        }
+        return value;
+      } finally {
+        postReadCleanup();
+      }
+    }
+
+    boolean containsKey(Object key, int hash) {
+      try {
+        if (count != 0) { // read-volatile
+          ReferenceEntry<K, V> e = getLiveEntry(key, hash);
+          if (e == null) {
+            return false;
+          }
+          return e.getValueReference().get() != null;
+        }
+
+        return false;
+      } finally {
+        postReadCleanup();
+      }
+    }
+
+    /**
+     * This method is a convenience for testing. Code should call {@link
+     * MapMakerInternalMap#containsValue} directly.
+     */
+    @VisibleForTesting
+    boolean containsValue(Object value) {
+      try {
+        if (count != 0) { // read-volatile
+          AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+          int length = table.length();
+          for (int i = 0; i < length; ++i) {
+            for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
+              V entryValue = getLiveValue(e);
+              if (entryValue == null) {
+                continue;
+              }
+              if (map.valueEquivalence.equivalent(value, entryValue)) {
+                return true;
+              }
+            }
+          }
+        }
+
+        return false;
+      } finally {
+        postReadCleanup();
+      }
+    }
+
+    V put(K key, int hash, V value, boolean onlyIfAbsent) {
+      lock();
+      try {
+        preWriteCleanup();
+
+        int newCount = this.count + 1;
+        if (newCount > this.threshold) { // ensure capacity
+          expand();
+          newCount = this.count + 1;
+        }
+
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        // Look for an existing entry.
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          K entryKey = e.getKey();
+          if (e.getHash() == hash && entryKey != null
+              && map.keyEquivalence.equivalent(key, entryKey)) {
+            // We found an existing entry.
+
+            ValueReference<K, V> valueReference = e.getValueReference();
+            V entryValue = valueReference.get();
+
+            if (entryValue == null) {
+              ++modCount;
+              setValue(e, value);
+              if (!valueReference.isComputingReference()) {
+                enqueueNotification(key, hash, entryValue, RemovalCause.COLLECTED);
+                newCount = this.count; // count remains unchanged
+              } else if (evictEntries()) { // evictEntries after setting new value
+                newCount = this.count + 1;
+              }
+              this.count = newCount; // write-volatile
+              return null;
+            } else if (onlyIfAbsent) {
+              // Mimic
+              // "if (!map.containsKey(key)) ...
+              // else return map.get(key);
+              recordLockedRead(e);
+              return entryValue;
+            } else {
+              // clobber existing entry, count remains unchanged
+              ++modCount;
+              enqueueNotification(key, hash, entryValue, RemovalCause.REPLACED);
+              setValue(e, value);
+              return entryValue;
+            }
+          }
+        }
+
+        // Create a new entry.
+        ++modCount;
+        ReferenceEntry<K, V> newEntry = newEntry(key, hash, first);
+        setValue(newEntry, value);
+        table.set(index, newEntry);
+        if (evictEntries()) { // evictEntries after setting new value
+          newCount = this.count + 1;
+        }
+        this.count = newCount; // write-volatile
+        return null;
+      } finally {
+        unlock();
+        postWriteCleanup();
+      }
+    }
+
+    /**
+     * Expands the table if possible.
+     */
+    @GuardedBy("Segment.this")
+    void expand() {
+      AtomicReferenceArray<ReferenceEntry<K, V>> oldTable = table;
+      int oldCapacity = oldTable.length();
+      if (oldCapacity >= MAXIMUM_CAPACITY) {
+        return;
+      }
+
+      /*
+       * Reclassify nodes in each list to new Map. Because we are using power-of-two expansion, the
+       * elements from each bin must either stay at same index, or move with a power of two offset.
+       * We eliminate unnecessary node creation by catching cases where old nodes can be reused
+       * because their next fields won't change. Statistically, at the default threshold, only
+       * about one-sixth of them need cloning when a table doubles. The nodes they replace will be
+       * garbage collectable as soon as they are no longer referenced by any reader thread that may
+       * be in the midst of traversing table right now.
+       */
+
+      int newCount = count;
+      AtomicReferenceArray<ReferenceEntry<K, V>> newTable = newEntryArray(oldCapacity << 1);
+      threshold = newTable.length() * 3 / 4;
+      int newMask = newTable.length() - 1;
+      for (int oldIndex = 0; oldIndex < oldCapacity; ++oldIndex) {
+        // We need to guarantee that any existing reads of old Map can
+        // proceed. So we cannot yet null out each bin.
+        ReferenceEntry<K, V> head = oldTable.get(oldIndex);
+
+        if (head != null) {
+          ReferenceEntry<K, V> next = head.getNext();
+          int headIndex = head.getHash() & newMask;
+
+          // Single node on list
+          if (next == null) {
+            newTable.set(headIndex, head);
+          } else {
+            // Reuse the consecutive sequence of nodes with the same target
+            // index from the end of the list. tail points to the first
+            // entry in the reusable list.
+            ReferenceEntry<K, V> tail = head;
+            int tailIndex = headIndex;
+            for (ReferenceEntry<K, V> e = next; e != null; e = e.getNext()) {
+              int newIndex = e.getHash() & newMask;
+              if (newIndex != tailIndex) {
+                // The index changed. We'll need to copy the previous entry.
+                tailIndex = newIndex;
+                tail = e;
+              }
+            }
+            newTable.set(tailIndex, tail);
+
+            // Clone nodes leading up to the tail.
+            for (ReferenceEntry<K, V> e = head; e != tail; e = e.getNext()) {
+              int newIndex = e.getHash() & newMask;
+              ReferenceEntry<K, V> newNext = newTable.get(newIndex);
+              ReferenceEntry<K, V> newFirst = copyEntry(e, newNext);
+              if (newFirst != null) {
+                newTable.set(newIndex, newFirst);
+              } else {
+                removeCollectedEntry(e);
+                newCount--;
+              }
+            }
+          }
+        }
+      }
+      table = newTable;
+      this.count = newCount;
+    }
+
+    boolean replace(K key, int hash, V oldValue, V newValue) {
+      lock();
+      try {
+        preWriteCleanup();
+
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          K entryKey = e.getKey();
+          if (e.getHash() == hash && entryKey != null
+              && map.keyEquivalence.equivalent(key, entryKey)) {
+            // If the value disappeared, this entry is partially collected,
+            // and we should pretend like it doesn't exist.
+            ValueReference<K, V> valueReference = e.getValueReference();
+            V entryValue = valueReference.get();
+            if (entryValue == null) {
+              if (isCollected(valueReference)) {
+                int newCount = this.count - 1;
+                ++modCount;
+                enqueueNotification(entryKey, hash, entryValue, RemovalCause.COLLECTED);
+                ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+                newCount = this.count - 1;
+                table.set(index, newFirst);
+                this.count = newCount; // write-volatile
+              }
+              return false;
+            }
+
+            if (map.valueEquivalence.equivalent(oldValue, entryValue)) {
+              ++modCount;
+              enqueueNotification(key, hash, entryValue, RemovalCause.REPLACED);
+              setValue(e, newValue);
+              return true;
+            } else {
+              // Mimic
+              // "if (map.containsKey(key) && map.get(key).equals(oldValue))..."
+              recordLockedRead(e);
+              return false;
+            }
+          }
+        }
+
+        return false;
+      } finally {
+        unlock();
+        postWriteCleanup();
+      }
+    }
+
+    V replace(K key, int hash, V newValue) {
+      lock();
+      try {
+        preWriteCleanup();
+
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          K entryKey = e.getKey();
+          if (e.getHash() == hash && entryKey != null
+              && map.keyEquivalence.equivalent(key, entryKey)) {
+            // If the value disappeared, this entry is partially collected,
+            // and we should pretend like it doesn't exist.
+            ValueReference<K, V> valueReference = e.getValueReference();
+            V entryValue = valueReference.get();
+            if (entryValue == null) {
+              if (isCollected(valueReference)) {
+                int newCount = this.count - 1;
+                ++modCount;
+                enqueueNotification(entryKey, hash, entryValue, RemovalCause.COLLECTED);
+                ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+                newCount = this.count - 1;
+                table.set(index, newFirst);
+                this.count = newCount; // write-volatile
+              }
+              return null;
+            }
+
+            ++modCount;
+            enqueueNotification(key, hash, entryValue, RemovalCause.REPLACED);
+            setValue(e, newValue);
+            return entryValue;
+          }
+        }
+
+        return null;
+      } finally {
+        unlock();
+        postWriteCleanup();
+      }
+    }
+
+    V remove(Object key, int hash) {
+      lock();
+      try {
+        preWriteCleanup();
+
+        int newCount = this.count - 1;
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          K entryKey = e.getKey();
+          if (e.getHash() == hash && entryKey != null
+              && map.keyEquivalence.equivalent(key, entryKey)) {
+            ValueReference<K, V> valueReference = e.getValueReference();
+            V entryValue = valueReference.get();
+
+            RemovalCause cause;
+            if (entryValue != null) {
+              cause = RemovalCause.EXPLICIT;
+            } else if (isCollected(valueReference)) {
+              cause = RemovalCause.COLLECTED;
+            } else {
+              return null;
+            }
+
+            ++modCount;
+            enqueueNotification(entryKey, hash, entryValue, cause);
+            ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+            newCount = this.count - 1;
+            table.set(index, newFirst);
+            this.count = newCount; // write-volatile
+            return entryValue;
+          }
+        }
+
+        return null;
+      } finally {
+        unlock();
+        postWriteCleanup();
+      }
+    }
+
+    boolean remove(Object key, int hash, Object value) {
+      lock();
+      try {
+        preWriteCleanup();
+
+        int newCount = this.count - 1;
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          K entryKey = e.getKey();
+          if (e.getHash() == hash && entryKey != null
+              && map.keyEquivalence.equivalent(key, entryKey)) {
+            ValueReference<K, V> valueReference = e.getValueReference();
+            V entryValue = valueReference.get();
+
+            RemovalCause cause;
+            if (map.valueEquivalence.equivalent(value, entryValue)) {
+              cause = RemovalCause.EXPLICIT;
+            } else if (isCollected(valueReference)) {
+              cause = RemovalCause.COLLECTED;
+            } else {
+              return false;
+            }
+
+            ++modCount;
+            enqueueNotification(entryKey, hash, entryValue, cause);
+            ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+            newCount = this.count - 1;
+            table.set(index, newFirst);
+            this.count = newCount; // write-volatile
+            return (cause == RemovalCause.EXPLICIT);
+          }
+        }
+
+        return false;
+      } finally {
+        unlock();
+        postWriteCleanup();
+      }
+    }
+
+    void clear() {
+      if (count != 0) {
+        lock();
+        try {
+          AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+          if (map.removalNotificationQueue != DISCARDING_QUEUE) {
+            for (int i = 0; i < table.length(); ++i) {
+              for (ReferenceEntry<K, V> e = table.get(i); e != null; e = e.getNext()) {
+                // Computing references aren't actually in the map yet.
+                if (!e.getValueReference().isComputingReference()) {
+                  enqueueNotification(e, RemovalCause.EXPLICIT);
+                }
+              }
+            }
+          }
+          for (int i = 0; i < table.length(); ++i) {
+            table.set(i, null);
+          }
+          clearReferenceQueues();
+          evictionQueue.clear();
+          expirationQueue.clear();
+          readCount.set(0);
+
+          ++modCount;
+          count = 0; // write-volatile
+        } finally {
+          unlock();
+          postWriteCleanup();
+        }
+      }
+    }
+
+    /**
+     * Removes an entry from within a table. All entries following the removed node can stay, but
+     * all preceding ones need to be cloned.
+     *
+     * <p>This method does not decrement count for the removed entry, but does decrement count for
+     * all partially collected entries which are skipped. As such callers which are modifying count
+     * must re-read it after calling removeFromChain.
+     *
+     * @param first the first entry of the table
+     * @param entry the entry being removed from the table
+     * @return the new first entry for the table
+     */
+    @GuardedBy("Segment.this")
+    ReferenceEntry<K, V> removeFromChain(ReferenceEntry<K, V> first, ReferenceEntry<K, V> entry) {
+      evictionQueue.remove(entry);
+      expirationQueue.remove(entry);
+
+      int newCount = count;
+      ReferenceEntry<K, V> newFirst = entry.getNext();
+      for (ReferenceEntry<K, V> e = first; e != entry; e = e.getNext()) {
+        ReferenceEntry<K, V> next = copyEntry(e, newFirst);
+        if (next != null) {
+          newFirst = next;
+        } else {
+          removeCollectedEntry(e);
+          newCount--;
+        }
+      }
+      this.count = newCount;
+      return newFirst;
+    }
+
+    void removeCollectedEntry(ReferenceEntry<K, V> entry) {
+      enqueueNotification(entry, RemovalCause.COLLECTED);
+      evictionQueue.remove(entry);
+      expirationQueue.remove(entry);
+    }
+
+    /**
+     * Removes an entry whose key has been garbage collected.
+     */
+    boolean reclaimKey(ReferenceEntry<K, V> entry, int hash) {
+      lock();
+      try {
+        int newCount = count - 1;
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          if (e == entry) {
+            ++modCount;
+            enqueueNotification(
+                e.getKey(), hash, e.getValueReference().get(), RemovalCause.COLLECTED);
+            ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+            newCount = this.count - 1;
+            table.set(index, newFirst);
+            this.count = newCount; // write-volatile
+            return true;
+          }
+        }
+
+        return false;
+      } finally {
+        unlock();
+        postWriteCleanup();
+      }
+    }
+
+    /**
+     * Removes an entry whose value has been garbage collected.
+     */
+    boolean reclaimValue(K key, int hash, ValueReference<K, V> valueReference) {
+      lock();
+      try {
+        int newCount = this.count - 1;
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          K entryKey = e.getKey();
+          if (e.getHash() == hash && entryKey != null
+              && map.keyEquivalence.equivalent(key, entryKey)) {
+            ValueReference<K, V> v = e.getValueReference();
+            if (v == valueReference) {
+              ++modCount;
+              enqueueNotification(key, hash, valueReference.get(), RemovalCause.COLLECTED);
+              ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+              newCount = this.count - 1;
+              table.set(index, newFirst);
+              this.count = newCount; // write-volatile
+              return true;
+            }
+            return false;
+          }
+        }
+
+        return false;
+      } finally {
+        unlock();
+        if (!isHeldByCurrentThread()) { // don't cleanup inside of put
+          postWriteCleanup();
+        }
+      }
+    }
+
+    /**
+     * Clears a value that has not yet been set, and thus does not require count to be modified.
+     */
+    boolean clearValue(K key, int hash, ValueReference<K, V> valueReference) {
+      lock();
+      try {
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+        int index = hash & (table.length() - 1);
+        ReferenceEntry<K, V> first = table.get(index);
+
+        for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+          K entryKey = e.getKey();
+          if (e.getHash() == hash && entryKey != null
+              && map.keyEquivalence.equivalent(key, entryKey)) {
+            ValueReference<K, V> v = e.getValueReference();
+            if (v == valueReference) {
+              ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+              table.set(index, newFirst);
+              return true;
+            }
+            return false;
+          }
+        }
+
+        return false;
+      } finally {
+        unlock();
+        postWriteCleanup();
+      }
+    }
+
+    @GuardedBy("Segment.this")
+    boolean removeEntry(ReferenceEntry<K, V> entry, int hash, RemovalCause cause) {
+      int newCount = this.count - 1;
+      AtomicReferenceArray<ReferenceEntry<K, V>> table = this.table;
+      int index = hash & (table.length() - 1);
+      ReferenceEntry<K, V> first = table.get(index);
+
+      for (ReferenceEntry<K, V> e = first; e != null; e = e.getNext()) {
+        if (e == entry) {
+          ++modCount;
+          enqueueNotification(e.getKey(), hash, e.getValueReference().get(), cause);
+          ReferenceEntry<K, V> newFirst = removeFromChain(first, e);
+          newCount = this.count - 1;
+          table.set(index, newFirst);
+          this.count = newCount; // write-volatile
+          return true;
+        }
+      }
+
+      return false;
+    }
+
+    /**
+     * Returns {@code true} if the entry has been partially collected, meaning that either the key
+     * is null, or the value is null and it is not computing.
+     */
+    boolean isCollected(ReferenceEntry<K, V> entry) {
+      if (entry.getKey() == null) {
+        return true;
+      }
+      return isCollected(entry.getValueReference());
+    }
+
+    /**
+     * Returns {@code true} if the value has been partially collected, meaning that the value is
+     * null and it is not computing.
+     */
+    boolean isCollected(ValueReference<K, V> valueReference) {
+      if (valueReference.isComputingReference()) {
+        return false;
+      }
+      return (valueReference.get() == null);
+    }
+
+    /**
+     * Gets the value from an entry. Returns {@code null} if the entry is invalid,
+     * partially-collected, computing, or expired.
+     */
+    V getLiveValue(ReferenceEntry<K, V> entry) {
+      if (entry.getKey() == null) {
+        tryDrainReferenceQueues();
+        return null;
+      }
+      V value = entry.getValueReference().get();
+      if (value == null) {
+        tryDrainReferenceQueues();
+        return null;
+      }
+
+      if (map.expires() && map.isExpired(entry)) {
+        tryExpireEntries();
+        return null;
+      }
+      return value;
+    }
+
+    /**
+     * Performs routine cleanup following a read. Normally cleanup happens during writes, or from
+     * the cleanupExecutor. If cleanup is not observed after a sufficient number of reads, try
+     * cleaning up from the read thread.
+     */
+    void postReadCleanup() {
+      if ((readCount.incrementAndGet() & DRAIN_THRESHOLD) == 0) {
+        runCleanup();
+      }
+    }
+
+    /**
+     * Performs routine cleanup prior to executing a write. This should be called every time a
+     * write thread acquires the segment lock, immediately after acquiring the lock.
+     *
+     * <p>Post-condition: expireEntries has been run.
+     */
+    @GuardedBy("Segment.this")
+    void preWriteCleanup() {
+      runLockedCleanup();
+    }
+
+    /**
+     * Performs routine cleanup following a write.
+     */
+    void postWriteCleanup() {
+      runUnlockedCleanup();
+    }
+
+    void runCleanup() {
+      runLockedCleanup();
+      runUnlockedCleanup();
+    }
+
+    void runLockedCleanup() {
+      if (tryLock()) {
+        try {
+          drainReferenceQueues();
+          expireEntries(); // calls drainRecencyQueue
+          readCount.set(0);
+        } finally {
+          unlock();
+        }
+      }
+    }
+
+    void runUnlockedCleanup() {
+      // locked cleanup may generate notifications we can send unlocked
+      if (!isHeldByCurrentThread()) {
+        map.processPendingNotifications();
+      }
+    }
+
+  }
+
+  // Queues
+
+  /**
+   * A custom queue for managing eviction order. Note that this is tightly integrated with {@code
+   * ReferenceEntry}, upon which it relies to perform its linking.
+   *
+   * <p>Note that this entire implementation makes the assumption that all elements which are in
+   * the map are also in this queue, and that all elements not in the queue are not in the map.
+   *
+   * <p>The benefits of creating our own queue are that (1) we can replace elements in the middle
+   * of the queue as part of copyEvictableEntry, and (2) the contains method is highly optimized
+   * for the current model.
+   */
+  static final class EvictionQueue<K, V> extends AbstractQueue<ReferenceEntry<K, V>> {
+    final ReferenceEntry<K, V> head = new AbstractReferenceEntry<K, V>() {
+
+      ReferenceEntry<K, V> nextEvictable = this;
+
+      @Override
+      public ReferenceEntry<K, V> getNextEvictable() {
+        return nextEvictable;
+      }
+
+      @Override
+      public void setNextEvictable(ReferenceEntry<K, V> next) {
+        this.nextEvictable = next;
+      }
+
+      ReferenceEntry<K, V> previousEvictable = this;
+
+      @Override
+      public ReferenceEntry<K, V> getPreviousEvictable() {
+        return previousEvictable;
+      }
+
+      @Override
+      public void setPreviousEvictable(ReferenceEntry<K, V> previous) {
+        this.previousEvictable = previous;
+      }
+    };
+
+    // implements Queue
+
+    @Override
+    public boolean offer(ReferenceEntry<K, V> entry) {
+      // unlink
+      connectEvictables(entry.getPreviousEvictable(), entry.getNextEvictable());
+
+      // add to tail
+      connectEvictables(head.getPreviousEvictable(), entry);
+      connectEvictables(entry, head);
+
+      return true;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> peek() {
+      ReferenceEntry<K, V> next = head.getNextEvictable();
+      return (next == head) ? null : next;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> poll() {
+      ReferenceEntry<K, V> next = head.getNextEvictable();
+      if (next == head) {
+        return null;
+      }
+
+      remove(next);
+      return next;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public boolean remove(Object o) {
+      ReferenceEntry<K, V> e = (ReferenceEntry) o;
+      ReferenceEntry<K, V> previous = e.getPreviousEvictable();
+      ReferenceEntry<K, V> next = e.getNextEvictable();
+      connectEvictables(previous, next);
+      nullifyEvictable(e);
+
+      return next != NullEntry.INSTANCE;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public boolean contains(Object o) {
+      ReferenceEntry<K, V> e = (ReferenceEntry) o;
+      return e.getNextEvictable() != NullEntry.INSTANCE;
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return head.getNextEvictable() == head;
+    }
+
+    @Override
+    public int size() {
+      int size = 0;
+      for (ReferenceEntry<K, V> e = head.getNextEvictable(); e != head; e = e.getNextEvictable()) {
+        size++;
+      }
+      return size;
+    }
+
+    @Override
+    public void clear() {
+      ReferenceEntry<K, V> e = head.getNextEvictable();
+      while (e != head) {
+        ReferenceEntry<K, V> next = e.getNextEvictable();
+        nullifyEvictable(e);
+        e = next;
+      }
+
+      head.setNextEvictable(head);
+      head.setPreviousEvictable(head);
+    }
+
+    @Override
+    public Iterator<ReferenceEntry<K, V>> iterator() {
+      return new AbstractSequentialIterator<ReferenceEntry<K, V>>(peek()) {
+        @Override
+        protected ReferenceEntry<K, V> computeNext(ReferenceEntry<K, V> previous) {
+          ReferenceEntry<K, V> next = previous.getNextEvictable();
+          return (next == head) ? null : next;
+        }
+      };
+    }
+  }
+
+  /**
+   * A custom queue for managing expiration order. Note that this is tightly integrated with
+   * {@code ReferenceEntry}, upon which it reliese to perform its linking.
+   *
+   * <p>Note that this entire implementation makes the assumption that all elements which are in
+   * the map are also in this queue, and that all elements not in the queue are not in the map.
+   *
+   * <p>The benefits of creating our own queue are that (1) we can replace elements in the middle
+   * of the queue as part of copyEvictableEntry, and (2) the contains method is highly optimized
+   * for the current model.
+   */
+  static final class ExpirationQueue<K, V> extends AbstractQueue<ReferenceEntry<K, V>> {
+    final ReferenceEntry<K, V> head = new AbstractReferenceEntry<K, V>() {
+
+      @Override
+      public long getExpirationTime() {
+        return Long.MAX_VALUE;
+      }
+
+      @Override
+      public void setExpirationTime(long time) {}
+
+      ReferenceEntry<K, V> nextExpirable = this;
+
+      @Override
+      public ReferenceEntry<K, V> getNextExpirable() {
+        return nextExpirable;
+      }
+
+      @Override
+      public void setNextExpirable(ReferenceEntry<K, V> next) {
+        this.nextExpirable = next;
+      }
+
+      ReferenceEntry<K, V> previousExpirable = this;
+
+      @Override
+      public ReferenceEntry<K, V> getPreviousExpirable() {
+        return previousExpirable;
+      }
+
+      @Override
+      public void setPreviousExpirable(ReferenceEntry<K, V> previous) {
+        this.previousExpirable = previous;
+      }
+    };
+
+    // implements Queue
+
+    @Override
+    public boolean offer(ReferenceEntry<K, V> entry) {
+      // unlink
+      connectExpirables(entry.getPreviousExpirable(), entry.getNextExpirable());
+
+      // add to tail
+      connectExpirables(head.getPreviousExpirable(), entry);
+      connectExpirables(entry, head);
+
+      return true;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> peek() {
+      ReferenceEntry<K, V> next = head.getNextExpirable();
+      return (next == head) ? null : next;
+    }
+
+    @Override
+    public ReferenceEntry<K, V> poll() {
+      ReferenceEntry<K, V> next = head.getNextExpirable();
+      if (next == head) {
+        return null;
+      }
+
+      remove(next);
+      return next;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public boolean remove(Object o) {
+      ReferenceEntry<K, V> e = (ReferenceEntry) o;
+      ReferenceEntry<K, V> previous = e.getPreviousExpirable();
+      ReferenceEntry<K, V> next = e.getNextExpirable();
+      connectExpirables(previous, next);
+      nullifyExpirable(e);
+
+      return next != NullEntry.INSTANCE;
+    }
+
+    @Override
+    @SuppressWarnings("unchecked")
+    public boolean contains(Object o) {
+      ReferenceEntry<K, V> e = (ReferenceEntry) o;
+      return e.getNextExpirable() != NullEntry.INSTANCE;
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return head.getNextExpirable() == head;
+    }
+
+    @Override
+    public int size() {
+      int size = 0;
+      for (ReferenceEntry<K, V> e = head.getNextExpirable(); e != head; e = e.getNextExpirable()) {
+        size++;
+      }
+      return size;
+    }
+
+    @Override
+    public void clear() {
+      ReferenceEntry<K, V> e = head.getNextExpirable();
+      while (e != head) {
+        ReferenceEntry<K, V> next = e.getNextExpirable();
+        nullifyExpirable(e);
+        e = next;
+      }
+
+      head.setNextExpirable(head);
+      head.setPreviousExpirable(head);
+    }
+
+    @Override
+    public Iterator<ReferenceEntry<K, V>> iterator() {
+      return new AbstractSequentialIterator<ReferenceEntry<K, V>>(peek()) {
+        @Override
+        protected ReferenceEntry<K, V> computeNext(ReferenceEntry<K, V> previous) {
+          ReferenceEntry<K, V> next = previous.getNextExpirable();
+          return (next == head) ? null : next;
+        }
+      };
+    }
+  }
+
+  static final class CleanupMapTask implements Runnable {
+    final WeakReference<MapMakerInternalMap<?, ?>> mapReference;
+
+    public CleanupMapTask(MapMakerInternalMap<?, ?> map) {
+      this.mapReference = new WeakReference<MapMakerInternalMap<?, ?>>(map);
+    }
+
+    @Override
+    public void run() {
+      MapMakerInternalMap<?, ?> map = mapReference.get();
+      if (map == null) {
+        throw new CancellationException();
+      }
+
+      for (Segment<?, ?> segment : map.segments) {
+        segment.runCleanup();
+      }
+    }
+  }
+
+  // ConcurrentMap methods
+
+  @Override
+  public boolean isEmpty() {
+    /*
+     * Sum per-segment modCounts to avoid mis-reporting when elements are concurrently added and
+     * removed in one segment while checking another, in which case the table was never actually
+     * empty at any point. (The sum ensures accuracy up through at least 1<<31 per-segment
+     * modifications before recheck.)  Method containsValue() uses similar constructions for
+     * stability checks.
+     */
+    long sum = 0L;
+    Segment<K, V>[] segments = this.segments;
+    for (int i = 0; i < segments.length; ++i) {
+      if (segments[i].count != 0) {
+        return false;
+      }
+      sum += segments[i].modCount;
+    }
+
+    if (sum != 0L) { // recheck unless no modifications
+      for (int i = 0; i < segments.length; ++i) {
+        if (segments[i].count != 0) {
+          return false;
+        }
+        sum -= segments[i].modCount;
+      }
+      if (sum != 0L) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  @Override
+  public int size() {
+    Segment<K, V>[] segments = this.segments;
+    long sum = 0;
+    for (int i = 0; i < segments.length; ++i) {
+      sum += segments[i].count;
+    }
+    return Ints.saturatedCast(sum);
+  }
+
+  @Override
+  public V get(@Nullable Object key) {
+    if (key == null) {
+      return null;
+    }
+    int hash = hash(key);
+    return segmentFor(hash).get(key, hash);
+  }
+
+  /**
+   * Returns the internal entry for the specified key. The entry may be computing, expired, or
+   * partially collected. Does not impact recency ordering.
+   */
+  ReferenceEntry<K, V> getEntry(@Nullable Object key) {
+    if (key == null) {
+      return null;
+    }
+    int hash = hash(key);
+    return segmentFor(hash).getEntry(key, hash);
+  }
+
+  /**
+   * Returns the live internal entry for the specified key. Does not impact recency ordering.
+   */
+  ReferenceEntry<K, V> getLiveEntry(@Nullable Object key) {
+    if (key == null) {
+      return null;
+    }
+    int hash = hash(key);
+    return segmentFor(hash).getLiveEntry(key, hash);
+  }
+
+  @Override
+  public boolean containsKey(@Nullable Object key) {
+    if (key == null) {
+      return false;
+    }
+    int hash = hash(key);
+    return segmentFor(hash).containsKey(key, hash);
+  }
+
+  @Override
+  public boolean containsValue(@Nullable Object value) {
+    if (value == null) {
+      return false;
+    }
+
+    // This implementation is patterned after ConcurrentHashMap, but without the locking. The only
+    // way for it to return a false negative would be for the target value to jump around in the map
+    // such that none of the subsequent iterations observed it, despite the fact that at every point
+    // in time it was present somewhere int the map. This becomes increasingly unlikely as
+    // CONTAINS_VALUE_RETRIES increases, though without locking it is theoretically possible.
+    final Segment<K, V>[] segments = this.segments;
+    long last = -1L;
+    for (int i = 0; i < CONTAINS_VALUE_RETRIES; i++) {
+      long sum = 0L;
+      for (Segment<K, V> segment : segments) {
+        // ensure visibility of most recent completed write
+        @SuppressWarnings({"UnusedDeclaration", "unused"})
+        int c = segment.count; // read-volatile
+
+        AtomicReferenceArray<ReferenceEntry<K, V>> table = segment.table;
+        for (int j = 0; j < table.length(); j++) {
+          for (ReferenceEntry<K, V> e = table.get(j); e != null; e = e.getNext()) {
+            V v = segment.getLiveValue(e);
+            if (v != null && valueEquivalence.equivalent(value, v)) {
+              return true;
+            }
+          }
+        }
+        sum += segment.modCount;
+      }
+      if (sum == last) {
+        break;
+      }
+      last = sum;
+    }
+    return false;
+  }
+
+  @Override
+  public V put(K key, V value) {
+    checkNotNull(key);
+    checkNotNull(value);
+    int hash = hash(key);
+    return segmentFor(hash).put(key, hash, value, false);
+  }
+
+  @Override
+  public V putIfAbsent(K key, V value) {
+    checkNotNull(key);
+    checkNotNull(value);
+    int hash = hash(key);
+    return segmentFor(hash).put(key, hash, value, true);
+  }
+
+  @Override
+  public void putAll(Map<? extends K, ? extends V> m) {
+    for (Entry<? extends K, ? extends V> e : m.entrySet()) {
+      put(e.getKey(), e.getValue());
+    }
+  }
+
+  @Override
+  public V remove(@Nullable Object key) {
+    if (key == null) {
+      return null;
+    }
+    int hash = hash(key);
+    return segmentFor(hash).remove(key, hash);
+  }
+
+  @Override
+  public boolean remove(@Nullable Object key, @Nullable Object value) {
+    if (key == null || value == null) {
+      return false;
+    }
+    int hash = hash(key);
+    return segmentFor(hash).remove(key, hash, value);
+  }
+
+  @Override
+  public boolean replace(K key, @Nullable V oldValue, V newValue) {
+    checkNotNull(key);
+    checkNotNull(newValue);
+    if (oldValue == null) {
+      return false;
+    }
+    int hash = hash(key);
+    return segmentFor(hash).replace(key, hash, oldValue, newValue);
+  }
+
+  @Override
+  public V replace(K key, V value) {
+    checkNotNull(key);
+    checkNotNull(value);
+    int hash = hash(key);
+    return segmentFor(hash).replace(key, hash, value);
+  }
+
+  @Override
+  public void clear() {
+    for (Segment<K, V> segment : segments) {
+      segment.clear();
+    }
+  }
+
+  transient Set<K> keySet;
+
+  @Override
+  public Set<K> keySet() {
+    Set<K> ks = keySet;
+    return (ks != null) ? ks : (keySet = new KeySet());
+  }
+
+  transient Collection<V> values;
+
+  @Override
+  public Collection<V> values() {
+    Collection<V> vs = values;
+    return (vs != null) ? vs : (values = new Values());
+  }
+
+  transient Set<Entry<K, V>> entrySet;
+
+  @Override
+  public Set<Entry<K, V>> entrySet() {
+    Set<Entry<K, V>> es = entrySet;
+    return (es != null) ? es : (entrySet = new EntrySet());
+  }
+
+  // Iterator Support
+
+  abstract class HashIterator {
+
+    int nextSegmentIndex;
+    int nextTableIndex;
+    Segment<K, V> currentSegment;
+    AtomicReferenceArray<ReferenceEntry<K, V>> currentTable;
+    ReferenceEntry<K, V> nextEntry;
+    WriteThroughEntry nextExternal;
+    WriteThroughEntry lastReturned;
+
+    HashIterator() {
+      nextSegmentIndex = segments.length - 1;
+      nextTableIndex = -1;
+      advance();
+    }
+
+    final void advance() {
+      nextExternal = null;
+
+      if (nextInChain()) {
+        return;
+      }
+
+      if (nextInTable()) {
+        return;
+      }
+
+      while (nextSegmentIndex >= 0) {
+        currentSegment = segments[nextSegmentIndex--];
+        if (currentSegment.count != 0) {
+          currentTable = currentSegment.table;
+          nextTableIndex = currentTable.length() - 1;
+          if (nextInTable()) {
+            return;
+          }
+        }
+      }
+    }
+
+    /**
+     * Finds the next entry in the current chain. Returns {@code true} if an entry was found.
+     */
+    boolean nextInChain() {
+      if (nextEntry != null) {
+        for (nextEntry = nextEntry.getNext(); nextEntry != null; nextEntry = nextEntry.getNext()) {
+          if (advanceTo(nextEntry)) {
+            return true;
+          }
+        }
+      }
+      return false;
+    }
+
+    /**
+     * Finds the next entry in the current table. Returns {@code true} if an entry was found.
+     */
+    boolean nextInTable() {
+      while (nextTableIndex >= 0) {
+        if ((nextEntry = currentTable.get(nextTableIndex--)) != null) {
+          if (advanceTo(nextEntry) || nextInChain()) {
+            return true;
+          }
+        }
+      }
+      return false;
+    }
+
+    /**
+     * Advances to the given entry. Returns {@code true} if the entry was valid, {@code false} if it
+     * should be skipped.
+     */
+    boolean advanceTo(ReferenceEntry<K, V> entry) {
+      try {
+        K key = entry.getKey();
+        V value = getLiveValue(entry);
+        if (value != null) {
+          nextExternal = new WriteThroughEntry(key, value);
+          return true;
+        } else {
+          // Skip stale entry.
+          return false;
+        }
+      } finally {
+        currentSegment.postReadCleanup();
+      }
+    }
+
+    public boolean hasNext() {
+      return nextExternal != null;
+    }
+
+    WriteThroughEntry nextEntry() {
+      if (nextExternal == null) {
+        throw new NoSuchElementException();
+      }
+      lastReturned = nextExternal;
+      advance();
+      return lastReturned;
+    }
+
+    public void remove() {
+      checkState(lastReturned != null);
+      MapMakerInternalMap.this.remove(lastReturned.getKey());
+      lastReturned = null;
+    }
+  }
+
+  final class KeyIterator extends HashIterator implements Iterator<K> {
+
+    @Override
+    public K next() {
+      return nextEntry().getKey();
+    }
+  }
+
+  final class ValueIterator extends HashIterator implements Iterator<V> {
+
+    @Override
+    public V next() {
+      return nextEntry().getValue();
+    }
+  }
+
+  /**
+   * Custom Entry class used by EntryIterator.next(), that relays setValue changes to the
+   * underlying map.
+   */
+  final class WriteThroughEntry extends AbstractMapEntry<K, V> {
+    final K key; // non-null
+    V value; // non-null
+
+    WriteThroughEntry(K key, V value) {
+      this.key = key;
+      this.value = value;
+    }
+
+    @Override
+    public K getKey() {
+      return key;
+    }
+
+    @Override
+    public V getValue() {
+      return value;
+    }
+
+    @Override
+    public boolean equals(@Nullable Object object) {
+      // Cannot use key and value equivalence
+      if (object instanceof Entry) {
+        Entry<?, ?> that = (Entry<?, ?>) object;
+        return key.equals(that.getKey()) && value.equals(that.getValue());
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      // Cannot use key and value equivalence
+      return key.hashCode() ^ value.hashCode();
+    }
+
+    @Override
+    public V setValue(V newValue) {
+      V oldValue = put(key, newValue);
+      value = newValue; // only if put succeeds
+      return oldValue;
+    }
+  }
+
+  final class EntryIterator extends HashIterator implements Iterator<Entry<K, V>> {
+
+    @Override
+    public Entry<K, V> next() {
+      return nextEntry();
+    }
+  }
+
+  final class KeySet extends AbstractSet<K> {
+
+    @Override
+    public Iterator<K> iterator() {
+      return new KeyIterator();
+    }
+
+    @Override
+    public int size() {
+      return MapMakerInternalMap.this.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return MapMakerInternalMap.this.isEmpty();
+    }
+
+    @Override
+    public boolean contains(Object o) {
+      return MapMakerInternalMap.this.containsKey(o);
+    }
+
+    @Override
+    public boolean remove(Object o) {
+      return MapMakerInternalMap.this.remove(o) != null;
+    }
+
+    @Override
+    public void clear() {
+      MapMakerInternalMap.this.clear();
+    }
+  }
+
+  final class Values extends AbstractCollection<V> {
+
+    @Override
+    public Iterator<V> iterator() {
+      return new ValueIterator();
+    }
+
+    @Override
+    public int size() {
+      return MapMakerInternalMap.this.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return MapMakerInternalMap.this.isEmpty();
+    }
+
+    @Override
+    public boolean contains(Object o) {
+      return MapMakerInternalMap.this.containsValue(o);
+    }
+
+    @Override
+    public void clear() {
+      MapMakerInternalMap.this.clear();
+    }
+  }
+
+  final class EntrySet extends AbstractSet<Entry<K, V>> {
+
+    @Override
+    public Iterator<Entry<K, V>> iterator() {
+      return new EntryIterator();
+    }
+
+    @Override
+    public boolean contains(Object o) {
+      if (!(o instanceof Entry)) {
+        return false;
+      }
+      Entry<?, ?> e = (Entry<?, ?>) o;
+      Object key = e.getKey();
+      if (key == null) {
+        return false;
+      }
+      V v = MapMakerInternalMap.this.get(key);
+
+      return v != null && valueEquivalence.equivalent(e.getValue(), v);
+    }
+
+    @Override
+    public boolean remove(Object o) {
+      if (!(o instanceof Entry)) {
+        return false;
+      }
+      Entry<?, ?> e = (Entry<?, ?>) o;
+      Object key = e.getKey();
+      return key != null && MapMakerInternalMap.this.remove(key, e.getValue());
+    }
+
+    @Override
+    public int size() {
+      return MapMakerInternalMap.this.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return MapMakerInternalMap.this.isEmpty();
+    }
+
+    @Override
+    public void clear() {
+      MapMakerInternalMap.this.clear();
+    }
+  }
+
+  // Serialization Support
+
+  private static final long serialVersionUID = 5;
+
+  Object writeReplace() {
+    return new SerializationProxy<K, V>(keyStrength, valueStrength, keyEquivalence,
+        valueEquivalence, expireAfterWriteNanos, expireAfterAccessNanos, maximumSize,
+        concurrencyLevel, removalListener, this);
+  }
+
+  /**
+   * The actual object that gets serialized. Unfortunately, readResolve() doesn't get called when a
+   * circular dependency is present, so the proxy must be able to behave as the map itself.
+   */
+  abstract static class AbstractSerializationProxy<K, V>
+      extends ForwardingConcurrentMap<K, V> implements Serializable {
+    private static final long serialVersionUID = 3;
+
+    final Strength keyStrength;
+    final Strength valueStrength;
+    final Equivalence<Object> keyEquivalence;
+    final Equivalence<Object> valueEquivalence;
+    final long expireAfterWriteNanos;
+    final long expireAfterAccessNanos;
+    final int maximumSize;
+    final int concurrencyLevel;
+    final RemovalListener<? super K, ? super V> removalListener;
+
+    transient ConcurrentMap<K, V> delegate;
+
+    AbstractSerializationProxy(Strength keyStrength, Strength valueStrength,
+        Equivalence<Object> keyEquivalence, Equivalence<Object> valueEquivalence,
+        long expireAfterWriteNanos, long expireAfterAccessNanos, int maximumSize,
+        int concurrencyLevel, RemovalListener<? super K, ? super V> removalListener,
+        ConcurrentMap<K, V> delegate) {
+      this.keyStrength = keyStrength;
+      this.valueStrength = valueStrength;
+      this.keyEquivalence = keyEquivalence;
+      this.valueEquivalence = valueEquivalence;
+      this.expireAfterWriteNanos = expireAfterWriteNanos;
+      this.expireAfterAccessNanos = expireAfterAccessNanos;
+      this.maximumSize = maximumSize;
+      this.concurrencyLevel = concurrencyLevel;
+      this.removalListener = removalListener;
+      this.delegate = delegate;
+    }
+
+    @Override
+    protected ConcurrentMap<K, V> delegate() {
+      return delegate;
+    }
+
+    void writeMapTo(ObjectOutputStream out) throws IOException {
+      out.writeInt(delegate.size());
+      for (Entry<K, V> entry : delegate.entrySet()) {
+        out.writeObject(entry.getKey());
+        out.writeObject(entry.getValue());
+      }
+      out.writeObject(null); // terminate entries
+    }
+
+    @SuppressWarnings("deprecation") // serialization of deprecated feature
+    MapMaker readMapMaker(ObjectInputStream in) throws IOException {
+      int size = in.readInt();
+      MapMaker mapMaker = new MapMaker()
+          .initialCapacity(size)
+          .setKeyStrength(keyStrength)
+          .setValueStrength(valueStrength)
+          .keyEquivalence(keyEquivalence)
+          .concurrencyLevel(concurrencyLevel);
+      mapMaker.removalListener(removalListener);
+      if (expireAfterWriteNanos > 0) {
+        mapMaker.expireAfterWrite(expireAfterWriteNanos, TimeUnit.NANOSECONDS);
+      }
+      if (expireAfterAccessNanos > 0) {
+        mapMaker.expireAfterAccess(expireAfterAccessNanos, TimeUnit.NANOSECONDS);
+      }
+      if (maximumSize != MapMaker.UNSET_INT) {
+        mapMaker.maximumSize(maximumSize);
+      }
+      return mapMaker;
+    }
+
+    @SuppressWarnings("unchecked")
+    void readEntries(ObjectInputStream in) throws IOException, ClassNotFoundException {
+      while (true) {
+        K key = (K) in.readObject();
+        if (key == null) {
+          break; // terminator
+        }
+        V value = (V) in.readObject();
+        delegate.put(key, value);
+      }
+    }
+  }
+
+  /**
+   * The actual object that gets serialized. Unfortunately, readResolve() doesn't get called when a
+   * circular dependency is present, so the proxy must be able to behave as the map itself.
+   */
+  private static final class SerializationProxy<K, V> extends AbstractSerializationProxy<K, V> {
+    private static final long serialVersionUID = 3;
+
+    SerializationProxy(Strength keyStrength, Strength valueStrength,
+        Equivalence<Object> keyEquivalence, Equivalence<Object> valueEquivalence,
+        long expireAfterWriteNanos, long expireAfterAccessNanos, int maximumSize,
+        int concurrencyLevel, RemovalListener<? super K, ? super V> removalListener,
+        ConcurrentMap<K, V> delegate) {
+      super(keyStrength, valueStrength, keyEquivalence, valueEquivalence, expireAfterWriteNanos,
+          expireAfterAccessNanos, maximumSize, concurrencyLevel, removalListener, delegate);
+    }
+
+    private void writeObject(ObjectOutputStream out) throws IOException {
+      out.defaultWriteObject();
+      writeMapTo(out);
+    }
+
+    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+      in.defaultReadObject();
+      MapMaker mapMaker = readMapMaker(in);
+      delegate = mapMaker.makeMap();
+      readEntries(in);
+    }
+
+    private Object readResolve() {
+      return delegate;
+    }
+  }
+}