LRU算法到底是怎么一回事？
2020-07-07
加入收藏
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
简单描述一下在《操作系统》这本书里面对于LRU算法的解说。
假定系统为某进程分配了3个物理块，进程运行时的页面走向为 7 0 1 2 0 3 0 4，开始时3个物理块均为空，那么LRU 算法是如下工作的：
这就是最基本的LRU的磁盘调度逻辑，该算法运用领域比较广泛比如redis的内存淘汰策略等等，该算法也是面试中面试官常常用来考验面试者代码能力和对LRU算法的正确理解。
以下我主要以为双向链表+HashMap的方式手撕一个时间复杂度为O(1)的LRU算法。
在JAVA中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造方法第三个参数传入true( accessOrder = true;)，表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private int capacity;
LRULinkedHashMap(int capacity) {
//true是表示按照访问时间排序,
super(capacity, 0.75f, true);
//传入指定的缓存最大容量
this.capacity = capacity;
}
/**
* 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
算法设计思路
- 访问某个节点时，将其从原来的位置删除，并重新插入到链表头部。
- 这样就能保证链表尾部存储的就是最近最久未使用的节点，当节点数量大于缓存最大空间时就淘汰链表尾部的节点。
- 为了使删除操作时间复杂度为 O(1)，就不能采用遍历的方式找到某个节点。
- HashMap 存储着 Key 到节点的映射，通过 Key 就能以 O(1) 的时间得到节点，然后再以 O(1) 的时间将其从双向队列中删除。
一.构建双向链表Node节点
/**
* 定义双向链表其中K为Map中的K 降低查找时间复杂度
*/
class Node {
K k;
V v;
Node pre;
Node next;
Node(K k, V v) {
this.k = k;
this.v = v;
}
}
二.定义变量
//定义缓存大小
private int size;
// 存储K和Node节点的映射 Node中会存放KV
private HashMap<K, Node> map;
private Node head;
private Node tail;
三.初始化结构体
XLRUCache(int size) {
this.size = size;
map = new HashMap<>();
}
四.添加元素
/**
* 添加元素
* 1.元素存在，将元素移动到队尾
* 2.不存在，判断链表是否满。
* 如果满，则删除队首（head）元素，新元素放入队尾元素
* 如果不满，放入队尾（tail）元素
*/
public void put(K key, V value) {
Node node = map.get(key);
if (node != null) {
//更新值
node.v = value;
moveNodeToTail(node);
} else {
Node newNode = new Node(key, value);
//链表满，需要删除首节点
if (map.size() == size) {
Node delHead = removeHead();
map.remove(delHead.k);
}
addLast(newNode);
map.put(key, newNode);
}
}
- 移动元素到链表尾部
public void moveNodeToTail(Node node) {
if (tail == node) {
return;
}
// 头节点直接置空
if (head == node) { // 备注一
head = node.next;
head.pre = null;
} else { // 备注一
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 备注三
node.pre = tail;
node.next = null;
tail.next = node;
tail = node;
}
- 看备注一&备注三如下图
- 看备注二&备注三如下图
- 删除头节点
public Node removeHead() {
// 空链表
if (head == null) {
return null;
}
Node res = head;
// 只有一个节点
if (head == tail) {
head = null;
tail = null;
} else {
// 多个节点
head = res.next;
head.pre = null;
res.next = null;
}
return res;
}
map.remove(delHead.k): 删除Map中的Kv映射关系
- 添加新节点
public void addLast(Node newNode) {
// 添加节点为空节点直接返回
if (newNode == null) {
return;
}
// 如果链表为空则直接添加
if (head == null) {
head = newNode;
tail = newNode;
} else {
// 不为空则尾部添加
tail.next = newNode;
newNode.pre = tail;
tail = newNode;
}
}
如果链表为空则将该元素设置成表头元素同时也是表尾元素。
五.获取元素
public V get(K key) {
Node node = map.get(key);
if (node != null) {
moveNodeToTail(node);
return node.v;
}
return null;
}
调度访问后的节点需要移动到链表尾部。
完整代码
import java.util.HashMap;
/**
* @Auther: Xianglei
* @Company:
* @Date: 2020/6/27 14:52
* @Version 1.0
*/
public class XLRUCache<K, V> {
private int size;
// 存储K和Node节点的映射 Node中会存放KV
private HashMap<K, Node> map;
private Node head;
private Node tail;
XLRUCache(int size) {
this.size = size;
map = new HashMap<>();
}
/**
* 添加元素
* 1.元素存在，将元素移动到队尾
* 2.不存在，判断链表是否满。
* 如果满，则删除队首元素，放入队尾元素，删除更新哈希表
* 如果不满，放入队尾元素，更新哈希表
*/
public void put(K key, V value) {
Node node = map.get(key);
if (node != null) {
//更新值
node.v = value;
moveNodeToTail(node);
} else {
Node newNode = new Node(key, value);
//链表满，需要删除首节点
if (map.size() == size) {
Node delHead = removeHead();
map.remove(delHead.k);
}
addLast(newNode);
map.put(key, newNode);
}
}
public V get(K key) {
Node node = map.get(key);
if (node != null) {
moveNodeToTail(node);
return node.v;
}
return null;
}
public void addLast(Node newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.pre = tail;
tail = newNode;
}
}
public void moveNodeToTail(Node node) {
if (tail == node) {
return;
}
if (head == node) {
head = node.next;
head.pre = null;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
node.pre = tail;
node.next = null;
tail.next = node;
tail = node;
}
public Node removeHead() {
if (head == null) {
return null;
}
Node res = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = res.next;
head.pre = null;
res.next = null;
}
return res;
}
/**
* 定义双向链表
*/
class Node {
K k;
V v;
Node pre;
Node next;
Node(K k, V v) {
this.k = k;
this.v = v;
}
}
}
测试
至此，你应该已经掌握 LRU 算i法的思想和实现过程了，这里面最重要的一点是理清楚双向链表和HasMap的映射关系以及节点移动操作。自此，你知道为什么用双向链表了吗？
更多精彩好文尽在： Java编程之道
