This is the first day of my participation in Gwen Challenge

LRU principle

LRU:(least recently used) algorithm, which is designed to exclude least recently used data when memory is running out, cache eviction policies, iction policies. The LRU algorithm assumes that the data that has been used least recently is not likely to be used in the future. When the memory is limited, the information that is not commonly used can be eliminated. For example, when there is a popular product, everyone is searching for this information, and the information just searched is more likely to be searched next, which is more likely than some products that are not commonly Used. Therefore, the data that has not been Used for a long time needs to be kicked out, that is, the Least Recently Used information is kicked out. The idea is to keep hot data (the most recently used data). Using LRU we can solve a lot of real development problems, and it fits well with the business scenario. The algorithm weeds out data according to the historical access record of the data. Its main measurement index is the time of use, and the additional index is the frequency of use.

Algorithm analysis and implementation:

Use HashMap + Key Linked List. The Cache object needs to specify the size of the Cache, set the size of the Cache during initialization, and then instantiate the head and tail of the bidirectional list. The list is two-way. We define the head and tail nodes, and then use the first in, first out (FIFO). HahsMap is used to quickly locate nodes where the most recently added data is stored, and the used nodes are placed at the head so that the least recently used nodes naturally fall to the end of the queue.

Public class LRUCache {// static class Node {int key; int val; Node next; Node prev; public Node(int key, int val) { this.key = key; this.val = val; }} Map<Integer, Node> Map = new HashMap<>(); // private Node head; // private Node tail; Private int cap; public LRUCache(int capacity) { cap = capacity; } public int get(int key) { Node node = map.get(key); If (Node == null) {return -1; if(Node == null) {return -1; } else {// If there is one, move Node to the header int res = node.val; remove(node); appendHead(node); return res; } } public void put(int key, int value) { Node node = map.get(key); If (Node! = null) { node.val = value; remove(node); appendHead(node); } else {// If Node is not in the table, Node = new Node(key, value); if(map.size() < cap) { appendHead(node); map.put(key, node); } else {// remove old map.remove(tail.key); remove(tail); appendHead(node); map.put(key, node); } } } private void appendHead(Node node) { if(head == null) { head = tail = node; } else { node.next = head; head.prev = node; head = node; } } private void remove(Node node) { if(head == tail) { head = tail = null; } else { if(head == node) { head = head.next; node.next = null; } else if (tail == node) { tail = tail.prev; tail.next = null; node.prev = null; } else { node.prev.next = node.next; node.next.prev = node.prev; node.prev = null; node.next = null; }}}}Copy the code