How to implement a most-recently-used cache

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.

Java Collections provide LinkedHashMap out of the box, which is well-suited to building caches. You probably don't have this in Java ME, but you can grab the source code here:

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

If you can't just copy-paste it, looking at it should get you started implementing one for inclusion in your mobile app. The basic idea is just to include a linked list through the map elements. If you keep this updated whenever someone does put or get, you can efficiently track access order and use order.

The docs contain instructions for building an MRU Cache by overriding the removeEldestEntry(Map.Entry) method. All you really have to do is make a class that extends LinkedHashMap and override the method like so:

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

There's also a constructor that lets you specify whether you want the class to store things in order by insertion or by use, so you've got a little flexibility for your eviction policy, too:

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

Pass true for use-order and false for insertion order.