lru算法介绍
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 extends linkedhashmap {
private int capacity;
lrulinkedhashmap(int capacity) {
//true是表示按照访问时间排序,
super(capacity, 0.75f, true);
//传入指定的缓存最大容量
this.capacity = capacity;
}
/**
* 实现lru的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
*/
@override
protected boolean removeeldestentry(map.entry 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 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;
public class xlrucache {
private int size;
// 存储k和node节点的映射 node中会存放kv
private hashmap 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 算法的思想和实现过程了，这里面最重要的一点是理清楚双向链表和hasmap的映射关系以及节点移动操作。自此，你知道为什么用双向链表了吗？