Cache eviction policy in Java — Part 3 of 5 — LFU

This article handles the 🥉rd part of Cache eviction policy and in this article will cover the famous 😏 LFU.

Class diagram for this series

Where could I use this kind of cache?

This kind of cache can be used in: Ads, products, store, market, contract, life itself when an item is no longer or not used for a long time it’s common to throw away or sell.

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.

LFU

The LFU (Least Frequently Used) is a data structure where the element least used is evicted when the max limit of the list is reached[1].

Code

In this tutorial will be used two ConcurrentHashMap objects. One to store the elements and another to store how many times an item has been accessed.

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

LeastFrequentlyUsed

On the code below is possible to see the logic to add a new element. The key is the player id and player object as value.

If the limit wasn’t reached the element is stored on countItemMap and then stored on Cache LFU.

LFU put

If the Cache reached the limit, the removeElement is called and the item least accessed is removed.

The Collections API brings to us a useful method to speed up the search.

LFU removeElement

Once the element is stored and available to be queried, this method retrieves the element and increment the access.

LFU get

For each access/request this method is called and is incremented the time and also the last time, to remove the element in the future.

LFU hitCount

Below is the helper class to control the access to elements and allow us to work with LFU softly.

LFU CounterItem

Tests

Scenario

The scenario is: Given a Cache with size 3 When a player is request increment the counter and when a new player is added remove the least frequently player.

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.

LFU Scenario

Code

LFU Test

Next

In the next article, I’ll bring the LRU (Least Recently Used).

GitHub

The code is available on my GitHub.

References

1 — https://www.ehcache.org/documentation/2.8/apis/cache-eviction-algorithms.html

2 — https://svn.apache.org/repos/asf/activemq/trunk/activemq-kahadb-store/src/main/java/org/apache/activemq/util/LFUCache.java

3 — https://www.programmersought.com/article/2064658867

4 — https://luizcostatech.medium.com/cache-eviction-policy-in-java-part-2-of-5-lifo-2e4f980aae3

5 — Cache eviction policy in Java — Part 1 of 5 — FIFO