image
原文链接：https://wangwei.one/posts/java-algoDS-LRU-implement-by-linkedlist.html
前面，我们学习了 链表 的实现，今天我们来学习链表的一个经典的应用场景——LRU淘汰算法。
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used），本篇将介绍LRU策略算法。
LRU Cache
这一算法的核心思想是，当缓存数据达到预设的上限后，会优先淘汰掉近期最少使用的缓存对象。
思路
LRU淘汰算法涉及数据的添加与删除，出于性能考虑，采用链表来进行实现，思路如下：
- 维护一个双向链表用于存放缓存数据，越接近链表尾部的数据表示越少被使用到。
- 放入一个数据时，如果数据已存在则将其移动到链表头部，并更新Key所对应的Value值，如果不存在，则：
- 如果缓存容量已达到最大值，则将链表尾部节点删除掉，将新的数据放入链表头部；
- 如果缓存容量未达到最大值，则直接将新的数据放入链表头部；
- 查询一个数据时，遍历整个链表，如果能查询到对应的数据，则将其移动到链表头部；如果查询不到则返回
null；- 由于遍历链表的时间复杂度为
O(n)，我们可以使用散列表HashMap来记录每个Key所对应的Node节点，将时间复杂度降为O(1)。
- 由于遍历链表的时间复杂度为
LRU-Cache
代码
package one.wangwei.algorithms.utils;
import java.util.HashMap;
import java.util.Map;
/**
* LRU Cache
*
* @author https://wangwei.one
* @date 2019/01/29
*/
public class LRUCache<K, V> {
private int capacity;
private Node head;
private Node tail;
private Map<K, Node> nodeMap;
public LRUCache(int capacity) {
this.capacity = capacity;
this.nodeMap = new HashMap<>(capacity);
}
/**
* Get Key
*
* @param key
* @return
*/
public V get(K key) {
Node existNode = nodeMap.get(key);
if (existNode == null) {
return null;
}
remove(existNode);
addFirst(existNode);
return existNode.value;
}
/**
* Add Key-Value
*
* @param key
* @param value
*/
public void put(K key, V value) {
Node existNode = nodeMap.get(key);
if (existNode == null) {
Node newNode = new Node(key, value);
if (nodeMap.size() >= capacity) {
removeLast();
}
addFirst(newNode);
}
else {
// update the value
existNode.value = value;
remove(existNode);
addFirst(existNode);
}
}
/**
* remove node
*
* @param node
*/
private void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
if (prev == null) {
head = next;
} else {
prev.next = next;
}
if (next == null) {
tail = prev;
} else {
next.prev = prev;
}
nodeMap.remove(node.key);
}
/**
* add first node
*
* @param node
*/
private void addFirst(Node node) {
// don't forget set node prev pointer to null !
node.prev = null;
if (head == null) {
head = tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
nodeMap.put(node.key, node);
}
/**
* remove last
*/
private void removeLast() {
if (tail == null) {
return;
}
// remove key from map
nodeMap.remove(tail.key);
// remove node from linked list
Node prev = tail.prev;
if (prev != null) {
prev.next = null;
tail = prev;
} else {
head = tail = null;
}
}
private class Node {
private K key;
private V value;
private Node prev;
private Node next;
private Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
LeetCode上相关的练习题：Leetcode 146. LRU Cache
性能测试：LeetCode上运行时间为88ms，超过了 43.42% 的Java代码。
