实现 LRU 算法 两种常用方式

什么是LRU 算法

LRU 算法设计原理 是概率算法基于假设，假设最近最常被访问的数据，那么以后也会被经常访问，不常被访问的数据应该被淘汰。 基于这个假设，我们可以定义一个 数组，当元素被访问那么它的位置就会移动到最前面，当超过了数组的长度，那么删除最后一个元素来保证数组中存在的都是最常用的热点数据。

实现方式

1.利用LinkHashMap 的特性实现 LRU

首先 LinkHashMap 继承至 HashMap 拥有 HashMap 所有的特性，但是HashMap 不是有序的，LinkHashMap 在 HashMap 的基础上包装了一层 双向链表，保证有序性。

使用了 LinkHashMap 实现 LRU 主要利用 LinkHashMap 的几个特性：

1. 数据是有序的。
2. accessOrder 属性可以设置 false(默认) 按插入顺序排序，true：按访问顺序排序，移动被访问元素到最新的位置即最后。
3. 重写 removeEldestEntry 方法，控制超出集合范围后，LinkHashMap 会自动删除最老的数据 即 第一个数据。

package mian.com.test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Map;
/**
 * @className LRULinkedHashMap
 * @Desc LinkHashMap 实现 LRu 算法
 * @Author 张埔枘
 * @Date 2021/9/17 4:07 下午
 * @Version 1.0
 */
public class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
    private final int maxSize;

    public LRULinkedHashMap(int maxSize,Float loadFactor){
        super(maxSize,loadFactor,true);
        this.maxSize = maxSize;
    }


    /**
     * 符合条件的 删除最老的数据，即为 第一个数独，因为是 有序的
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }

    public static void main(String[] args) {
        LRULinkedHashMap<String,String> lruLinkedHashMap = new LRULinkedHashMap(4, 0.75F);
        lruLinkedHashMap.put("1","1");
        lruLinkedHashMap.put("2","2");
        lruLinkedHashMap.put("3","3");
        lruLinkedHashMap.put("4","4");
        lruLinkedHashMap.put("5","5");
        lruLinkedHashMap.get("3");

        System.out.println(lruLinkedHashMap.entrySet());
	//输出结果 ： [2=2, 4=4, 5=5, 3=3]
    }
}

2.双向链表 + HashMap 实现 LRU

思路：

双向链表用于保存数据节点的顺序关系，ConcurrentHashMap 存储数据（支持并发操作且增删改查速度快）。

首先在双向链表上 模拟两个虚拟节点(不会被覆盖和删除)，最新的热点🔥数据在后面，老数据在前面(优先淘汰)，所有的数据节点都添加在 两个虚拟节点的范围之内，实现 LRU 主要 实现 put 和 get 方法，put时需要检查是否存在，存在则更新值并放到末尾并检查是否超过容量，超过则移除第一个节点数据(headNode 的 nextNode)，不存在则添加数据并添加到链表的末尾，get 时判断是否存在，存在则移动到末尾并返回值，不存在则返回不存在。

package mian.com.test;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @className LRUCustomLink
 * @Desc 双向链表 + hashmap 结果实现 lru
 * 大致思路：
 * 1.用 hashmap 来存储数据，然后自行构建一个 双向链表
 * 2.双向链表默认有两个 虚拟节点(不放入hashmap存储)，所有新添加的节点 不能覆盖或在 这两个虚拟节点的范围之外
 * 3.get 操作 首先 在双向链表中 删除当前节点(实际为把当前节点的 上一个节点 和 下一个节点链接起来)，然后把当前节点移动到最后面
 * 4.put 操作，首先判断key 是否存在，存在则覆盖值然后移动到最后，否则添加新的节点 并移动到最后
 *
 * @Author 张埔枘
 * @Date 2021/9/17 5:06 下午
 * @Version 1.0
 */
public class LRUCustomLink {
    private Node headNode;
    private Node tailNode;
    private int maxSize;
    private final Map<Integer,Node> containerMap;

    public LRUCustomLink(int maxSize){
        this.containerMap = new ConcurrentHashMap<Integer,Node>(maxSize);
        //初始化 headNode 和 tailNode-虚拟节点
        this.headNode = new Node(-1,-1);
        this.tailNode = new Node(-1,-1);
        //构建双向链表关系
        this.headNode.nextNode = tailNode;
        this.tailNode.preNode = headNode;
        this.maxSize = maxSize;
    }

    public int get(int key){
        if(!containerMap.containsKey(key)){
            return -1;
        }
        Node node = containerMap.get(key);
        //删除当前节点(实际为在双向链表上把当前节点抹除，然后连接当前节点的前后节点)
        node.preNode.nextNode = node.nextNode;
        node.nextNode.preNode = node.preNode;
        //移动在最后
        moveNode2laste(node);
        return node.value;
    }

    private void moveNode2laste(Node node) {
        //先处理 preNode  后处理 nextNode 防止出错
        node.preNode = tailNode.preNode;
        tailNode.preNode = node;
        node.preNode.nextNode = node;
        node.nextNode = tailNode;
    }


    public void put(int key,int value){
        if(containerMap.containsKey(key)){
            //覆盖值，同时移动值
            containerMap.get(key).value = value;
            get(key);
        }else{
            //创建并移动到最后
            Node node = new Node(key, value);
            containerMap.put(key,node);
            moveNode2laste(node);
            //判断是否超过容量
            if(containerMap.size() > maxSize){
                containerMap.remove(this.headNode.nextNode.key);
                //基于headeNode 处理被删除节点的 前后节点关系
                this.headNode.nextNode = this.headNode.nextNode.nextNode;
                this.headNode.nextNode.preNode = this.headNode;
            }
        }
    }



    class Node{
        private Integer key;
        private Integer value;
        private Node preNode;
        private Node nextNode;

        public Node(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }


    }


    public static void main(String[] args) {
        LRUCustomLink lruCustomLink = new LRUCustomLink(3);
        lruCustomLink.put(1,1);
        lruCustomLink.put(2,2);
        lruCustomLink.put(3,3);
        lruCustomLink.put(4,4);
        lruCustomLink.get(3);
        lruCustomLink.get(4);
        lruCustomLink.get(2);
        Node headNode = lruCustomLink.headNode;
        printNode(headNode);

    }

    private static void printNode(Node headNode) {
        System.out.println(headNode.value);
        Node nextNode = headNode.nextNode;
        if(null != nextNode){
            printNode(nextNode);
        }
    }
}