Hello, I’m Daming
Personal website: www.cmsblogs.cn/
At Least Recently Use. It is based on the historical access records of data to carry out data elimination, the first access to the data is eliminated, the core idea is that if the data has been recently accessed, then the chance of future access will be higher.
To implement LRU, you need to do two things:
- The latest used item is queried
- Mark the most recently used item
There are many kinds of implementation schemes, here xiaobian mainly introduces two kinds:
- LinkedHashMap
- Two-way linked list + HashMap
LinkedHashMap implementation
The reason for using a LinkedHashMap is that it is ordered. By default, the LinkedHashMap is stored in the order in which the elements were added. It can also be adjusted to adjust the internal order according to the order in which the elements were accessed. We use this feature of LinkedHashMap to implement LRU. Let’s start with a simple example:
public static void main(String[] args){
Map<String,String> map = new LinkedHashMap(10.0.75 f.true);
map.put("1"."a");
map.put("2"."b");
map.put("3"."c");
map.put("4"."d");
System.out.println("The original order is:");
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator(); it.hasNext();) { System.out.print(it.next().getKey() +"");
}
System.out.println();
map.get("2");
System.out.println("After accessing 4, the order is:");
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator(); it.hasNext();) { System.out.print(it.next().getKey() +""); }}Copy the codeRunning result:
The original order is 1, 2, 3, 4. The order after accessing 4 is 1, 3, 4, 2Copy the codeFor more on LinkedHashMap, see this article: Graphic Collection 6: LinkedHashMap
There are two ways to implement LRU with LinkedHashMap. One is to inherit LinkedHashMap, and the other is to use combination.
Inheritance LinkedHashMap
It is very easy to implement this inheritance method, because LinkedHashMap already has LRU features. We only need to implement one thing: when the number of elements in the container exceeds our set capacity, we can remove the first element. And since LinkedHashMap itself is not thread safe, we need to make sure that it is thread safe. This is as simple as rewriting the get() and put() methods of LinkedHashMap. Or use the Collections. SynchronizedMap () method can also be. The implementation is as follows:
public class LRUCacheLinkedHashMap<K.V> extends LinkedHashMap<K.V> {
/**
* 定一缓存容量
*/
private int capacity;
LRUCacheLinkedHashMap(int capacity){
// AccessOrder = true
super(capacity,0.75 f.true);
this.capacity = capacity;
}
/** * The key method for implementing LRU is to remove the top element ** if the number of elements in the map exceeds the maximum cache capacity@param eldest
* @return* /
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
@Override
public synchronized V get(Object key) {
return super.get(key);
}
@Override
public synchronized V put(K key, V value) {
return super.put(key, value); }}Copy the codevalidation
public static void main(String[] args){
LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(5);
cache.put("1"."a");
cache.put("2"."b");
cache.put("3"."c");
cache.put("4"."d");
cache.put("5"."e");
System.out.println("The order after inserting five elements.");
printlnCache(cache);
// Insert the sixth element
cache.put("6"."e");
System.out.println("The order after insertion of the sixth element.");
printlnCache(cache);
// Access the third element
cache.get("3");
System.out.println("The order after accessing element 3");
printlnCache(cache);
}
private static void printlnCache(LRUCacheLinkedHashMap cacheMap){
for(Iterator<Map.Entry<String,String>> it = cacheMap.entrySet().iterator(); it.hasNext();) { System.out.print(it.next().getKey() +"");
}
System.out.println();
}
Copy the codeRunning result:
Order after inserting five elements 1 2 3 4 5 Order after inserting the sixth element 2 3 4 5 6 Order after accessing element 3 2 4 5 6 3Copy the codeThe results are exactly what we expected
Combination of LinkedHashMap
Use combination way may be more elegant, but with no implement the Map interface, so they cannot use the Collections. The synchronizedMap () method to ensure thread safety, so I need at each method increase synchronized to ensure thread safety. The implementation is as follows:
public class LRUCache<K.V> {
private int capacity;
private Map<K,V> cacheMap;
public LRUCache(int capacity){
this.capacity = capacity;
cacheMap = new LinkedHashMap<>(capacity,0.75 f.true);
}
public synchronized void put(K k,V v){
cacheMap.put(k,v);
// Remove the first element
if(cacheMap.size() > capacity){
K first = this.keyIterator().next(); cacheMap.remove(first); }}public synchronized V get(K k){
return cacheMap.get(k);
}
public Iterator<K> keyIterator(a){
returncacheMap.keySet().iterator(); }}Copy the codeValidation:
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(5);
lruCache.put("1"."a");
lruCache.put("2"."b");
lruCache.put("3"."c");
lruCache.put("4"."d");
lruCache.put("5"."e");
System.out.println("The order after inserting five elements.");
println(lruCache);
// Insert the sixth element
lruCache.put("6"."e");
System.out.println("The order after insertion of the sixth element.");
println(lruCache);
// Access the third element
lruCache.get("3");
System.out.println("The order after accessing element 3");
println(lruCache);
}
private static void println(LRUCache lruCache){
for(Iterator it = lruCache.keyIterator(); it.hasNext();) { System.out.print(it.next() +"");
}
System.out.println();
}
Copy the codeThe running results are as follows:
Order after inserting five elements 1 2 3 4 5 Order after inserting the sixth element 2 3 4 5 6 Order after accessing element 3 2 4 5 6 3Copy the codeThe way of combination also seems very simple, there are two points to note:
- Make every method thread-safe
- When putting, check whether the current capacity exceeds the set capacity. If yes, delete the first element. Of course, xiaobian this is not very elegant implementation, so do knowledge in order to be able to better elaborate the implementation of LRU. A better solution is to rewrite it when you construct a LinkedHashMap
removeEldestEntry()That is as follows:
cacheMap = new LinkedHashMap<K,V>(capacity,0.75 f.true) {@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
returnsize()>capacity; }};Copy the codeLinked list + HashMap implementation
Let’s think about how to implement an LRU without taking advantage of existing data structures such as LinkedHashMap. The caching part is easy to implement, and we all know that HashMap will do, but how about the ability to discard the least used data when the cache runs out of capacity?
- Use time stamps. Every element that we access, we add, we update it with a timestamp, and when we put, we just check and remove the one with the smallest timestamp. This method can be implemented, but the cost is high, that is, we need to traverse the entire data to get the minimum timestamp.
- We can the perspective-taking, we don’t need to pay attention to the increase of each node or traversed, we just need to know the node is the first access is ok, so we can use the list record access records, there is a new data to join on the head node of the linked list, every visit will be the data on the head node, The tail of the list must be the first node to be accessed, so every time there is a shortage of capacity, delete the tail node data and set its precursor to tail. Note that this list is a two-way list. The code is as follows:
public class LinkedLRUCache<K.V> {
private int capacity;
private Map<K,LRUNode> map;
private LRUNode head;
private LRUNode tail;
LinkedLRUCache(int capacity){
this.capacity = capacity;
this.map = new HashMap<>();
}
public synchronized void put(K k,V v){
LRUNode node = map.get(k);
// If the key exists, set the node to head
if(node ! =null){
node.value = v;
remove(node,false);
}else{
/** * This node does not exist * 1, add this node to the cache * 2, set this node to head * 3, determine whether the capacity exceeds the capacity */
node = new LRUNode(k,v);
if(map.size() >= capacity){
// Delete the tail node
remove(tail,true);
}
map.put(k,node);
setHead(node);
}
// Set the current node as the first node
setHead(node);
}
public Object get(String key) {
LRUNode node = map.get(key);
if(node ! =null) {
// Put the element you just operated into the head
remove(node, false);
setHead(node);
return node.value;
}
return null;
}
/** * set header node **@param node
*/
private void setHead(LRUNode node) {
if(head ! =null){
node.next = head;
head.prev = node;
}
head = node;
if(tail == null){ tail = node; }}/** * Remove Node ** from the list@param node
* @paramIf flag is true, the key */ of the node is deleted
private void remove(LRUNode node,boolean flag) {
if(node.prev ! =null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if(node.next ! =null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
node.next = null;
node.prev = null;
if(flag) { map.remove(node.key); }}private Iterator iterator(a){
return map.keySet().iterator();
}
private class LRUNode<K.V> {
/** * Cache key */
private K key;
/** * Cache value */
private V value;
private LRUNode next;
private LRUNode prev;
LRUNode(K key, V value) {
this.key = key;
this.value = value; }}}Copy the codevalidation
public static void main(String[] args){
LRUCache lruCache = new LRUCache(5);
lruCache.put("1"."a");
lruCache.put("2"."b");
lruCache.put("3"."c");
lruCache.put("4"."d");
lruCache.put("5"."e");
System.out.println("Insert 5 elements");
println(lruCache);
System.out.println("Insert 3 elements");
lruCache.put("3"."c");
println(lruCache);
System.out.println("Insert the sixth element");
lruCache.put("6"."f");
println(lruCache);
System.out.println("Access 4 elements");
lruCache.get("4");
println(lruCache);
}
private static void println(LRUCache lruCache){
Iterator iterator = lruCache.keyIterator();
while (iterator.hasNext()){
System.out.print(iterator.next() + "");
}
System.out.println();
}
Copy the codeExecution result:
Insert 5 elements 1 2 3 4 5 Insert 3 element 1 2 4 5 3 Insert 6 element 2 4 5 3 6 Access 4 element 2 5 3 6 4Copy the code