LRU算法介绍
LRU的全称为Least Recently Used，翻译出来就是最近最少使用的意思，它是一种内存淘汰算法，当内存不够时，将内存中最久没使用的数据清理掉。
LUR算法是内存管理的一种页面置换算法，就是用来删除内存中不被使用的数据，腾出空间来把常用的数据存进去。
为什么需要LRU算法？
现代计算机内存仍是相当昂贵的，那么如果利用好管理好有限的内存，来为用户提供更好的性能，是一个有意义的议题。
LRU(Least Recently Used) 即最近最少使用，属于典型的内存淘汰机制。
通俗的说，LRU算法认为，最近被频繁访问的数据会具备更高的留存，淘汰那些不常被访问的数据，这样可以极大的节省内存的使用。
所以，LRU算法也就常用于缓存的淘汰策略，更好的提升内存的使用率。
LRU算法原理
LRU算法的实现原理：把所有的缓存数据存入链表中，新插入的或被访问的数据存入链表头，如果链表满了，就把尾部的数据清除。
如下图所示：
为了更好地描述和理解LRU算法的原理，此处我们以一个队列举例，队列的头部表示最久没有被访问的数据，队列的尾部表示最近刚访问的数据。
假如定义一个长度为4的队列，我们随意添加几个数据进去，如下图：
此时我们访问一次下标为1的元素，根据LRU算法的思想，需要将下标为1的元素移动到队列的尾部，表示该元素最近访问过，后面的元素依次前移，如下图：
这样，每次队列满了的时候添加新的元素，我们只需要将队列头部的元素移除掉即可，这样就达到了淘汰最近最少使用数据的功能，这就是LRU算法的基本原理。
这样，每次队列满了的时候添加新的元素，我们只需要将队列头部的元素移除掉即可，这样就达到了淘汰最近最少使用数据的功能，这就是LRU算法的基本原理。
LRU算法实现
上面为了方便理解，我们使用的队列来举的例子，虽然可以实现LRU算法，但性能并不高，因为每次更新队列元素之后，都要对队列里面的元素进行大量拷贝（移动），并且访问队列元素时的时间复杂度是O(n)，所以，如果要实现LRU算法，需要再对上面的模型进行优化。
首先，针对元素更新后需要大量拷贝数据的问题，我们可以使用双向链表这种数据结构来解决，因为双向链表中，每个节点都维护有自己的前置节点和后置节点的信息，当我们需要移动一个元素到其他位置时，只需要更新几个节点的前置节点和后置节点信息即可，其他没有涉及的节点数据不需更新，如下图：
然后，针对查询队列元素性能较差的问题，我们可以使用key-value数据结构来解决，因为key-value的查询时间复杂度是O(1)，此处我们使用HashMap来实现。实现原理图如下：
双向链表中维护的是我们实际的数据，HashMap中维护的是双向链表中每个节点的key和node之间的关系，这样，我们在查询数据的时候，可以直接根据HashMap中的key找到对应的双向链表中的节点，然后得到节点中的值；并且在更新链表数据时，也只需要更新涉及节点的指向关系即可。
LRU算法实现
LRU的简易代码实现，如下：
public class LRUCache {
private HashMap<String, LRUNode> map;
private int capacity;
private LRUNode head;
private LRUNode tail;
public void set(String key, Object value) {
LRUNode node = map.get(key);
if (node != null) {
node = map.get(key);
node.value = value;
remove(node, false);
} else {
node = new LRUNode(key, value);
if (map.size() >= capacity) {
// 每次容量不足时先删除最久未使用的元素
remove(tail, true);
}
map.put(key, node);
}
// 将刚添加的元素设置为head
setHead(node);
}
public Object get(String key) {
LRUNode node = map.get(key);
if (node != null) {
// 将刚操作的元素放到head
remove(node, false);
setHead(node);
return node.value;
}
return null;
}
private void setHead(LRUNode node) {
// 先从链表中删除该元素
if (head != null) {
node.next = head;
head.prev = node;
}
head = node;
if (tail == null) {
tail = node;
}
}
// 从链表中删除此Node，此时要注意该Node是head或者是tail的情形
private void remove(LRUNode node, boolean flag) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
node.next = null;
node.prev = null;
if (flag) {
map.remove(node.key);
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<String, LRUNode>();
}
}
关于mikechen
mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。