LRU(Least Recently Used) algorithm. A flushing strategy commonly used for caching. Linux memory management and Redis memory elimination strategies both use the LRU algorithm.

When memory is full and new content needs to be loaded into memory, some content must be eliminated. It is key to keep the data that will be used frequently in the future by weeding out the data that is likely to be used least in memory. The main idea of LRU algorithm is to assume that data that has not been used for a long time has little probability of being used in the future. The main data structure of LRU is the hash linked list.

Algorithm thought

LRU algorithm can be implemented with the help of LinkedHashMap in Java. LinkedHashMap is mainly based on HashMap, adding before and after Pointers, head Pointers and tail Pointers to node information. The structure is shown below.

The LRU additions are as follows:

  • Add a cache capacity called cacheSize.
  • When using the GET method, you need to flush the node being visited at the end of the queue (The last node of the queue is the latest node).
  • If the value of cacheSize exceeds the value of put, delete the head node. The new node is then placed at the end of the queue

Put method

  • The value of cacheSize does not exceed the threshold

    The capacity does not exceed cacheSize

  • When cacheSize is exceeded.


The get method

The node location needs to be refreshed

Code implementation

Code to implement this, using LinkedHashMap implementation is the simplest, just need to rewrite the removeEldestEntry method. If you want to take this a step further, you can see how to implement it using HashMap.

LinkedHashMap implementation

Using HashMap

reference

This article refers to the wechat public number programmer Xiao Grey’s article — what is LRU algorithm

And gold digger users – hands-on implementation of an LRU cache