Sorted Keys data structure for LRU and MRU cache eviction policies

Question

I am working on a simple data structure that will implement a cache eviction policy. The two possible scenarios I want to implement are LRU and MRU

I am looking for a map-like data structure where keys are possibly time (or maybe just auto incremented integer) to know which cache block is most recently used or least recently used. And values are the IDs of the blocks.

Is there an existent Data structure that sorts the data by the keys on insert, and retrieves the value of a certain key in O(1) time?

For instance Java's HashMap has the constant time lookup, but I will need to get all keys, sort them and pick the last or the first depending on the algorithm I am implementing. Is SortedMap what I should go for? Do you suggest any other data structures that work well with LRU and MRU implementations?

Thanks

If concurrency is important, a [`ConcurrentSkipListMap`](http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html) could be pretty useful, or a configuration of a [Guava Cache](http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/com/google/common/collect/MapMaker.html) or [MapMaker](http://guava-libraries.googlecode.com/svn/tags/release09/javadoc/com/google/common/collect/MapMaker.html). — Perception, Mar 06 '13 at 07:17

score 3 · Accepted Answer · edited May 23 '17 at 10:32

You are right, SortedMap sorts entries according its keys on inserts. And the most known implementation of SortedMap is TreeMap, which stores entries as balanced binary tree.

From their javadoc:

A {@link Map} that further provides a total ordering on its keys. The map is ordered according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). Several additional operations are provided to take advantage of the ordering.

Even though entries and keys are returned in sorted ascending order from SortedMap, it also has methods firstKey() and lastKey(), which might be helpfull as well.

Particularly for LRU: the most common way in Java is to use LinkedHashMap, which has method removeEldestEntry(Map.Entry). By default it does nothing, but you can easily extend class and implement that method. More information you may find here.

Its very similar approach followed in Ehcache. http://svn.terracotta.org/svn/ehcache/trunk/ehcache/ehcache-core/src/main/java/net/sf/ehcache/store/LruMemoryStore.java — sundar, Mar 06 '13 at 07:31
@Saher Keys, I wrote wrong, now it is updated, thank for noticing — n1ckolas, Mar 06 '13 at 18:42

Sorted Keys data structure for LRU and MRU cache eviction policies

1 Answers1