起飞,手撸了一个 LRU 缓存,源码原来这么简单!

简介: LRU是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。简单的说就是,对于一组数据,例如:int[] a = {1,2,3,4,5,6},如果1,2这几个数字经常被使用,那么会排在3,4,5,6的后面,数组变成如下:int[] a = {3,4,5,6,1,2},如果一个数字,经常不被使用,就会排在最前面!LRU 算法,一般用于热点数据的查询,比如新闻信息,越是能被用户看得多的新闻,越有可能被别的用户所看到,对于那种基本没人访问的新闻,基本都类似存入大海!在 Java 中,就有这么一个集合类实现了这个功能

LRU 介绍

LRU是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰

简单的说就是,对于一组数据,例如:int[] a = {1,2,3,4,5,6},如果1,2这几个数字经常被使用,那么会排在3,4,5,6的后面,数组变成如下:int[] a = {3,4,5,6,1,2},如果一个数字,经常不被使用,就会排在最前面!

LRU 算法,一般用于热点数据的查询,比如新闻信息,越是能被用户看得多的新闻,越有可能被别的用户所看到,对于那种基本没人访问的新闻,基本都类似存入大海!

在 Java 中,就有这么一个集合类实现了这个功能,它就是LinkedHashMap

LinkedHashMap 介绍

我们都知道,在java集合中,LinkedHashMap 继承自 HashMap,底层是一个双向链表的数据结构,与 HashMap 不同的是,LinkedHashMap 初始化阶段有个参数accessOrder,默认是false

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>{
    /**双向链表的头节点*/
    transient LinkedHashMap.Entry<K,V> head;
    /**双向链表的尾节点*/
    transient LinkedHashMap.Entry<K,V> tail;
    /**
      * 1、如果accessOrder为true的话,则会把访问过的元素放在链表后面,放置顺序是访问的顺序
      * 2、如果accessOrder为false的话,则按插入顺序来遍历
      */
      final boolean accessOrder;
}

如果传入的是true,则会把最近访问过的元素放在链表后面,放置顺序是访问的顺序,测试如下:

public static void main(String[] args) {
        //accessOrder默认为false
        Map<String, String> accessOrderFalse = new LinkedHashMap<>();
        accessOrderFalse.put("1","1");
        accessOrderFalse.put("2","2");
        accessOrderFalse.put("3","3");
        accessOrderFalse.put("4","4");
        System.out.println("acessOrderFalse:"+accessOrderFalse.toString());
        //accessOrder设置为true
        Map<String, String> accessOrderTrue = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderTrue.put("1","1");
        accessOrderTrue.put("2","2");
        accessOrderTrue.put("3","3");
        accessOrderTrue.put("4","4");
        accessOrderTrue.get("2");//获取键2
        accessOrderTrue.get("3");//获取键3
        System.out.println("accessOrderTrue:"+accessOrderTrue.toString());
}

输出结果如下:

acessOrderFalse:{1=1, 2=2, 3=3, 4=4}
accessOrderTrue:{1=1, 4=4, 2=2, 3=3}

可以得知,当我们将accessOrder设置为true的时候,经常被访问的元素会放入前面!

我们利用这个特性,使用 LinkedHashMap 来实现一个 LRU 缓存,操作如下:

  • 创建一个 LinkedHashMap 对象,将accessOrder设置为true
  • 设定 LinkedHashMap 的容量为n,超过这个值就删除多余的元素;
  • 重写 LinkedHashMap 中removeEldestEntry()方法;

其中removeEldestEntry()表示,如果返回的是true,就会移除最近不被使用的元素,如果返回false,不做任何操作,这个方法每次在add()的时候就会调用。

创建一个 LRU 缓存类,内容如下:

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    //创建一个容量为3的LinkedHashMap
    private static final int MAX_SIZE = 3;
    /**
     * 重写LinkedHashMap中removeEldestEntry方法
     * @param eldest
     * @return
     */
    protected boolean removeEldestEntry(Map.Entry eldest) {
        //如果容器中的元素个数大于MAX_SIZE,在每次添加元素的时候,移除容器中最近不被使用的元素
        return size() > MAX_SIZE;
    }
    public LRULinkedHashMap() {
        //设置LinkedHashMap初始化容量,负载因子为0.75f,accessOrder设置为true
        super(MAX_SIZE, 0.75f, true);
    }
}

