Java使用LinkedHashMap实现LRU淘汰算法

蔚落 2023-07-19 15:29 94阅读 0赞

### 什么是LRU ###

`LRU` 是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法。

在一般标准的操作系统教材里，会用下面的方式来演示 LRU 原理，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。

![format_png][]

LRU示意图

那么Java中如何实现一个LRU算法呢。

### LinkedHashMap ###

LinkedHashMap是维护了双向链表的HashMap，保持了插入元素的顺序。

LinkedHashMap提供了一个钩子方法，在新插入元素后可以决定是否删除最老的元素。

/**
         * LRU中最大元素数量
         */
        private int maxSize;
    
        public LRUByLinkedHashMap(int maxSize) {
            // 容量为最大值/0.75，即最大负载容量为maxSize
            // accessOrder=true  根据查询排序，即最近被使用的放到后面
            super((int) Math.ceil(maxSize / 0.75) + 1, 0.75f, true);
            this.maxSize = maxSize;
        }
    
        /**
         * 此方法为钩子方法，map插入元素时会调用此方法
         * 此方法返回true则证明删除最老的因子
         *
         * @param eldest
         * @return
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > maxSize;
        }

[format_png]: /images/20230528/35a1887e0f38475dbeb5f6bfcbef9fd0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

相关 LinkedHashMap实现LRU算法

目录 LRU 简介 LinkedHashMap的使用手写LRU缓存淘汰算法 LRU 简介 LRU 是 Least Rec

我就是我/ 2024年03月26日 10:43/ 0 赞/ 89 阅读

相关【算法】不使用LinkedHashMap实现一个LRU缓存

文章目录什么是LRU？设计思路代码实现 LRU是我在面试过程中遇到的比较多的算法题了，并且我自己的项目中也手写了LRU算法，所以觉得还是有

Love The Way You Lie/ 2024年03月16日 09:15/ 0 赞/ 67 阅读

相关缓存淘汰算法-LRU

目录前言一、LRU 算法二、LRU 算法图解三、LRU 算法实现四、LRU 算法分析五、LRU 算法改进方案 ----------------

绝地灬酷狼/ 2024年03月08日 02:03/ 0 赞/ 102 阅读

相关基于LinkedhashMap实现的LRU算法

LRU全称是Least Recently Used，即最近最久未使用的意思。 LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很

曾经终败给现在/ 2023年08月17日 17:08/ 0 赞/ 148 阅读

相关 Java使用LinkedHashMap实现LRU淘汰算法

什么是LRU `LRU` 是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法。在一般标准的操作系统教材里，会用下面的方式来演示 LRU

蔚落/ 2023年07月19日 15:29/ 0 赞/ 95 阅读

相关如何实现LRU缓存淘汰算法

一概述缓存是一种提高数据可读性能的技术，在硬件设计，软件开发中都有着非常广泛的应用，常见的有CPU缓存，数据库缓存，浏览器缓存等。缓存的大小有限，当缓存被用完后，

た入场券/ 2022年12月11日 13:33/ 0 赞/ 190 阅读

相关【算法】LRU（缓存淘汰）

前言 Github：[https://github.com/yihonglei/road-of-arch][https_github.com_yihonglei_road

曾经终败给现在/ 2022年11月29日 11:44/ 0 赞/ 242 阅读

相关使用LinkedHashMap实现LRU算法

LRU算法，最近最少使用原则，如果要实现该算法，可以借助LinkedHashMap数据结构，LinkedHashMap继承HashMap，底层使用哈希表和双向链表来保存所有元素

谁践踏了优雅/ 2022年10月25日 14:01/ 0 赞/ 291 阅读

相关缓存淘汰算法--LRU

1. LRU 1.1. 原理 LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问

迷南。/ 2022年05月25日 05:06/ 0 赞/ 252 阅读

相关模拟缓存淘汰算法LRU（Java实现）

也是一个面试题，题目是这样的： > 假设有这样的缓存，如果get到数据返回成功，如果没有get到数据，那么返回失败，不管能否get到数据，总是会把 > 最新的记录加入缓存

Bertha 。/ 2021年12月19日 04:45/ 0 赞/ 391 阅读