A brief introduction to the LRU cache algorithm:
LRU (Least recently used) is the least recently used. Add data to the cache, and when the cache is full, remove the least recently accessed data to leave room for newly added data.
1. Basic structure of LRU cache algorithm
- Cache size + hashmap + doubly linked list
- The operation consists of two:
- put(): add data to the cache
- get(): Get the data in the cache
2. Operation description
get() operation:
- First determine whether the key exists in the hash table
- If it does not exist, return -1 directly
- If it exists, locate the node corresponding to the key in the linked list through the hashmap, delete the node, and then insert the same node at the end of the linked list (replace the move operation by deleting + adding, because the moving time complexity is higher), and return the node corresponding to the key value
put() operation:
- First determine whether the key exists in the hash table
- If it exists, locate the node corresponding to the key in the linked list through the hashmap, update the value of the node to the new value of put, delete it, and then insert an identical node at the end
- If it does not exist, insert a new node at the end of the linked list (add the key to the hashmap at the same time), and then judge whether the length of the linked list exceeds the upper limit of the cache capacity. If it exceeds, delete the head node of the linked list (and delete the corresponding key in the hashmap ), if not exceeded, do nothing
3. Native implementation based on HashMap and doubly linked list
import java.util.HashMap;
/**
* LRU cache algorithm implementation: based on HashMap + doubly linked list
* O(1) complexity implements get() and put() operations
*/
public class LRUCache{<!-- -->
private int cap; // cache size
private HashMap<Integer, Node> map; // hashmap
public DoubleList cache; // doubly linked list
class Node {<!-- -->
public int key, val;
public Node prev, next;
public Node(int key, int val){<!-- -->
this.key = key;
this.val = val;
}
}
class DoubleList {<!-- -->
private Node head, tail;
private int size;
/**
* Initialize the doubly linked list
*/
public DoubleList(){<!-- -->
head = new Node(-1, -1);
tail = new Node(-1, -1);
head. next = tail;
tail.prev = head;
size = 0;
}
/**
* Add a node at the end of the linked list
* @param node
*/
public void addLast(Node node){<!-- -->
tail.prev.next = node;
node.prev = tail.prev;
node.next = tail;
tail.prev = node;
map.put(node.key, node); // Put the information of the node into the map
size + + ;
}
/**
* remove node
* @param node
*/
public void remove(Node node){<!-- -->
node.prev.next = node.next;
node.next.prev = node.prev;
map.remove(node.key); // Remove the node information from the map
size--;
}
/**
* Remove the head node of the linked list
* @return
*/
public Node removeFirst(){<!-- -->
if(head.next == tail){<!-- -->
return null;
}
Node first = head. next;
remove(first);
return first;
}
public int size(){<!-- -->
return this. size;
}
}
/**
* Constructor: Initialize cache size, HashMap and DoubleList
* @param cap
*/
public LRUCache(int cap){<!-- -->
this.cap = cap;
map = new HashMap<>();
cache = new DoubleList();
}
/**
* When adding, first judge whether the node exists in the original map:
* If there is, remove it first, and then add the node at the end of the linked list (to ensure that the node has just been visited recently)
* If not, add the node at the end of the linked list, and then judge whether the cache capacity is exceeded:
* If there is, remove the head node (not visited for the longest time)
* If not, do nothing
* @param key
* @param val
*/
public void put(int key, int val){<!-- -->
Node node = new Node(key, val);
if(map. containsKey(key)){<!-- -->
cache. remove(node);
cache.addLast(node);
}else{<!-- -->
cache.addLast(node); // add a new node at the end
if(cache.size > this.cap){<!-- --> // exceeds the cache capacity
cache.removeFirst(); // Remove the node whose head has not been visited for the longest time
}
}
}
/**
* When obtaining, first judge whether the node exists in the original map:
* If not, return -1 directly, indicating that it does not exist
* If there is, delete it first, and then add the node to the end of the linked list (to ensure that it has just been accessed recently)
*/
public Integer get(int key){<!-- -->
if(!map.containsKey(key)){<!-- -->
return -1;
}
Node node = map. get(key);
cache. remove(node);
cache.addLast(node);
return map.get(key).val;
}
public static void main(String[] args) {<!-- -->
LRUCache cache = new LRUCache(3);
cache. put(1, 1);
cache. put(2, 2);
cache. put(3, 3);
cache. put(4, 4);
System.out.println(cache.get(3));
Node p = cache.cache.head;
// Print the node values in the cache in turn
System.out.println("------cache-------");
while (p!= null) {<!-- -->
System.out.println(p.val);
p = p. next;
}
}
}
4. Implementation based on LinkedHashMap
import java.util.LinkedHashMap;
/**
* LRU cache algorithm implementation: based on LinkedHashMap
*/
public class LRUCache1 {<!-- -->
private int cap;
private LinkedHashMap<Integer, Integer> cache;
public LRUCache1(int cap){<!-- -->
this.cap = cap;
cache = new LinkedHashMap<>();
}
public Integer get(int key){<!-- -->
if(!cache. containsKey(key)){<!-- -->
return -1;
}else{<!-- -->
Integer val = cache. get(key);
cache. remove(key);
cache. put(key, val);
return val;
}
}
public void put(int key, int val){<!-- -->
if(cache. containsKey(key)){<!-- -->
cache. remove(key);
cache. put(key, val);
}else{<!-- -->
cache. put(key, val);
if(cache.size() >= cap){<!-- --> // If the cache is exceeded, remove the element (head) that has not been accessed for the longest time
Integer first = cache.keySet().iterator().next();
cache. remove(first);
}
}
}
public static void main(String[] args) {<!-- -->
LRUCache1 cache1 = new LRUCache1(4); // initialize the cache with size 4
cache1. put(1, 1);
cache1. put(2, 2);
cache1. put(3, 3);
System.out.println("Get the cache with key 1:" + cache1.get(1)); // After querying the cache with key 1, the order of elements: 2 3 1
cache1.put(4, 4); // After adding, the order of elements: 2 3 1 4
cache1.put(5, 5); // At this time, the cache capacity is full (after adding new elements at the end, the head element needs to be deleted), after adding, the order of elements: 3 1 4 5
System.out.println(cache1.cache);
}
}
5. Reference documents
- Java implements LRU cache mechanism