Use LinkedHashMap to implement LRU cache

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/

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 }