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:
- I tried to minimize the complexity of this implementation, still, it is rather long, containing 5 classes.
- 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;
}
}
}