测试使用:

public static void main(String[] args) {
    LRULinkedHashMap<String,String> cache = new LRULinkedHashMap<String,String>();
    cache.put("1","a");
    cache.put("2","b");
    cache.put("3","c");
    System.out.println("初始cache内容:" + cache.toString());
    cache.get("2");
    System.out.println("查询key为2的元素之后,cache内容:" + cache.toString());
    cache.put("4","d");
    System.out.println("添加新的元素之后,cache内容:" + cache.toString());
}

输出结果如下:

初始cache内容:{1=a, 2=b, 3=c}
查询key为2的元素之后,cache内容:{1=a, 3=c, 2=b}
添加新的元素之后,cache内容:{3=c, 2=b, 4=d}
相关文章
|
2月前
|
缓存 算法 数据挖掘
深入理解缓存更新策略:从LRU到LFU
【10月更文挑战第7天】 在本文中,我们将探讨计算机系统中缓存机制的核心——缓存更新策略。缓存是提高数据检索速度的关键技术之一,无论是在硬件还是软件层面都扮演着重要角色。我们会详细介绍最常用的两种缓存算法:最近最少使用(LRU)和最少使用频率(LFU),并讨论它们的优缺点及适用场景。通过对比分析,旨在帮助读者更好地理解如何选择和实现适合自己需求的缓存策略,从而优化系统性能。
58 3
|
3月前
|
缓存 Java 开发工具
Spring是如何解决循环依赖的?从底层源码入手,详细解读Spring框架的三级缓存
三级缓存是Spring框架里,一个经典的技术点,它很好地解决了循环依赖的问题,也是很多面试中会被问到的问题,本文从源码入手,详细剖析Spring三级缓存的来龙去脉。
216 24
Spring是如何解决循环依赖的?从底层源码入手,详细解读Spring框架的三级缓存
|
2月前
|
缓存 NoSQL Ubuntu
大数据-39 Redis 高并发分布式缓存 Ubuntu源码编译安装 云服务器 启动并测试 redis-server redis-cli
大数据-39 Redis 高并发分布式缓存 Ubuntu源码编译安装 云服务器 启动并测试 redis-server redis-cli
57 3
|
2月前
|
缓存 分布式计算 NoSQL
大数据-47 Redis 缓存过期 淘汰删除策略 LRU LFU 基础概念
大数据-47 Redis 缓存过期 淘汰删除策略 LRU LFU 基础概念
78 2
|
4月前
|
缓存 算法 前端开发
深入理解缓存淘汰策略:LRU和LFU算法的解析与应用
【8月更文挑战第25天】在计算机科学领域,高效管理资源对于提升系统性能至关重要。内存缓存作为一种加速数据读取的有效方法,其管理策略直接影响整体性能。本文重点介绍两种常用的缓存淘汰算法:LRU(最近最少使用)和LFU(最不经常使用)。LRU算法依据数据最近是否被访问来进行淘汰决策;而LFU算法则根据数据的访问频率做出判断。这两种算法各有特点,适用于不同的应用场景。通过深入分析这两种算法的原理、实现方式及适用场景,本文旨在帮助开发者更好地理解缓存管理机制,从而在实际应用中作出更合理的选择,有效提升系统性能和用户体验。
206 1
|
5月前
|
缓存 Python
在Python中,`functools`模块提供了一个非常有用的装饰器`lru_cache()`,它实现了最近最少使用(Least Recently Used, LRU)缓存策略。
在Python中,`functools`模块提供了一个非常有用的装饰器`lru_cache()`,它实现了最近最少使用(Least Recently Used, LRU)缓存策略。
|
4月前
|
存储 缓存 Java
|
4月前
|
存储 缓存 算法
Python 从零开始实现一个简单的LRU缓存
Python 从零开始实现一个简单的LRU缓存
43 0
|
6月前
|
缓存 算法 索引
LeetCode146:LRU缓存
LeetCode146:LRU缓存
46 1
|
5月前
|
缓存 算法 前端开发
前端 JS 经典:LRU 缓存算法
前端 JS 经典:LRU 缓存算法
99 0