首先，什么是LRU算法呢？全称是：Least recently used，也就是最近最旧未被使用的算法。其核心思想就是：最近被访问到的数据，在未来也可能被访问到。
所以按照LRU算法来说，数据是有个优先级的，最近访问到的优先级就最高，例如：顺序访问1 2 3 4 5 6的话，那么在此刻1的优先级就是最低的。
LRU算法一般用于资源有限的情况下淘汰某些数据使用，Redis的淘汰策略中就有使用LRU实现。
原理
原理其实也很简单，就是每次访问一个元素时就将元素优先级提到最高。所以实现的是需要使用有序的数据结构的，数组，链表都能实现。
为什么不使用队列和栈呢？这是因为有些元素可能是已经存在数据结构中了，那就有可能再次访问它，此时就需要将它移动到首位，而队列和栈只能取队首和栈顶的数据无法将中间部位的数据移动。
例如：
编辑
图1
如果使用数组那每次访问已经在数组中的元素时都需要整体移动，效率不高。
所以一般LRU都是使用链表实现的，而使用链表时为了将元素从链表中间调整到链表头，那就需要将当前这个元素的前后元素改变指针，所以为了能取得前一个元素，则链表也需要使用双向链表。
再然后如果单纯使用链表的话，那每次访问一个元素都需要遍历整个链表才能知道元素是否已经缓存下来，那效率是极低的。基于此，实现一个LRU算法的话可以使用散列表+链表的组合来实现。
源码
接着我们就来实现一下吧。逻辑都已经写在源码中了，也加了一些注释，此处就不再赘述了。
public final class LRUDemo<K, V> {
@Setter
@Getter
// 定义一个node用于构造链表结构
private static final class Node<K, V> {
private K key;
private V value;
private Node<K, V> prev;
private Node<K, V> next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
@Override
// 此处只能打印next或者prev，如果两者都打印的话，调用toString就会出现栈溢出。至于为什么各位看官可以自己想一想
public String toString() {
return "Node{" +
"key=" + key +
", value=" + value +
", next=" + next +
'}';
}
}
// 缓存中最大存储的数据
private final int bufferSize;
private final Map<K, Node<K, V>> valueMap;
// 定义head和tail是为了避免链表中是空数据时空指针问题
private final Node<K, V> head;
private final Node<K, V> tail;
public LRUDemo() {
this(10);
}
public LRUDemo(int bufferSize) {
this.bufferSize = bufferSize;
// 防止空指针
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
valueMap = new HashMap<>();
}
public void put(K k, V v) {
// 超过缓存限制的最大数量时，移除链表尾部数据
if (valueMap.size() >= bufferSize) {
Node<K, V> last = tail.prev;
tail.prev = last.prev;
last.prev.next = tail;
valueMap.remove(last.getKey());
}
// 判断是否已经存在
Node<K, V> kvNode = valueMap.get(k);
if (kvNode != null) {
// 此处其实只是将node的next和prev直接链接
directNP(kvNode);
// 修改该node的value
kvNode.setValue(v);
} else {
kvNode = new Node<>(k, v);
valueMap.put(k, kvNode);
}
// 将node移动到首部（head的next节点）
moveFirst(kvNode);
}
public V get(K k) {
Node<K, V> kvNode = valueMap.get(k);
if (kvNode == null) {
return null;
}
// 如果有访问的话，就要将访问到的数据移动到首部
directNP(kvNode);
moveFirst(kvNode);
return kvNode.getValue();
}
// 测试方法
public static void main(String[] args) {
LRUDemo<String, Integer> lruDemo = new LRUDemo<>(3);
lruDemo.put("1", 1);
lruDemo.put("2", 2);
lruDemo.put("3", 3);
lruDemo.put("3", 4);
lruDemo.put("5", 5);
lruDemo.get("2");
System.out.println(lruDemo);
}
// 直连next节点和prev节点实际过程对应图2
private void directNP(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 实际过程对应图3
private void moveFirst(Node<K, V> node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// 这里单纯是为了打印出当前缓存列中的数据
@Override
public String toString() {
return "LRUDemo{" +
"head=" + head +
'}';
}
}
编辑
图2
编辑
图3
当然图3中的这个移动到列表头部的逻辑，node2可以是任意的状态，node2的next和prev可以指向任何节点，只需要调用moveFirst之后就会变成最终的node2在head下一个节点的状态。
核心逻辑就是这两段移动节点的逻辑而已。剩下的就是在put和get时查找节点以及操作节点。
使用场景
那么这种算法的适用场景又是哪些呢？像前文提到的Redis的淘汰策略其实就有使用LRU淘汰。另外像最近访问记录、最新热点投送等涉及到Last-N的这种形式都可以使用LRU来实现。
缺点
缺点其实还是蛮明显的，因为LRU本身是为了做淘汰使用的，只保留Last-N。那么如果出现偶尔访问一次的数据，这时恰好触发淘汰，就有可能把热门数据给淘汰了，导致缓存击穿。针对这种问题的话，我们也是有解法的，例
如：LFU，LRU-K等。就留待下次再说吧。
总结
今天我们稍微针对LRU算法做了一个分析，解析了下其原理，以及手写了一个实现。当然这个实现并不完美，起码没有考虑到线程安全问题，这就留给读者朋友们实践优化下了。
相信知道原理的你们是不会被难倒的。当然，如往常一样，也留了几个坑，就看后续作者小伙伴还有没有时间填了。
今天的分享到这里就结束了。咱们，下期间～
标签：Node,node,next,链表,如何,算法,LRU,prev From： https://www.cnblogs.com/aischen/p/16849554.html