Cache eviction policy in Java — Part 5 of 5 — MRU

3 min readNov 12, 2020

This article handles the last part of Cache eviction policy, I’m already missing 😢, but no problem next week a fresh article about a new subject 👌.

Where could I use this kind of cache?

I found a really good answer inside the StackOverflow[1] and the answer is

Imagine you were looking up the details of buses as they arrived at a bus stop, based on their bus number (or whatever identifier you use).
It’s somewhat reasonable to think that if you’ve just seen a number 36 bus, you’re less likely to see another one imminently than to see one of the other buses that stops there.
Just one example, but the idea is more general: in some cases, having “just seen something” is a good indicator that you’re unlikely to see the same thing again soon.

Based on the answer above it is possible to expand to our system or problem.

Assumptions

As was said before, the list must store at a maximum of 3 elements and the cache starts always with 3 players, Coutinho, Neto, and Messi all FCB’s ⚽️ players.

LRU

From [2]
The Most Recently Used (MRU) cache is like Cache and LRUCache but uses a most-recently-used replacement policy.
The primary difference with Cache is that cache entries are moved to the end of the eviction queue when both get() and set() are called (as opposed to Cache that only moves entries on set().
The primary difference with LRUCache is that cache entries are evicted from the end of the eviction queue first instead of evicting from the beginning.

Making a long story short, remove the last element accessed when a new element is added.

Code

The code below shows the constructor and the classes used to handle the MRU

MRU

The method discard is called by the put method when a new element is inserted and the list is full. Then using the method removeLast() of LinkedList the last element is removed, i.e, the last accessed.

MRU discar

The put method is used to store new elements, such as Messi 👕, Ronaldinho 😄 and so on.

MRU put

The method to get the element based on the key, returns the element but firstly removes it from the list and then adds (more simple than make a reorder).

MRU get

Tests

Scenario

The scenario is: Given a Cache with size 3 When a player is requested, it moves to the top and removed when a new is added, this is the MRU behaviour.

The initial list has Coutinho, Neto, and Messi.

Messi is requested twice and Coutinho once. As Coutinho was the last request, when Ronaldinho is added, Coutinho is evicted and then after Ronaldinho, as Pep Guardiola did 🛑.

MRU test

Below is possible to see how the player in/out in this Cache.