Which Java collection should I use to implement a

Question

I'm looking to implement a simple cache without doing too much work (naturally). It seems to me that one of the standard Java collections ought to suffice, with a little extra work. Specifically, I'm storing responses from a server, and the keys can either be the request URL string or a hash code generated from the URL.

I originally thought I'd be able to use a WeakHashMap, but it looks like that method forces me to manage which objects I want to keep around, and any objects I don't manage with strong references are immediately swept away. Should I try out a ConcurrentHashMap of SoftReference values instead? Or will those be cleaned up pretty aggressively too?

I'm now looking at the LinkedHashMap class. With some modifications it looks promising for an MRU cache. Any other suggestions?

Whichever collection I use, should I attempt to manually prune the LRU values, or can I trust the VM to bias against reclaiming recently accessed objects?

FYI, I'm developing on Android so I'd prefer not to import any third-party libraries. I'm dealing with a very small heap (16 to 24 MB) so the VM is probably pretty eager to reclaim resources. I assume the GC will be aggressive.

Answer 1

I like Apache Commons Collections LRUMap

Answer 2

LinkedHashMap is easy to use for cache. This creates an MRU cache of size 10.

private LinkedHashMap<File, ImageIcon> cache = new LinkedHashMap<File, ImageIcon>(10, 0.7f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<File, ImageIcon> eldest) {
        return size() > 10;
    }
};

I guess you can make a class with synchronized delegates to this LinkedHashMap. Forgive me if my understanding of synchronization is wrong.

Answer 3

If you use SoftReference-based keys, the VM will bias (strongly) against recently accessed objects. However it would be quite difficult to determine the caching semantics - the only guarantee that a SoftReference gives you (over a WeakReference) is that it will be cleared before an OutOfMemoryError is thrown. It would be perfectly legal for a JVM implementation to treat them identically to WeakReferences, at which point you might end up with a cache that doesn't cache anything.

I don't know how things work on Android, but with Sun's recent JVMs one can tweak the SoftReference behaviour with the -XX:SoftRefLRUPolicyMSPerMB command-line option, which determines the number of milliseconds that a softly-reachable object will be retained for, per MB of free memory in the heap. As you can see, this is going to be exceptionally difficult to get any predictable lifespan behaviour out of, with the added pain that this setting is global for all soft references in the VM and can't be tweaked separately for individual classes' use of SoftReferences (chances are each use will want different parameters).

---

The simplest way to make an LRU cache is by extending LinkedHashMap as described here. Since you need thread-safety, the simplest way to extend this initially is to just use Collections.synchronizedMap on an instance of this custom class to ensure safe concurrent behaviour.

Beware premature optimisation - unless you need very high throughput, the theoretically suboptimal overhead of the coarse synchronization is not likely to be an issue. And the good news - if profiling shows that you are performing too slowly due to heavy lock contention, you'll have enough information available about the runtime use of your cache that you'll be able to come up with a suitable lockless alternative (probably based on ConcurrentHashMap with some manual LRU treatment) rather than having to guess at its load profile.

Answer 4

www.javolution.org has some interestig features - synchronized fast collections. In your case it worth a try as it offers also some nifty enhancements for small devices as Android ones.

Answer 5

For synchronization, the Collections framework provides a synchronized map:

Map<V,T> myMap = Collections.synchronizedMap(new HashMap<V, T>());

You could then wrap this, or handle the LRU logic in a cache object.