写点什么

数据缓存历险记(四)--LRU 大师兄的 Java 实现

用户头像
卢卡多多
关注
发布于: 2 小时前
数据缓存历险记(四)--LRU大师兄的Java实现

LRU 算法

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

就是哈希链表,因为 LRU 大师兄,不仅查询数据 get(),set()数据也特别快,关键是可以很好的排序效果;

根据这三点,数据结构的木匠就给它打造了这个关于 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 的算法;你会如何写呢, 我是卢卡, 答案我们明天揭晓

发布于: 2 小时前阅读数: 3
用户头像

卢卡多多

关注

努力寻找生活答案的旅途者 2020.04.12 加入

公众号:卢卡多多,欢迎一起交流学习

评论

发布
暂无评论
数据缓存历险记(四)--LRU大师兄的Java实现