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?