明白和实现 LRU 缓存置换算法
引言在盘算机科学中，缓存是一种用于提高数据访问速度的技术。然而，缓存空间是有限的，当缓存被填满时，就需要一种策略来决定哪些数据应该保留，哪些应该被淘汰。LRU（迩来最少使用）算法是一种广泛使用的缓存淘汰策略，它基于一个简单的假设：如果数据迩来被访问过，那么它在将来也更有可能被访问。
LRU算法简介
LRU算法的核心思想是：在缓存空间不足时，淘汰最长时间未被访问的数据项。这种策略适用于多种场景，包括Web缓存、数据库查询缓存、操纵体系的页面置换等。
LRU算法的工作原理
LRU算法通常需要两种数据结构来实现：
哈希表：提供O(1)时间复杂度的数据访问和插入。
双向链表：维护数据项的使用序次，迩来使用的在头部，最久未使用的在尾部。
数据访问和插入的流程如下：
获取数据（Get）：从缓存中获取数据，如果数据存在（缓存命中），则将该数据移到链表头部；如果数据不存在（缓存未命中），返回 -1。
放入数据（Put）：将数据放入缓存，如果数据已经存在，则更新数据值并将该节点移到链表头部；如果数据不存在，则在链表头部插入新的节点，如果缓存已满，还需要移除链表尾部的节点。
LRU算法的实现
class LRUCache {
/**
整体思路：定义双向循环链表和Map，其中Map的key存储key，value存储链表节点.
为什么定义双向循环链表，因为这样定义就不需要定义额外的头尾节点
*/
static class Node{
Node prev, next;
int key, val;
public Node(int key, int val){
this.key = key;
this.val = val;
}
}
private Node dummy = new Node(-1,-1);
Map<Integer, Node> mp = new HashMap<>();
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
// 判断是否在缓存
Node node = mp.get(key);
// 不在，直接返回-1
if(node == null) return -1;
// 在，就把当前节点移动到前面
moveToHead(node);
// 返回节点值
return node.val;
}
public void put(int key, int value) {
// 判断是否在缓存
Node node = mp.get(key);
// 在，就把当前节点移动到前面
if(node != null){
// 更新node.val
node.val = value;
moveToHead(node);
}else{
// 不在，就加入
node = new Node(key, value);
mp.put(key, node);
// 将新节点加入到头部
insert(node);
// 如果当前容量大于LRU容量，就移出
if(mp.size() > capacity){
// 找到尾节点
node = dummy.prev;
// 删除尾节点
del(node);
// 从缓存移出对应的key
mp.remove(node.key);
}
}
}
// 移动当前节点到头节点
public void moveToHead(Node node){
del(node);
insert(node);
}
// 插入头部
public void insert(Node node){
node.prev = dummy;
node.next = dummy.next;
dummy.next.prev = node;
dummy.next = node;
}
// 删除节点
public void del(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
LRU算法的上风与范围
LRU算法的上风在于其简单性和效率。它能够快速地识别并淘汰最久未使用的数据项。然而，LRU也有范围性，它可能不适用于所有类型的访问模式，特别是那些具有周期性或随机性访问模式的场景。另外，在某些环境下，LRU 缓存可能会频仍地移除和加载数据，导致缓存抖动。这种现象在缓存大小接近于工作集大小时尤为显着。
结论
LRU算法是一种高效且广泛使用的缓存淘汰策略，适用于多种需要缓存的场景。通过明白其工作原理和实现方式，我们可以更好地使用缓存来提高体系性能。随着技术的发展，对LRU算法的优化和变种也在不停涌现，为不同的应用场景提供了更多的选择。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]