前言
本文将介绍LRU（Least Recently Used，最近最少使用）算法的基本概念，以及如何使用Java的LinkHashMap，并且手写自定义实现来实现LRU算法。可能很多人不清楚这个算法，但是如果知道Redis缓存淘汰策略，那么肯定离不开LRU算法，希望能够通过本文讲解，在实际开发中，能用到LRU进行优化
LRU算法介绍
Least Recently Used，最近最少使用，页面置换算法，选择最近最久未使用的数据予以淘汰。LRU算法是一种常用的缓存替换策略，它的核心思想是在缓存空间不足时，优先淘汰最近最少使用的数据。通过维护一个双向链表和一个哈希表，可以在O(1)时间内完成缓存的访问、修改和淘汰操作。简单来说：
最近最少使用，就是把数据加入一个链表中，按访问时间排序，发生淘汰的时候，把访问时间最旧的淘汰掉。
比如有数据 1，2，1，3，2，依次插入链表中
如果此时缓存中已有（1，2），当 3 加入的时候，得把后面的2淘汰，变成（3，1）
JDK利用LinkHashMap实现LRU
首先向从现有API入手，JDK其实也是封装好了对应的API，也就是LinkedHashMap类，使用时继承该类，设置相关参数就可以直接使用了。
如以下代码，设置LinkedHashMap大小为3，先插入数据，a,b,c，继续插入数据的时候，查看LinkedHashMap的数据情况。
代码语言：java复制public class LRUCacheDemoByLinkHashMap<K,V> extends LinkedHashMap<K,V> {
// 缓存坑位
private int capacity;
/**
*
* @param capacity
*/
public LRUCacheDemoByLinkHashMap(int capacity) {
super(capacity,0.75F,false);
this.capacity = capacity;
}
/***
* 删除最老的节点
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return super.size() > capacity;
}
public static void main(String[] args) {
LRUCacheDemoByLinkHashMap<Object, Object> lruCacheDemo = new LRUCacheDemoByLinkHashMap<>(3);
lruCacheDemo.put(1,"a");
lruCacheDemo.put(2,"b");
lruCacheDemo.put(3,"c");
System.out.println(lruCacheDemo.keySet());
System.out.println("插入新数据：");
lruCacheDemo.put(4,"d");
System.out.println(lruCacheDemo.keySet());
System.out.println("插入已存在数据：");
lruCacheDemo.put(3,"c");
System.out.println(lruCacheDemo.keySet());
lruCacheDemo.put(5,"x");
System.out.println(lruCacheDemo.keySet());
}结果，可以看到，LinkedHashMap数据从左到右，根据插入时间排序，也就是最右的数据为最新的，但是数据满了之后，会把最旧的数据（最近最久）删除
上述代码也可以看到，有个配置，主要设置链表大小，已经Map的扩容负载因子，可以直接设置0.75（map扩容默认就是0.75），这里介绍一下最后一个参数。
代码语言：java复制super(capacity,0.75F,false);最后一个字段accessOrder：
true： 每次插入，如果数据在链表存在，则排到最新（最右）
false：每次插入，如果数据在链表存在，则位置不变
上述代码设置了false，所以插入已存在数据，位置没有变化，接下来试试改成true。
可以看到，当插入已存在数据，比如 3，可以看到会将位置重新排序，排到最右。
以上就是关于JDK封装好的LRU实现方案，调用方很简单，主要是对LinkedHashMap的使用。
自定义手写实现LRU
虽然已经有了封装好的API，但是为了加深理解LUR算法，接下模拟LinkedHashMap数据结构，手写LRU框架。
思想：LRU算法目的实现读写两个操作，命中O(1) 时间复杂度
设计方案：采用哈希链表，hashmap 双向列表，主要是是因为哈希查找快，链表插入和删除快，利用hash来存储查找数据， 双向链表关联每个元素。最新最经常使用的排在最右（读取和插入都会最右）
具体结构如下：
删除节点，该节点后一个节点的前后指向该节点前一个节点，设置该节点指向指针为空
插入节点，新节点前后指向头结点
具体实现代码如下，主要是，使用了一个HashMap来存储键值对，以实现O(1)时间复杂度的查找。同时，使用了一个双向链表来维护元素的访问顺序。当一个元素被访问时，将其移动到双向链表的头部。当需要插入一个新元素时，如果缓存已满，我们会删除双向链表尾部的元素，然后将新元素插入到双向链表头部。
代码语言：java复制public class LRUCacheDemo {
// map负责查找，构建一个虚拟的双向链表，它里面安装的就是一个Node，作为数据载体
//1.构造一个Node节点，作为数据载体
class Node<K,V>{
K key;
V value;
Node<K,V> prev;
Node<K,V> next;
public Node() {
this.prev = this.next = null;
}
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
// 2。构造一个双向队列
class DoubleLinkedList<K,V>{
Node<K,V> head;
Node<K,V> tail;
// 初始化头尾相连,两个伪节点
public DoubleLinkedList(){
head = new Node<>();
tail = new Node<>();
head.next = tail;
tail.prev= head;
}
//2.1添加到头
public void addHead(Node<K,V> node){
// node后指针指向之前 head节点的下一节点（占领）
node.next = head.next;
// node的前指针指向头节点
node.prev = head;
// 之前 head节点的下一节点 的前指针指向node
head.next.prev = node;
// head后指针指向node
head.next = node;
}
// 2。2删除节点
public void removeNode(Node<K,V> node){
node.next.prev = node.prev;
node.prev.next = node.next;
node.prev = null;
node.next = null;
}
//2.3获得最后一个节点
public Node getLast(){
return tail.prev;
}
}
private int cacheSize;
Map<Integer,Node<Integer,Integer>> map;
DoubleLinkedList<Integer,Integer> doubleLinkedList;
public LRUCacheDemo(int cacheSize){
this.cacheSize = cacheSize;
map = new HashMap<>();
doubleLinkedList = new DoubleLinkedList<>();
}
public int get(int key){
if(!map.containsKey(key)){
return -1;
}
Node<Integer,Integer> node = map.get(key);
// 移动到头部
doubleLinkedList.removeNode(node);
doubleLinkedList.addHead(node);
return node.value;
}
public void put(Integer key,Integer value){
if (map.containsKey(key)){
Node<Integer,Integer> node = map.get(key);
node.value = value;
map.put(key,node);
//移动到头部
doubleLinkedList.removeNode(node);
doubleLinkedList.addHead(node);
}else{
if(map.size() == cacheSize){ //坑位满了
Node<Integer,Integer> lastNode = doubleLinkedList.getLast();
map.remove(lastNode.key);
doubleLinkedList.removeNode(lastNode);
}
//新增
Node<Integer,Integer> newNode = new Node<Integer,Integer>(key, value);
map.put(key,newNode);
doubleLinkedList.addHead(newNode);
}
}
public static void main(String[] args) {
LRUCacheDemo lruCacheDemo = new LRUCacheDemo(3);
lruCacheDemo.put(1,1);
lruCacheDemo.put(2,2);
lruCacheDemo.put(3,3);
System.out.println(lruCacheDemo.map.keySet());
lruCacheDemo.put(4,4);
System.out.println(lruCacheDemo.map.keySet());
lruCacheDemo.put(3,3);
System.out.println(lruCacheDemo.map.keySet());
lruCacheDemo.put(3,3);
System.out.println(lruCacheDemo.map.keySet());
lruCacheDemo.put(3,3);
System.out.println(lruCacheDemo.map.keySet());
lruCacheDemo.put(5,5);
System.out.println(lruCacheDemo.map.keySet());
}
}测试结果：
可以看到最终结果跟JDK自带的LinkedHashMap效果一样。
总结
本文主要是介绍了LRU算法，并且通过演示现有JDK的api，以及基于HashMap 双向链表自定义实现LRU。其思想是，通过使用HashMap，我们可以在不牺牲性能的情况下实现快速的键值对查找。同时，通过使用双向链表，可以维护元素的访问顺序，确保最近被访问的元素始终位于链表的头部，从而实现对LRU缓存的高效管理。这种实现方法适用于各种场景，特别是在需要缓存数据并且需要快速访问的场景中，表现尤为出色。
我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！
