LinkedHashMap如何实现LRU缓存淘汰策略?

这篇具有很好参考价值的文章主要介绍了LinkedHashMap如何实现LRU缓存淘汰策略?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.LRU是什么?

LRU,Least Recently Used,最近最少使用,也就是优先淘汰最近最少使用的元素。

2.如何使用LinkedHashMap实现LRU?

简而言之,就是将LinedHashMap的accessOrder设为true即可。
demo实现如下:

package com.hikvision.dai.didi;

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

/**
 * @Classname LRU
 * @Description LRU
 * @Date 2023/4/22 21:16
 * @Created by Chamption-Dai
 */
public class LRU<K, V> extends LinkedHashMap<K, V> {

    /**
     * 保存缓存的容量
     */
    private Integer cache;

    /**
     * 构造函数
     *
     * @param cache      缓存容量
     * @param loadFactor 负载因子
     */
    public LRU(int cache, float loadFactor) {
        //linkedHashMap中的accessOrder设为true
        super(cache, loadFactor, true);
        this.cache = cache;
    }

    /**
     * 重写removeEldestEntry()方法设置何时移除旧元素
     *
     * @param eldest 最好使用的元素
     * @return boolean
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        //当元素容量大鱼设置的缓存容量,就开始移除最少使用的元素
        return size() > this.cache;
    }

    public Integer getInitialCap() {
        return cache;
    }

    public void setInitialCap(Integer cache) {
        this.cache = cache;
    }
}

测试一下:

package com.hikvision.dai.didi;

/**
 * @Classname LRUTest
 * @Description LRUTest
 * @Date 2023/4/22 21:00
 * @Created by Chamption-dai
 */
public class LRUTest {

    public static void main(String[] args) {
        //设置缓存大小为5,负载因子为0.75f
        LRU<String, Integer> lru = new LRU<>(5, 0.75f);

        //添加元素:
        lru.put("1", 1);
        lru.put("2", 2);
        lru.put("3", 3);
        lru.put("4", 4);
        lru.put("5", 5);

        System.out.println(lru); //输出:{1=1, 2=2, 3=3, 4=4, 5=5}

        lru.put("100", 100);
        System.out.println(lru); //输出:{2=2, 3=3, 4=4, 5=5, 100=100} ,现象:最开始添加的“最老“的”1=1被移除了

        //使用entry:("3",3)
        lru.get("3");
        //调用get()或者put(),LinkedHashMap中的双向链表会把对应的元素放在链表的末尾,3=3目前是最年轻的
        System.out.println(lru); //输出:{2=2, 4=4, 5=5, 100=100, 3=3}。

        lru.put("200", 200);
        System.out.println(lru); //{4=4, 5=5, 100=100, 3=3, 200=200},现象,最老的“2=2”被移除了
    }
}

3.LinkedHashMap源码分析

3.1 LinkedHashMap简介

LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以用来实现LRU缓存策略。

LinkedHashMap可以看成是 LinkedList + HashMap。

3.2 继承体系

LinkedHashMap如何实现LRU缓存淘汰策略?

3.3 内部数据存储结构

LinkedHashMap如何实现LRU缓存淘汰策略?
HashMap是(数组 + 单链表 + 红黑树)的存储结构,那LinkedHashMap是怎么存储的呢?

通过上面的继承体系,我们知道它继承了HashMap,所以它的内部也有这三种结构,但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。

添加删除元素的时候需要同时维护在HashMap中的存储,也要维护在LinkedList中的存储,所以性能上来说会比HashMap稍慢。

3.4源码解析

属性:
    /**
     * The head (eldest) of the doubly linked list.(双向链表头节点)
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.(双向链表尾节点)
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *  是否按访问顺序排序
     */
    final boolean accessOrder;
构造方法:
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
  
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }
    
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

前四个构造方法accessOrder都等于false,说明双向链表是按插入顺序存储元素。

最后一个构造方法accessOrder从构造方法参数传入,如果传入true,则就实现了按访问顺序存储元素,这也是实现LRU缓存策略的关键。

afterNodeInsertion(boolean evict)方法

在节点插入之后做些什么,在HashMap中的putVal()方法中被调用,可以看到HashMap中这个方法的实现为空。

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
      
     //上述实现LRU重写了该方法,重写removeEldestEntry()可以实现不同的缓存机制
     protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

evict,英:/ɪˈvɪkt/ 美:/ɪˈvɪkt/ 驱逐、逐出的意思。

(1)如果evict为true,且头节点不为空,且确定移除最老的元素,那么就调用HashMap.removeNode()把头节点移除(这里的头节点是双向链表的头节点,而不是某个桶中的第一个元素);

(2)HashMap.removeNode()从HashMap中把这个节点移除之后,会调用afterNodeRemoval()方法;

(3)默认removeEldestEntry()方法返回false,也就是不删除元素。

afterNodeAccess(Node e)方法

在节点访问之后被调用,主要在put()已经存在的元素或get()时被调用,如果accessOrder为true,调用这个方法把访问到的节点移动到双向链表的末尾。

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        // 如果accessOrder为true,并且访问的节点不是尾节点
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                
           // 把p节点从双向链表中移除
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            
            // 把p节点放到双向链表的末尾
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            
            // 尾节点等于p
            tail = p;
            ++modCount;
        }
    }

(1)如果accessOrder为true,并且访问的节点不是尾节点;

(2)从双向链表中移除访问的节点;

(3)把访问的节点加到双向链表的末尾;(末尾为最新访问的元素)

afterNodeRemoval(Node e)方法

在节点被删除之后调用的方法。

 void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

直接将节点从双向链表中移除。

get(Object key)方法

获取元素

   public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

