Prob 13.4 LRU cache in Java - no need for moveToFront()/lookup()/insert() since LinkedHashMap already supports access-ordering via constructor

#1

I realized 13.4 LRU java book solution is currently using LinkedHashMap…

LinkedHashMap already supports access-order iteration and eviction via its 3-param constructor.

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

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches. Invoking the put or get method results in an access to the corresponding entry (assuming it exists after the invocation completes).

so lookup() can just call get() and be done.

even re-insertion also places it to the front automatically if access-order is set to true. i just tested it.
so insert() can just call put() and be done.

in fact, if we’re allowed to use LinkedHashMap in the first place, we can just give LinkedHashMap with just removeEldestEntry overriden… it satisfies all the problem requirements in java. otherwise, we should not be allowed to use this class.

0 Likes
#2

Hi @xjis, thanks for sharing!

Yeah, LinkedHashMap well-suited to building a LRU cache, but typically for an interview, I’m afraid it is not allowed to do so. Or we need to reinvent the wheel for the interview. :joy:

0 Likes
#3

i’m not saying you should be allowed to use it; the book solution for this problem is already using it as you can see it here:
https://github.com/epibook/epibook.github.io/blob/master/solutions/java/src/main/java/com/epi/LRUCache.java

and if the solution wishes to use it, then you don’t even need all these extra wrappers (lookup/moveToFront/etc) on top of LinkedHashMap either because LinkedHashMap already provides access-order capabilities w/o you doing so manually.

the book probably thinks LinkedHashMap only supports insertion-order, but it actually supports both insertion-order and access-order.

i’m arguing, because of this, LinkedHashMap should not be allowed nor used in the book solution…

1 Like
#4

Ah, good catch! If you’ve already reinvented it, why not make a pull request? I think it would be great if we can show this powerful feature of Java and provide an alternative reinvented wheel at the same time. :grin:

0 Likes
#5

I wasnt aware of the constructor call that takes the accessOrder boolean argument. you are correct, setting it means we don’t need to use the moveToFront() method.

In the next release we will resolve this, either by requiring an implementation from scratch or just using

this.isbnToPrice = new LinkedHashMap<Integer, Integer>(capacity, 1.00f, true) {
  @Override
  protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
    return this.size() > capacity;
  }
};

which makes the rest of the implementation very simple. Thanks for pointing that out, we really appreciate feedback from our wonderful readers.

bye,
Adnan

0 Likes