“This is my 28th day of participating in the First Challenge 2022. For details: First Challenge 2022.”
Redis LRU algorithm introduction
Title: 1, Redis LRU understand? Is it possible to write an LRU algorithm?
What is LRU?
LRU is the abbreviation of Least Recently Used, which is a commonly Used page replacement algorithm.
Select the most recent and longest unused data for elimination.
Source of algorithm Design
Force link (146 title LRU algorithm introduction) :
Leetcode-cn.com/problems/lr…
As shown in figure:
Design idea
1. The so-called cache must have read and write operations. According to the thought of hit ratio, the time complexity of write and read operations should be O(1).
2. Feature requirements
2.1 There must be a distinction between the ordering of recently used data and data that has not been used for a long time.
2.2 Write and read Operations Are performed at one time.
2.3 If the capacity (pit) is full to delete the least long use who, each new access to the new data in and out of the team head (according to the business of your own set which side is the team head).
Fast to find, fast to insert, fast to delete, and also sort —–> What kind of data structure can satisfy this problem?
Can you do both in O(1) time?
What data structure do you think works best if you can find it once?
The algorithm core of LRU is hash linked list
Essentially HashMap + DoubleLinkedList
Time complexity is a combination of O(1), hash and bidirectional linked lists.
LRU algorithm animation
LRU manual coding implementation
Implementation Case 1
Reference: LinkedHashMap
Relying on the JDK
public class Q149<K, V> extends LinkedHashMap<K, V> { private int capacity; // Cache pit public Q149(int capacity) {// true is the access order // false is the insert order super(capacity, 0.75f, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return super.size() > capacity; } public static void main(String[] args) { Q149 q149 = new Q149(3); q149.put(1, "a"); q149.put(2, "b"); q149.put(3, "c"); System.out.println(q149.keySet()); q149.put(4, "d"); q149.put(5, "e"); System.out.println(q149.keySet()); }}Copy the code
Implementation Case 2
Do not rely on the JDK
Schematic data structure:
Create a Node object containing k, v attributes, and a pointer to the following object. 2. Construct a double-ended linked list DoubleLinkList to realize the cache data linked list structure. AddHead is used to update the first Node, and removeNode is used to remove the Node. And getLastNode to get the tail node. 3. Build an LRU structure by combining Map and DoubleLinkList. The whole is shown in the figure above
public class Q149_1 {
// Map is responsible for finding and building a virtual bidirectional linked list, which is installed in a Node Node, as the carrier of data
// 1 Constructs a Node as the data carrier
class Node<K.V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
public Node(a) {
this.prev = this.next = null;
}
public Node(K key, V value) {
this.key = key;
this.value = value;
this.prev = this.next = null; }}//2 Create a bidirectional queue containing our Node
class DoubleLinkList<K.V> {
Node<K, V> head;
Node<K, V> tail;
// 2.1 constructor
public DoubleLinkList(a) {
this.head = new Node<>();
this.tail = new Node<>();
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 2.2 Add a header
public void addHead(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
//2.3 Deleting a Node
public void removeNode(Node<K, V> node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null;
}
//2.4 Get the last node
public Node<K, V> getLast(a) {
returntail.prev; }}private int cacheSize;
private Map<Integer, Node<Integer, Integer>> map;
private DoubleLinkList<Integer, Integer> doubleLinkList;
public Q149_1(int cacheSize) {
this.cacheSize = cacheSize;
this.map = new HashMap<>();
doubleLinkList = new DoubleLinkList<>();
}
public int get(int key) {
if(! map.containsKey(key)) {return -1;
}
Node<Integer, Integer> node = map.get(key);
doubleLinkList.removeNode(node);
doubleLinkList.addHead(node);
return node.value;
}
// save of update method
public void put(int key, int value) {
// update
if (map.containsKey(key)) {
Node<Integer, Integer> node = map.get(key);
node.value = value;
map.put(key, node);
doubleLinkList.removeNode(node);
doubleLinkList.addHead(node);
} else {
if (map.size() == cacheSize) {
Node<Integer, Integer> lastNode = doubleLinkList.getLast();
map.remove(lastNode.key);
doubleLinkList.removeNode(lastNode);
}
/ / new
Node<Integer, Integer> newNode = newNode<>(key, value); map.put(key, newNode); doubleLinkList.addHead(newNode); }}public static void main(String[] args) {
Q149_1 q149 = new Q149_1(3);
q149.put(1.1);
q149.put(2.2);
q149.put(3.3);
System.out.println(q149.map.keySet());
q149.put(1.2);
q149.put(2.1); System.out.println(q149.map.keySet()); }}Copy the code
The resources
- www.jianshu.com/p/12f025aba…