数据缓存历险记（四）–LRU大师兄的Java实现

“这是我参与8月更文挑战的第9天，活动详情查看：8月更文挑战”

“数据缓存历险记第三篇老头的LRU很带劲”
“数据缓存历险记第二篇被过期键经理上了一课“

“数据缓存历险记第一篇被淘汰警察上了一课“

LRU算法

数据今天遇到一个大佬，人家都成为缓存老头的得意门生LRU，数据在此之前早就听过它的大名，因为很多数据在过期之后，会让LRU大师兄去筛选出合适的数据，用来继续提供缓存服务，这里面就涉及了LRU大师兄的秘笈了

就是哈希链表，

根据这三点，数据结构的木匠就给它打造了这个关于 hash –>保持顺序
链表，将数据链接起来，查询和插入；

用Java中的数据结构写出LRU算法

Java中对于链表有存在hash的，我们首先可以想到是hashmap，但是我们这次要使用一个他的子类，

public class LinkedHashMap<K,V>  extends HashMap<K,V> implements Map<K,V>
复制代码

继承了HashMap的特性，查询快+插入快，底层是数组+红黑树

基于对于LinkedHashMap,我们可以看一下关于类的注释：

手写LRU算法步骤

1. 创建初始最大的容量

2. 通过对构造器初始化，创建初始容器

3. 删除操作，（必要的）

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author lucas
 * @create 2021-08-09 19:53
 * @description LRU算法的基础实现
 */
public class LRUCacheDemo<k, v> extends LinkedHashMap<k, v> {

    /**
     * 1.确定初始容量
     * 2.初始化构造器的，容量capacity
     * 3.删除操作
     */
    private int capacity;  //最大容量


    public LRUCacheDemo(int capacity) {
        /**
         *  @param  initialCapacity the initial capacity
         * @param  loadFactor      the load factor
         * @param  accessOrder     the ordering mode - <tt>true</tt> for
         *         access-order, <tt>false</tt> for insertion-order 访问顺序
         */
        super(capacity, 0.75F, false);
        this.capacity = capacity;
    }

    //    默认的构造方法基于，负载因子和顺序
//    public LRUCacheDemo(int initialCapacity, float loadFactor, boolean accessOrder, int capacity) {
//        super(initialCapacity, loadFactor, accessOrder);
//        this.capacity = capacity;
//    }

    //删除操作
    @Override
    protected boolean removeEldestEntry(Map.Entry<k, v> eldest) {
        return super.size() > capacity;
    }


    public static void main(String[] args) {


        LRUCacheDemo lruCacheDemo = new LRUCacheDemo(3);

        lruCacheDemo.put(1, "a");
        lruCacheDemo.put(2, "b");
        lruCacheDemo.put(3, "c");

        System.out.println(lruCacheDemo.keySet());

        lruCacheDemo.put(4, "d");
        System.out.println("增加第四个后，列表是"+lruCacheDemo.keySet());

        /**
         * [1, 2, 3]
         * 增加第四个后，列表是[2, 3, 4]
         * 解析： 当前第四个进来之后，4这个值将最近最少使用的直接踢出去
         */

        System.out.println("--------------------------------------------");
        lruCacheDemo.put(3, "d");
        System.out.println(lruCacheDemo.keySet());
        lruCacheDemo.put(3, "d");
        System.out.println(lruCacheDemo.keySet());
        lruCacheDemo.put(3, "d");
        System.out.println(lruCacheDemo.keySet());

        /***
         * [2, 4, 3]
         * [2, 4, 3]
         * [2, 4, 3]
         * 最近一直使用的，3的值最频繁，放在最右侧
         */
        System.out.println("--------------------------------------------");
        lruCacheDemo.put(5, "d");
        System.out.println(lruCacheDemo.keySet());

        /**
         * [4, 3, 5]
         * 5,进入之后，直接将最少使用的2挤出去
         */

        /**  访问顺序（accessOrder）为ture
         * [1, 2, 3]
         * 增加第四个后，列表是[2, 3, 4]
         * --------------------------------------------
         * [2, 4, 3]
         * [2, 4, 3]
         * [2, 4, 3]
         * --------------------------------------------
         * [4, 3, 5]
         */


```js
复制代码

    /**访问顺序（accessOrder）为false
     * [1, 2, 3]
     * 增加第四个后，列表是[2, 3, 4]
     * --------------------------------------------
     * [2, 3, 4]
     * [2, 3, 4]
     * [2, 3, 4]
     * --------------------------------------------
     * [3, 4, 5]
     */
}
复制代码

}

利用Java的集合，可以实现LRU的功能；

本质上： 如何在有限的容器中，转载多变的数据；

LRU： 最近访问最少的元素挑选出来

其中对于构造器中，需要注意的点，对于accessOrder-代表访问顺序

* 访问顺序accessOreder
* - true for access-order,
* -false for insertion-order
复制代码

卢卡寄语

数据通过对于LRU中 LINKhashMap的实现， 是基于hash+双向链表的集合， 熟悉了LRU基本的工作机制，以及对于多个数据进入固定容器，如何筛选的过程，下期我们会根据数据的表现，提升一个段位，
对于让你纯手写，不借助现成的集合方式，实现一个LRU的算法；
你会如何写呢， 我是卢卡， 答案我们明天揭晓