Use LinkedHashMap to implement LRU cache

Question

I was trying to implement a LRU cache using LinkedHashMap. In the documentation of LinkedHashMap (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html), it says:

Note that insertion order is not affected if a key is re-inserted into the map.

But when I do the following puts

public class LRUCache<K, V> extends LinkedHashMap<K, V> {     private int size;      public static void main(String[] args) {         LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);         cache.put(1, 1);         cache.put(2, 2);         cache.put(1, 1);         cache.put(3, 3);          System.out.println(cache);     }      private LRUCache(int size) {         super(size, 0.75f, true);         this.size = size;     }      @Override     protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {         return size() > size;     }      public static <K, V> LRUCache<K, V> newInstance(int size) {         return new LRUCache<K, V>(size);     }  } 

The output is

{1=1, 3=3} 

Which indicates that the re-inserted did affected the order. Does anybody know any explanation?

Answer 1

As pointed out by Jeffrey, you are using accessOrder. When you created the LinkedHashMap, the third parameter specify how the order is changed.

"true for access-order, false for insertion-order" 

For more detailed implementation of LRU, you can look at this http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

Answer 2

But you aren't using insertion order, you're using access order.

order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)

...

Invoking the put or get method results in an access to the corresponding entry

So this is the state of your cache as you modify it:

    LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);     cache.put(1, 1); // { 1=1 }     cache.put(2, 2); // { 1=1, 2=2 }     cache.put(1, 1); // { 2=2, 1=1 }     cache.put(3, 3); // { 1=1, 3=3 }