Today we will look at how to implement a simple least recently used (LRU) cache.
concept
LRU is the Least Recently Used language.
LRU cache is simply a cache of a certain amount of data, and when a set threshold is exceeded, some outdated data is deleted.
For example, if you have a pile of shoes, you must have the newly bought and favorite ones beside you. If the shoe cabinet is full, if you are not the trench, you will throw the old shoes first.
In the picture, think of the grid as your shoe closet. Only one pair of shoes can fit in one grid.
Insert new data into the linked list header; (The new shoes are on the outside)
Whenever a cache hit (that is, cached data is accessed), the data is moved to the head of the linked list; (The newly worn shoes are on the outside)
When the list is full, discard the data at the end of the list. (When the shoe closet is full, you have to throw out your old shoes.)
The efficiency of LRU is good when there is hot data, but occasional and periodic batch operations will lead to a sharp drop in LRU hit ratio and serious cache contamination.
implementation
LRU cache implementation in Java usually have a variety of options, one is to use LinkedHashMap, one is to design their own data structure, using linked list +HashMap, more flexible can customize the use of the way. Happy for Java students because LinkedHashMap is a natural LRU.
Take a look at the constructor of the LinkedHashMap.
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
Copy the codeNote the accessOrder argument, which uses accessOrder for true and insertion order for false. Sort using access order, which is LRU.
When an element needs to be added, the removeEldestEntry method is called. This is where the LRU element expiration mechanism is implemented. By default, the removeEldestEntry method only returns false to indicate that the element is never expired.
As described above, you can implement the simplest LRU using inheritance. Simply override the removeEldestEntry method.
public static class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { private static final int LRU_MAX_CAPACITY = 1024; public LRULinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } /** * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry) */ @Override protected boolean removeEldestEntry(Entry<K, V> eldest) { if(size() > LRU_MAX_CAPACITY) { return true; } return false; }}Copy the codePay attention to the point
Note the following when using LRU:
Whether cached data actually has hot data
The size of the cache must be limited, otherwise there is a risk of memory bursting
It is a cliche to note that synchronization of LRU operations is a must for high concurrency
How to obtain information →[click me](http://)Docs.qq.com/doc/DVUNiQV…)
You can follow my B station account →→→→B station account
Study communication groups →→→→ →Communication group