1 概述
LRU（Least Recently Used）算法是一种缓存淘汰算法，其算法思想是如果数据最近被访问过，那么将来被访问的几率也更高。即当系统的缓存过大，达到删除缓存的阀值时，最先删除最久没有被使用过的数据，被用于操作系统和Redis数据库中。
LRU的底层是由哈希算法+链表组成的。哈希算法具有查找高效的优点，却没法保存添加顺序，因此采用链表记录数据的使用顺序。说白了就是数据被存为两份，哈希和链表各一份。在没有达到缓存上限时候，它两相安无事，当达到缓存上限时，根据链表中保存的使用顺序进行删除。
2 图解数据移动顺序
假设系统缓存的上限为3个节点
2.1 向缓存中添加数据
根据添加的顺序，越后添加的数据在链表中越靠后
2.2 使用数据
因为数据2最近被使用，因此会被移动到链表的末尾
2.3 继续添加数据（未超上限）
添加数据1，因为1存在缓存中，因此只需将1移动到链表的末尾
2.4 继续添加数据（超过上限）
添加数据4，因为4不存在缓存中，因此会触发缓存的淘汰，根据LRU规则，淘汰最久未使用的数据3.
3 代码实现
3.1 源码
/**
* @ClassName LRUCache
* @Description 线程不安全版LRU(哈希＋双向链表)
* @Author laiqj
* @Date 2021-07-25
*/
public class LRUCache<K, v> {
/**
* 链表头节点
*/
private Node first;
/**
* 链表尾节点
*/
private Node last;
/**
* 缓存存储上限
*/
private int limit;
/**
* 存储数据集合
*/
private Map<K, Node> map;
/**
* 构造函数
* @param limit
*/
public LRUCache(int limit) {
this.limit = limit;
this.map = new HashMap<>(limit);
}
/**
* 添加
* @param key
* @param value
* @return
*/
public K put(K key, v value){
//不支持插入空key或者空的value
if(key == null || value == null){
//抛出异常
new NullPointerException("key或value为空！");
}
Node<K, v> node = map.get(key);
//节点不存在
if(node == null){
//实际容量不小于设置的阀值
//删除首节点
if(map.size() >= limit){
node = removeFirst();
map.remove(node.key);
}
} else{//节点存在
node = removeNode(node);
map.remove(node.key);
}
//插入末节点
Node<K, v> newNode = addLast(key, value);
map.put(key, newNode);
return newNode.key;
}
/**
* 查询
* @param key
* @return
*/
public v get(K key){
Node<K, v> node = map.get(key);
if(node == null){
return null;
}
if(first == node) {
removeFirst();
addLast(node.key, node.value);
}else if(last != node){
//从链表中删除当前节点
removeNode(node);
addLast(node.key, node.value);
}
return node.value;
}
/**
* 删除
* @param key
* @return
*/
public v del(K key){
Node<K, v> node = map.remove(key);
if(node == null){
return null;
}
//从链表中删除当前节点
if(first == node) {
removeFirst();
}else if(last != node){
removeNode(node);
}else{
Node<K, v> prevNode = node.prev;
prevNode.next = null;
node.prev = null;
last = prevNode;
}
return node.value;
}
/**
* 插入末尾节点
*/
private Node<K, v> addLast(K key, v value){
//插入末节点
Node<K, v> newNode = new Node(key, value);
if(first == null){
first = newNode;
}else{
last.next = newNode;
newNode.prev = last;
}
last = newNode;
return newNode;
}
/**
* 删除首节点
*/
private Node<K, v> removeFirst() {
Node<K, v> tmpNode = first;
if(tmpNode.next == null){
last = null;
first = null;
}else{
first.next.prev = null;
first = first.next;
tmpNode.next = null;
}
return tmpNode;
}
/**
* 删除尾节点
*/
private Node<K, v> removeLast() {
Node<K, v> tmpNode = last;
if(tmpNode.prev == null){
first = null;
last = null;
}else{
last.prev.next = null;
last = last.prev;
tmpNode.prev = null;
}
return tmpNode;
}
/**
* 从链表中删除节点
* @param node
*/
private Node<K, v> removeNode(Node<K, v> node){
if(node == first){
removeFirst();
}else if(node == last){
removeLast();
}else{
//从链表中删除当前节点
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
}
return node;
}
/**
* 从头到位获取全部键值对数据
* @return
*/
public String displayForward(){
Node<K, v> node = first;
StringBuilder sb = new StringBuilder("[");
while (node != null){
sb.append("{key:" + node.key + ",value:" + node.value + "},");
node = node.next;
}
if(sb.length() == 1){
return "";
}
sb.delete(sb.length() - 1, sb.length());
sb.append("]");
return sb.toString();
}
/**
* 从尾到头获取全部键值对数据
* @return
*/
public String displayBaclward(){
Node<K, v> node = last;
StringBuilder sb = new StringBuilder("[");
while (node != null){
sb.append("{key:" + node.key + ",value:" + node.value + "},");
node = node.prev;
}
if(sb.length() == 1){
return "";
}
sb.delete(sb.length() - 1, sb.length());
sb.append("]");
return sb.toString();
}
/**
* 节点类
* @param <K>
* @param <v>
*/
private class Node<K, v> {
private Node prev;
private Node next;
private K key;
private v value;
Node(K key, v value){
this.key = key;
this.value = value;
}
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(10);
for (int i = 0; i < 5; i++){
lruCache.put(Integer.toString(i), Integer.toString(i));
}
System.out.println("打印全部元素．．．．");
System.out.println(lruCache.displayForward());
System.out.println(lruCache.displayBaclward());
System.out.println("添加(0, 0)．．．．");
lruCache.put("0", "0");
System.out.println(lruCache.displayForward());
System.out.println(lruCache.displayBaclward());
System.out.println("删除key为3的数据．．．．");
lruCache.del("3");
System.out.println(lruCache.displayForward());
System.out.println(lruCache.displayBaclward());
System.out.println("添加(11, 11)．．．．");
lruCache.put("11", "11");
System.out.println(lruCache.displayForward());
System.out.println(lruCache.displayBaclward());
System.out.println("删除key为11的数据．．．．");
lruCache.del("11");
System.out.println(lruCache.displayForward());
System.out.println(lruCache.displayBaclward());
System.out.println("查询key为11的数据．．．．");
lruCache.get("11");
System.out.println(lruCache.displayForward());
System.out.println(lruCache.displayBaclward());
}
}
3.2 测试结果
打印全部元素．．．．
[{key:0,value:0},{key:1,value:1},{key:2,value:2},{key:3,value:3},{key:4,value:4}]
[{key:4,value:4},{key:3,value:3},{key:2,value:2},{key:1,value:1},{key:0,value:0}]
添加(0, 0)．．．．
[{key:1,value:1},{key:2,value:2},{key:3,value:3},{key:4,value:4},{key:0,value:0}]
[{key:0,value:0},{key:4,value:4},{key:3,value:3},{key:2,value:2},{key:1,value:1}]
删除key为3的数据．．．．
[{key:1,value:1},{key:2,value:2},{key:4,value:4},{key:0,value:0}]
[{key:0,value:0},{key:4,value:4},{key:2,value:2},{key:1,value:1}]
添加(11, 11)．．．．
[{key:1,value:1},{key:2,value:2},{key:4,value:4},{key:0,value:0},{key:11,value:11}]
[{key:11,value:11},{key:0,value:0},{key:4,value:4},{key:2,value:2},{key:1,value:1}]
删除key为11的数据．．．．
[{key:1,value:1},{key:2,value:2},{key:4,value:4},{key:0,value:0}]
[{key:0,value:0},{key:4,value:4},{key:2,value:2},{key:1,value:1}]
查询key为11的数据．．．．
[{key:1,value:1},{key:2,value:2},{key:4,value:4},{key:0,value:0}]
[{key:0,value:0},{key:4,value:4},{key:2,value:2},{key:1,value:1}]
4 参考文献
[1]程杰. 大话数据结构[M]. 清华大学出版社,2011
[2] Robert, Lafore., Java数据结构和算法.第2版 版. 2004: 中国电力出版社.[2] Sedgewick Robert与Wayne Kevin, 算法. 2012: 人民邮电出版社.