How to implement a most-recently-used cache

Asked 2009-02-24T22:13:25.263

What would be the best way to implement a most-recently-used cache of objects?

Here are the requirements and restrictions...

Objects are stored as key/value Object/Object pairs, so the interface would be a bit like Hashtable get/put
A call to 'get' would mark that object as the most recently used.
At any time, the least recently used object can be purged from the cache.
Lookups and purges must be fast (As in Hashtable fast)
The number of Objects may be large, so list lookups are not good enough.
The implementation must be made using JavaME, so there is little scope for using third-party code or neat library classes from the standard Java libraries. For this reason I'm looking more for algorithmic answers rather than recommendations of off-the-peg solutions.

Edit Report

2 Answers

Why implement something already implemented? Use Ehcache.

However, if third-party libraries are totally out of the question, I guess you are looking to implement a data structure which looks something like this:

Basically is a HashMap (extends HashMap<Object, Object> if you will)
Each value in the Map points to an object in a sorted list, based on which is most used.
Objects recently used are added to the head of the list - O(1)
Purging least-recently used means truncating the end of the list - O(1)
Still gives you Map lookups, but still keeps recently-used items first...

answered 2009-02-24T22:19:05.890

Another approach may be to take a look at section 5.6 in Java Concurrency in Practice by Brian Goetz: "Building an efficient, scalable result cache". Take a look at the Memoizer, although you may have to customize it for your purposes.

As an aside, what I cannot figure out is why Java does not have a ConcurrentLinkedHashMap out of the box. This data structure would be very helpful for building a cache.

answered 2009-02-24T22:58:22.830

How to implement a most-recently-used cache

2 Answers

Your Answer