Is there a SoftHashMap in Java?

Question

I know there is a WeakHashMap in java.util, but since it uses WeakReferences for everything, which is only referenced by this Map, referenced objects will get lost on the next GC cycle. So it's nearly useless if you want to cache random data, which is very likely to be requested again without being Hard-linked the rest of the time. The best solution would be a map, which uses SoftReferences instead, but I didn't find one in the Java RT Package.

Moskow

Answer 1

Edit (Aug. 2012):

It turns out that currently the best solution are probably Guava 13.0's Cache classes, explained on Guava's Wiki - that's what I'm going to use. It even supports building a SoftHashMap (see CacheBuilder.newBuilder().softKeys()), but it is probably not what you want, as Java expert Jeremy Manson explains (below you'll find the link).

---

Not that I know of (Nov. 2008), but you kind find some implementation of SoftHashMap on the net.

Like this one: SoftHashMap or this one.

---

Edit (Nov. 2009)
As Matthias mentions in the comments, the Google Guava MapMaker does use SoftReferences:

A ConcurrentMap builder, providing any combination of these features:

• soft or weak keys,

• soft or weak values,
• timed expiration, and
• on-demand computation of values.

As mentioned in this thread, another JSR166y candidate:

jsr166y.ConcurrentReferenceHashMap

It provides an alternative concurrent reference map to the Google implementation (which relies on a background thread to evict entries)

---

Edit (August 2012)

The Google implementation uses a background thread only when timed expiration of entries is requested. In particular, it simply uses java.util.Timer, which is not so intrusive as having a separate background thread.

Jeremy Manson recommends, for any cache, using this feature to avoid the dangers of SoftReference: http://jeremymanson.blogspot.de/2009/07/how-hotspot-decides-to-clear_07.html

There's another implementation from Apache Commons, namely org.apache.commons.collections.map.ReferenceMap; it does not support timed removal, but it does support choosing whether keys should be compared by identity or by equality. Moreover, this implementation is not concurrent - it can be made synchronized, but that works less well under accesses from multiple threads.

Fuzz

Another useful implementation is OpenJDK's own sun.security.util.Cache, which supports a max size, time-limited lifetime, and a choice of normal references versus SoftReferences. The version in Java 7 maps Objects to Objects; the version in Java 8 is generic. Obviously we shouldn't be importing sun. stuff directly, but the code is GPL'd and can be copied out if you want a starting point. – Kendre

Answer 2

I am familiar with two libraries that offer a SoftHashMap implementation:

1. Apache Commons: org.apache.commons.collections.map.ReferenceMap

2. Google Collections: com.google.common.collect.ReferenceMap

Paleozoic

ReferenceMap has been scrapped from Google Collections. Use MapMaker now. – Bohunk

Answer 3

There is an example implementation in 98 issue of java specialists newsletter

Loriannlorianna

I've been using Dr. Kabutz's issue 98 version of the SoftHashMap in a project for nearly six years and it has worked out well for this particular use. It seems a little long to paste here, but you can find an example in jidesoft.swing.SoftHashMap and org.jvnet.substance.utils.SoftHashMap. There is a tweaked version in org.pushingpixels.substance.internal.utils.SoftHashMap – Afebrile

Answer 4

Have you considered using an LRUMap instead of a soft HashMap? You get more control over what gets stored (or at least, how much).

Raindrop

LRU is the valid old-school approach. But an soft reference cache should do a better job adapting to spikes and valleys in cache and memory usage. Probably that's why the OP was asking for a SoftReference analog of WeakReferenceMap in the first place. – Asymmetric

Answer 5

Apache Shiro comes with a SoftHashMap designed for caching. Its based on the article posted by jb above and licensed under Apache v2. You can find the documentation here and the source code here.

Awed

Answer 6

If you want to implement a cache softreferences are definetly a better idea than weak references, but it puts your entire cache removal policy in the hands of the garbage collector. which is probably not what you want.

If cache removal policy is important your are going to need to do it on your own most likely using regular references. However you are going to have to decide when to eject items and which to eject. If you only want to lose things when you are running out of heap space you can query available heap space via:

Runtime.getRuntime().getFreeMemory();

Then once free memory drops below a certain amount you can start either dropping items. Or you could just implement a max size for the cache and use that to decide when to drop things.

here's an LRU cache i designed with O(1) insertion, deletion and lookup time, that has a configurable max number of elements. If you want a cache this is going to be a better solution imho than a SoftHashMap.

The softreferences are a great way to create a growable cache. So the ideal solution would be to use a SoftHashMap along with a regular fixed size cache. have all inserts into the cache go into both the fixed cache and the soft hash map then to reference something just see if its in the soft hashmap (and update the reference time in the cache). this way all your most important items (according to your chosen policy LRU, MFU,...) will never be removed because they are hard referenced in the cache but you will also hold on to more things (with no policy control) as long as there is sufficient memory.

Sabatier

As Jeremy Manson explains, timed removal (from MapMaker) is a good solution to the problems of SoftReferences: jeremymanson.blogspot.de/2009/07/… Otherwise, Apache Commons maintains an implementation of LRUMap, mentioned below by Joel. – Swatch

Answer 7

You can use for example this implementation thread-safe Soft reference HashMap:

package cz.b2b.jcl.util;

import java.util.*;
import java.lang.ref.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.AbstractMap.SimpleImmutableEntry;

public class ConcurrentSoftHashMap<K, V> extends AbstractMap {

    /**
     The internal HashMap that will hold the SoftReference.
     */
    private final Map<Object, SoftReference> hash = new ConcurrentHashMap<>();
    /**
     The number of "hard" references to hold internally.
     */
    private final int HARD_SIZE;
    /**
     The FIFO list of hard references, order of last access.
     */
    private final ConcurrentLinkedSetQueue hardCache = new ConcurrentLinkedSetQueue();
    /**
     Reference queue for cleared SoftReference objects.
     */
    private final ReferenceQueue queue = new ReferenceQueue();

    public ConcurrentSoftHashMap(int hardSize) {
        HARD_SIZE = hardSize;
    }

    @Override
    public Object get(Object key) {
        Object result = null;
        // We get the SoftReference represented by that key
        SoftReference soft_ref = hash.get(key);
        if (soft_ref != null) {
            // From the SoftReference we get the value, which can be
            // null if it was not in the map, or it was removed in
            // the processQueue() method defined below
            result = soft_ref.get();
            if (result == null) {
                // If the value has been garbage collected, remove the
                // entry from the HashMap.
                hash.remove(key);
            } else {
                // We now add this object to the beginning of the hard
                // reference queue.  
                hardCache.enqueue(result);
                if (hardCache.size() > HARD_SIZE) {
                    // Remove the last entry if list longer than HARD_SIZE
                    hardCache.dequeue();
                }
            }
        }
        return result;
    }

    /**
     Here we put the key, value pair into the HashMap using
     a SoftValue object.
     @param key
     @param value
     @return
     */
    @Override
    public Object put(Object key, Object value) {
        processQueue(); // throw out garbage collected values first
        return hash.put(key, new SoftValue(value, key, queue));
    }

    @Override
    public Object remove(Object key) {
        processQueue(); // throw out garbage collected values first
        return hash.remove(key);
    }

    @Override
    public void clear() {
        hardCache.clear();
        processQueue(); // throw out garbage collected values
        hash.clear();
    }

    @Override
    public int size() {
        processQueue(); // throw out garbage collected values first
        return hash.size();
    }

    @Override
    public boolean containsKey(Object key) {
        processQueue(); // throw out garbage collected values first
        return hash.containsKey(key);
    }

    @Override
    public Set entrySet() {
        Set<Map.Entry> entry = new HashSet<>();
        Map.Entry simpleImmutableEntry = null;
        Object result = null;
        processQueue(); // throw out garbage collected values first
        for (Map.Entry<Object, SoftReference> item : hash.entrySet()) {
            if (item == null) {
                continue;
            }
            Object key = item.getKey();
            SoftReference soft_ref = item.getValue();
            if (soft_ref != null) {
                result = soft_ref.get();
                if (result == null) {
                    hash.remove(key);
                } else {
                    hardCache.enqueue(result);
                    if (hardCache.size() > HARD_SIZE) {
                        hardCache.dequeue();
                    }
                    simpleImmutableEntry = new SimpleImmutableEntry(key, result);
                    entry.add(simpleImmutableEntry);

                }
            }

        }

        return entry;
    }

    private class ConcurrentLinkedSetQueue<E> extends ConcurrentLinkedQueue<E> {

        public void enqueue(E o) {
            if (!contains(o)) {
                add(o);
            }
        }

        public E dequeue() {
            return poll();
        }

    }

    /**
     We define our own subclass of SoftReference which contains
     not only the value but also the key to make it easier to find
     the entry in the HashMap after it's been garbage collected.
     */
    private static class SoftValue extends SoftReference {

        private final Object key; // always make data member final

        /**
         Did you know that an outer class can access private data
         members and methods of an inner class? I didn't know that!
         I thought it was only the inner class who could access the
         outer class's private information. An outer class can also
         access private members of an inner class inside its inner
         class.
         */
        private SoftValue(Object k, Object key, ReferenceQueue q) {
            super(k, q);
            this.key = key;
        }
    }

    /**
     Here we go through the ReferenceQueue and remove garbage
     collected SoftValue objects from the HashMap by looking them
     up using the SoftValue.key data member.
     */
    private void processQueue() {
        SoftValue sv;
        while ((sv = (SoftValue) queue.poll()) != null) {
            hash.remove(sv.key); // we can access private data!
        }
    }

}

Roundhouse