Cache eviction policy in Java — Part 4 of 5 — LRU

This article handles the 4️⃣th part of Cache eviction policy and in this article will cover the also famous 😏 LRU.

Class diagram for this series

Where could I use this kind of cache?

This kind of cache is used for memory management but also in: Redis, Cache tool, and to the most import make your data fast to delivery.

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

The LRU (Least Recently Used) algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.[1]

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits. [2]

A Least Recently Used (LRU) Cache organizes items in order of use, allowing you to quickly identify which item hasn’t been used for the longest amount of time. [3]

Code

This tutorial will be used LinkedHashMap and passing true to the access order parameter. When the true value is passing, the LinkedHashMap is sorted in order of access and thus make your life easier to remove the LRU element.

The variable cacheSize is used in this context to be the limit of elements in Cache since it should be smaller here and in the real life.

LRU Java

For put and get wasn’t required any kind of special code, since this work is already made for HashMap.

LRU — put get getCache

The core of this solution is inside the HashMap class. When the put called from the code above, the method removeEldestEntry override by the class LeastRecentlyUsed is classed and the oldest element is removed by removeNode do the job.

Extracted from HashMap

Tests

Scenario

The scenario is: Given a Cache with size 3 When a player is requested, the last requested is placed on the top, and remove the oldest element when a new is added the oldest should be removed, this is the LRU behavior.

The initial list has Coutinho, Neto, and Messi.

Messi is requested twice and Coutinho once. When a new player comes in, “The Magic Ronaldinho” ⚽️ 😃, Neto is evicted since doesn’t have hits and so on.

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

LRU test

Next

The last but not the least, I’ll bring the MRU(Most Recently Used).

GitHub

The code is available on my GitHub.

References

[1] — Using Redis as an LRU cache - Redis

[2] — Cache replacement policies

[3 ] — LRU Cache Data Structure | Interview Cake

4 - https://www.programmersought.com/article/35722271759/