如果查找到了元素,且accessOrder为true,则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。

源码总结

(1)LinkedHashMap继承自HashMap,具有HashMap的所有特性;

(2)LinkedHashMap内部维护了一个双向链表存储所有的元素;

(3)如果accessOrder为false,则可以按插入元素的顺序遍历元素;

(4)如果accessOrder为true,则可以按访问元素的顺序遍历元素;

(5)LinkedHashMap的实现非常精妙,很多方法都是在HashMap中留的钩子(Hook),直接实现这些Hook就可以实现对应的功能了,并不需要再重写put()等方法;

(6)默认的LinkedHashMap并不会移除旧元素,如果需要移除旧元素,则需要重写removeEldestEntry()方法设定移除策略;

(7)LinkedHashMap可以用来实现LRU缓存淘汰策略;文章来源地址https://www.toymoban.com/news/detail-423502.html

到了这里,关于LinkedHashMap如何实现LRU缓存淘汰策略?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 从 LinkedHashMap 源码到手撕 LRU 缓存

    大家好,我是 方圆 。最近在刷 LeetCode 上LRU缓存的题目,发现答案中有 LinkedHashMap 和自己定义双向链表的两种解法,但是我对 LinkedHashMap 相关源码并不清楚,所以准备学习和记录一下。如果大家想要找刷题路线的话,可以参考 Github: LeetCode。 LRU(Least Recently Used) ,即最近最少使

    2024年02月09日
    浏览(39)
  • LRU淘汰策略执行过程

    目录 1 介绍 2 Redis内存淘汰策略 2.1 设置过期时间的淘汰策略 2.2 所有 key 的淘汰策略 3 LRU淘汰策略执行过程 4 算法实现 Redis无论是惰性删除还是定期删除,都可能存在删除不尽的情况,无法删除完全,比如每次删除完过期的 key 还是超过 25%,且这些 key 再也不会被客户端访问。

    2024年02月11日
    浏览(29)
  • LRU 缓存淘汰算法

    Least Recently Used(LRU) 是缓存淘汰一种常用的策略,内存满了则优先删除最久没被使用的数据。 接收一个参数 capacity 作为缓存的最大容量 实现一个函数 put() 添加数据到缓存 实现一个函数 get() 查询缓存中的数据 以上函数应该在 (O(1)) 的时间内完成 满足以上需求的数据结构 —

    2024年02月11日
    浏览(60)
  • LinkedHashMap 简单实现LRU

    要使用 LinkedHashMap 来实现LRU(最近最少使用)缓存,可以设置它的访问顺序为 true ,以便在每次访问一个元素时,将它移到最后,从而实现LRU的特性。以下是一个简单的Java示例: 在上面的示例中,创建了一个 LRUCache 类,它扩展了 LinkedHashMap ,并在构造函数中设置了访问顺序

    2024年02月08日
    浏览(52)
  • 缓存替换策略:LRU-K算法详解及其C++实现 CMU15-445 Project#1

    CMU 15-445 (FALL 2022) Project #1 Task#2 LRU-K 替换策略详解实现,尽量提供思路,也可以为其他同学实现LRU-K算法做参考 参考文献:The LRU-K page replacement algorithm for database disk buffering (acm.org) 在网上都找不到其他参考,只有这一篇1993年的论文 LRU-K替换策略 LRU-K是LRU算法的一种衍生。强烈

    2023年04月12日
    浏览(37)
  • 缓存淘汰策略

    LRU 与 LFU 缓存策略及其实现。 鉴于磁盘和内存读写的差异性,DB 中低频写、高频读的数据适合放入内存中,直接供应用层读写。在项目中读取用户资料时就使用到了 LRU,而非放到 Redis 中。 缓存的 2 个基本实现 缓存的 2 个特征 命中率:即命中数 / 请求数,比值越高即表明缓

    2024年02月16日
    浏览(45)
  • Redis的缓存过期淘汰策略

    生产上你们redis内存设置多少? 如何配置,修改redis的内存大小? 如果内存满了怎么办? redis清理内存的方式?定期删除和惰性删除了解过吗? redis缓存淘汰策略有哪些?分别是什么?你用哪个? redis的LRU了解过吗?请手写LRU。 LRU和LFU算法的区别是什么? … 如何查看Redis最

    2024年02月07日
    浏览(48)
  • Redis_缓存2_缓存删除和淘汰策略

    14.5.1 过期数据 可以使用ttl查看key的状态。已过期的数据,redis并未马上删除。优先去执行读写数据操作,删除操作延后执行。 14.5.2 删除策略 redis中每一个value对应一个内存地址,在expires,一个内存地址,对应一个时间截,如果达到指定时间,就完成删除处理 三种删除策略

    2024年02月13日
    浏览(54)
  • (高阶) Redis 7 第19讲 缓存过期淘汰策略 大厂篇

    1. 生产上,redis内存设置的多少 2. 如何配置、修改Redis 内存大小 3. 如果内存满了,如何处理 4. Redis 清理内存的方式有哪些?定期删除和惰性删除了解吗 5. Redis 缓存淘汰策略有哪些?分别是什么?你用哪个 6. Redis 的LRU了解过吗?请手写LRU 7. LRU和LFU 算法的区别是什么  Redis 默

    2024年02月07日
    浏览(47)
  • rust里如何快速实现一个LRU 本地缓存?

    LRU是Least Recently Used(最近最少使用)的缩写,是一种常见的缓存淘汰算法。LRU算法的基本思想是,当缓存空间已满时,优先淘汰最近最少使用的数据,以保留最常用的数据。 在计算机系统中,LRU算法常用于缓存系统、页面置换算法等场景,以提高数据访问的效率和性能。 要

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包