基于HashMap+双向列表手写实现LRU算法-世界杯乌拉圭-俄罗斯世界杯_u20世界杯法国

前言本文将介绍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 extends LinkedHashMap {

// 缓存坑位

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 eldest) {

return super.size() > capacity;

}

public static void main(String[] args) {

LRUCacheDemoByLinkHashMap 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 key;

V value;

Node prev;

Node next;

public Node() {

this.prev = this.next = null;

}

public Node(K key, V value) {

this.key = key;

this.value = value;

}

// 2。构造一个双向队列

class DoubleLinkedList{

Node head;

Node tail;

// 初始化头尾相连,两个伪节点

public DoubleLinkedList(){

head = new Node<>();

tail = new Node<>();

head.next = tail;

tail.prev= head;

}

//2.1添加到头

public void addHead(Node 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 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> map;

DoubleLinkedList 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 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 node = map.get(key);

node.value = value;

map.put(key,node);

//移动到头部

doubleLinkedList.removeNode(node);

doubleLinkedList.addHead(node);

}else{

if(map.size() == cacheSize){ //坑位满了

Node lastNode = doubleLinkedList.getLast();

map.remove(lastNode.key);

doubleLinkedList.removeNode(lastNode);

}

//新增

Node newNode = new Node(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);