Minimal Map implementation with weak values

Question

What follows is an implementation of the java.util.Map interface with weak values. This means that entries should be removed from the map when their values become weakly reachable, in the same way that WeakHashMap removes entries whose keys have become weakly reachable.

It is intended to fully implement the contract of the Map interface while being optimized for simplicity rather than performance. It works correctly under a set of simple test cases, some of which try to provoke race conditions by asynchronously invoking the garbage collector while accessing the map.

Besides whatever I may have missed, I mainly feel uneasy about the these two concerns:

1. I tried to minimize the complexity of this implementation, still, it is rather long, containing 5 classes.
2. My usage of WeakReference and whether there are race conditions between e.g. getting or iterating over entries and the garbage collector.

import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
@SuppressWarnings({ "ConstantConditions", "NullableProblems" })
final class WeakValueMap<K, V> extends AbstractMap<K, V> {
 Map<K, ValueReference<K, V>> backingMap = new HashMap<>();
 ReferenceQueue<V> referenceQueue = new ReferenceQueue<>();
 Set<Map.Entry<K, V>> entrySet = new EntrySet();
 @Override
 public V get(Object key) {
 Objects.requireNonNull(key);
 processQueue();
 return resolveReference(backingMap.get(key));
 }
 @Override
 public V put(K key, V value) {
 Objects.requireNonNull(key);
 Objects.requireNonNull(value);
 processQueue();
 return resolveReference(backingMap.put(key, new ValueReference<>(referenceQueue, key, value)));
 }
 @Override
 public V remove(Object key) {
 Objects.requireNonNull(key);
 processQueue();
 return resolveReference(backingMap.remove(key));
 }
 @Override
 public int size() {
 processQueue();
 return backingMap.size();
 }
 @SuppressWarnings("ReturnOfCollectionOrArrayField")
 @Override
 public Set<Map.Entry<K, V>> entrySet() {
 return entrySet;
 }
 private V resolveReference(Reference<V> reference) {
 if (reference == null) {
 return null;
 } else {
 return reference.get();
 }
 }
 private void processQueue() {
 while (true) {
 ValueReference<?, ?> reference = (ValueReference<?, ?>) referenceQueue.poll();
 if (reference == null) {
 break;
 }
 backingMap.remove(reference.key);
 }
 }
 private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
 @Override
 public Iterator<Map.Entry<K, V>> iterator() {
 Set<Map.Entry<K, V>> iterationSet = new HashSet<>();
 processQueue();
 for (Map.Entry<K, ValueReference<K, V>> i : backingMap.entrySet()) {
 K key = i.getKey();
 V value = i.getValue().get();
 if (value != null) {
 iterationSet.add(new Entry(key, value));
 }
 }
 Iterator<Map.Entry<K, V>> setIterator = iterationSet.iterator();
 return new EntryIterator(setIterator);
 }
 @Override
 public boolean remove(Object o) {
 if (o instanceof Map.Entry<?, ?>) {
 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
 return WeakValueMap.this.remove(entry.getKey(), entry.getValue());
 } else {
 return false;
 }
 }
 @Override
 public boolean contains(Object o) {
 if (o instanceof Map.Entry<?, ?>) {
 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
 return entry.getValue().equals(get(entry.getKey()));
 } else {
 return false;
 }
 }
 @Override
 public int size() {
 return WeakValueMap.this.size();
 }
 final class EntryIterator implements Iterator<Map.Entry<K, V>> {
 final Iterator<Map.Entry<K, V>> setIterator;
 Map.Entry<K, V> currentEntry = null;
 EntryIterator(Iterator<Map.Entry<K, V>> setIterator) {
 this.setIterator = setIterator;
 }
 @Override
 public boolean hasNext() {
 return setIterator.hasNext();
 }
 @Override
 public Map.Entry<K, V> next() {
 currentEntry = setIterator.next();
 return currentEntry;
 }
 @Override
 public void remove() {
 setIterator.remove();
 EntrySet.this.remove(currentEntry);
 }
 }
 }
 private final class Entry extends SimpleEntry<K, V> {
 Entry(K key, V value) {
 super(key, value);
 }
 @Override
 public V setValue(V value) {
 put(getKey(), value);
 return super.setValue(value);
 }
 }
 private static final class ValueReference<K, V> extends WeakReference<V> {
 final K key;
 ValueReference(ReferenceQueue<V> referenceQueue, K key, V value) {
 super(value, referenceQueue);
 this.key = key;
 }
 }
}

Answer 1

You seem to ignore this part of the Map javadoc:

All general-purpose map implementation classes should provide two "standard" constructors: ... and a constructor with a single argument of type `Map, which creates a new map with the same key-value mappings as its argument.

But you can claim that it's not a general-purpose map.

---

You inherit equals and hashCode, which is finebut note that it behaves a bit strangely (two equal maps can cease to be equal after the GC runs).

---

Concern Nr. 1: I tried to minimize the complexity of this implementation, still, it is rather long, containing 5 classes.

The Map interface is a monster and always requires a lot of code. While 5 classes is a lot, they're not big and I can't see anything superfluous.

Concern Nr. 2: My usage of WeakReference and whether there are race conditions between e.g. getting or iterating over entries and the garbage collector.

Initially, I thought that you've created a problem by calling processQueue() in non-mutator methods. It would means that simply iterating and calling get may lead to a ConcurrentModificationException thrown by the backingMap.

However, you're using a separate iterationSet, which is decoupled. This means that you never get this exception, which may not be what you want.

With non-mutators processing the queue and without the iterationSet, even a trivial loop like this could throw

for (Map.Entry e1 : map.entrySet) {
 for (Map.Entry e2 : map.entrySet) {
 }
}

Note that your EntrySet.iterator() references the values strongly. This makes it easier to use, but it mayn't be what you want. You could avoid it by reading and storing the (dereferenced) value when calling hasNext() (in order to prevent the value from disappearing between the calls to hasNext and next).

---

public boolean contains(Object o) {
 if (o instanceof Map.Entry<?, ?>) {
 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
 return entry.getValue().equals(get(entry.getKey()));
 } else {
 return false;
 }
}

This will throw whenever o is an entry with a null key or value. I don't think that it's what the Set interface allows.

---

All in all, it's a nice code and I couldn't find any problems, but don't celebrate as such thing are hard to find.

You're aware of com.google.common.cache.CacheBuilder.weakKeys(), right?

• Feuermurmel: Thanks for this very thorough answer! I think the comment about entrySet().contains() throwing a NullPointerException when it shouldn’t, doesn’t the same apply for null keys when calling entrySet().remove()? See the update at the bottom of the question.
• Feuermurmel: About EntryIterator holding strong references to the values: This was a deliberate decision, to keep the implementation simpler. My assumption is that iterators are short-lived and thus these references should not be a problem. IMHO it is acceptable for an iterator to not throw a ConcurrentModificationException when it could, as long as it behaves reasonably (i.e. not throw some other exception or corrupting the collection).
• maaartinus: @Feuermurmel Removing null is documented as "@throws NullPointerException if the specified element is null and this set does not permit null elements", but removing new SimpleEntry(whatever, null) is not covered by this javadoc. +++ "strong references" - when you know about it, it's fine. Add javadoc? +++ The same for ConcurrentModificationException.
• Feuermurmel: I was thinking about .entrySet().remove(new SimpleEntry(null, ...)) which I think throws an NPE in the original implementation, which I think it shouldn't, according to the contract of Set +++ Yes, these things will included in the documentation.