LRU 缓存淘汰算法

Least Recently Used(LRU) 是缓存淘汰一种常用的策略，内存满了则优先删除最久没被使用的数据。

LRU 算法的需求

• 接收一个参数 capacity 作为缓存的最大容量
  
• 实现一个函数 put() 添加数据到缓存
  
• 实现一个函数 get() 查询缓存中的数据
  
• 以上函数应该在 \(O(1)\) 的时间内完成
  

满足以上需求的数据结构 —— 哈希表 + 双向链表，通过哈希表快速定位到链表中的节点，然后完成添加、删除等操作。
LRU 算法的实现

节点定义

1. public class Node {
2.     public int key;
3.     public String data;
4.     public Node next;
5.     public Node prev;
6.    
7.     public Node(int key, String data) {
8.         this.key = key;
9.         this.value = value;
10.         this.next = null;
11.         this.prev = null;
12.     }
13. }

复制代码

双向链表

1. public class MyLinkedList {
2.     private Node head;    // 头节点
3.     private Node tail;    // 尾节点
4.     private int size;
5.    
6.     public MyLinkedList() {
7.         this.head = new Node(-1, "head");
8.         this.tail = new Node(-1, "tail");
9.         
10.         head.next = tail;
11.         tail.prev = head;
12.         
13.         this.size = 0;
14.     }
15.    
16.      // 添加新的数据到缓存
17.      public void addLast(Node node) {
18.          node.prev = tail.prev;
19.          node.next = tail;
20.          tail.prev.next = node;
21.          tail.prev = node;
22.          
23.          this.size += 1;
24.      }
25.    
26.     // 删除缓存中的某项数据
27.     public void remove(Node node) {
28.         node.prev.next = node.next;
29.         node.next.prev = node.prev;
30.         
31.         this.size -= 1;
32.     }
33.    
34.     // 缓存空间已满，删除最早未被使用的数据
35.     public Node removeFirst() {
36.         if (head.next == tail) {
37.             return null;
38.         }
39.         
40.         Node first = head.next;
41.         remove(first);
42.         
43.         return first;
44.     }
45.    
46.     public int size() {
47.         return this.size;
48.     }
49. }

复制代码

LRU Cache

目前使用的双向链表支持从尾部插入，即尾部为最新的数据，头部则是最久未被使用的数据。

1. public class LRUCache {
2.     private Map<Integer, Node> map;
3.     private MyLinkedList cache;
4.     private int capacity;
5.    
6.     public LRUCache(int capacity) {
7.         this.map = new HashMap<>();
8.         this.cache = new MyLinkedList();
9.         this.capacity = capacity;
10.     }
11.    
12.     public String get(int key) {
13.         if (!map.containsKey(key)) {
14.             return null;
15.         }
16.         
17.         makeRecently(key);
18.         return map.get(key).data;
19.     }
20.    
21.     /**
22.      * 1. 判断 key 是否已存在于缓存，若已存在则更新对应的data，并设置为最新使用即添加到队尾
23.      * 2. 判断缓存空间是否已满，若已满则删除最久未使用的数据
24.      */
25.     public void put(int key, String data) {
26.         if (map.containsKey(key)) {
27.             deleteKey(key);
28.             addRecently(key, data);
29.             return;
30.         }
31.         
32.         // 缓存空间已满
33.         if (this.capacity == cache.size()) {
34.             removeLeastRecently();
35.         }
36.         
37.         addRecently(key, data);
38.     }
39.    
40.     private void addRecently(int key, String data) {
41.         Node node = new Node(key, data);
42.         cache.addLast(node);
43.         map.put(key, node);
44.     }
45.    
46.     private void makeRecently(int key) {
47.         Node node = map.get(key);
48.         cache.remove(node);
49.         cache.addLast(node);
50.     }
51.    
52.     private void deleteKey(int key) {
53.         Node node = map.get(key);
54.         cache.remove(node);
55.         map.remove(key);
56.     }
57.    
58.     /**
59.      * 删除最久未被使用的数据
60.      */
61.     private void removeLeastRecently() {
62.         Node node = cache.removeFirst();
63.         map.remove(node.key);
64.     }
65. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！