明白和实现 LRU 缓存置换算法

引言

在盘算机科学中，缓存是一种用于提高数据访问速度的技术。然而，缓存空间是有限的，当缓存被填满时，就需要一种策略来决定哪些数据应该保留，哪些应该被淘汰。LRU（迩来最少使用）算法是一种广泛使用的缓存淘汰策略，它基于一个简单的假设：如果数据迩来被访问过，那么它在将来也更有可能被访问。
LRU算法简介

LRU算法的核心思想是：在缓存空间不足时，淘汰最长时间未被访问的数据项。这种策略适用于多种场景，包括Web缓存、数据库查询缓存、操纵体系的页面置换等。
LRU算法的工作原理

LRU算法通常需要两种数据结构来实现：
哈希表：提供O(1)时间复杂度的数据访问和插入。
双向链表：维护数据项的使用序次，迩来使用的在头部，最久未使用的在尾部。
数据访问和插入的流程如下：

获取数据（Get）：从缓存中获取数据，如果数据存在（缓存命中），则将该数据移到链表头部；如果数据不存在（缓存未命中），返回 -1。
放入数据（Put）：将数据放入缓存，如果数据已经存在，则更新数据值并将该节点移到链表头部；如果数据不存在，则在链表头部插入新的节点，如果缓存已满，还需要移除链表尾部的节点。
LRU算法的实现

1. class LRUCache {
2.     /**
3.         整体思路：定义双向循环链表和Map，其中Map的key存储key，value存储链表节点.
4.         为什么定义双向循环链表，因为这样定义就不需要定义额外的头尾节点
5.     */
7.     static class Node{
9.         Node prev, next;
10.         int key, val;
12.         public Node(int key, int val){
13.             this.key = key;
14.             this.val = val;
15.         }
16.     }
18.     private Node dummy = new Node(-1,-1);
19.    
20.     Map<Integer, Node> mp = new HashMap<>();
21.     private int capacity;
23.     public LRUCache(int capacity) {
24.         this.capacity = capacity;
25.         dummy.prev = dummy;
26.         dummy.next = dummy;
27.     }
28.    
29.     public int get(int key) {
30.             // 判断是否在缓存
31.         Node node = mp.get(key);
32.         // 不在，直接返回-1
33.         if(node == null) return -1;
34.         // 在，就把当前节点移动到前面
35.         moveToHead(node);
36.         // 返回节点值
37.         return node.val;
38.     }
39.    
40.     public void put(int key, int value) {
41.             // 判断是否在缓存
42.         Node node = mp.get(key);
43.         // 在，就把当前节点移动到前面
44.         if(node != null){
45.                 // 更新node.val
46.             node.val = value;
47.             moveToHead(node);
48.         }else{
49.                 // 不在，就加入
50.             node = new Node(key, value);
51.             mp.put(key, node);
52.             // 将新节点加入到头部
53.             insert(node);
54.             // 如果当前容量大于LRU容量，就移出
55.             if(mp.size() > capacity){
56.                     // 找到尾节点
57.                 node = dummy.prev;
58.                 // 删除尾节点
59.                 del(node);
60.                 // 从缓存移出对应的key
61.                 mp.remove(node.key);
62.             }
63.         }
64.     }
65.        
66.         // 移动当前节点到头节点
67.     public void moveToHead(Node node){
68.         del(node);
69.         insert(node);
70.     }
72.         // 插入头部
73.     public void insert(Node node){
74.         node.prev = dummy;
75.         node.next = dummy.next;
76.         dummy.next.prev = node;
77.         dummy.next = node;
78.     }
80.         // 删除节点
81.     public void del(Node node){
82.         node.prev.next = node.next;
83.         node.next.prev = node.prev;
84.     }
85. }

复制代码

LRU算法的上风与范围

LRU算法的上风在于其简单性和效率。它能够快速地识别并淘汰最久未使用的数据项。然而，LRU也有范围性，它可能不适用于所有类型的访问模式，特别是那些具有周期性或随机性访问模式的场景。另外，在某些环境下，LRU 缓存可能会频仍地移除和加载数据，导致缓存抖动。这种现象在缓存大小接近于工作集大小时尤为显着。
结论

LRU算法是一种高效且广泛使用的缓存淘汰策略，适用于多种需要缓存的场景。通过明白其工作原理和实现方式，我们可以更好地使用缓存来提高体系性能。随着技术的发展，对LRU算法的优化和变种也在不停涌现，为不同的应用场景提供了更多的选择。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。