`

LRU算法解析

LRU 
阅读更多

在项目中用到了common-collections中LRUMap,最近有空看了一下源码,对LRU算法有了更具体的认识,LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

LRUMap实现的核心思想是使用一个链表,将经常使用的放在链表的尾部,如果LRUMap的size已经到最大值时不会像传统的Map会进行自动容量扩充,而是从链表的头部覆盖数据,覆盖后以前头部的数据就相当于被淘汰。LRUMap

中使用了一个固定大小的数组来存放数据,数组中每个元素都是一个LinkEntry数据结构,除了key和value外还多了一个after和before,这样就形成了一个双向链表

protected static class LinkEntry extends HashEntry {
        protected AbstractLinkedMap.LinkEntry before;
        protected AbstractLinkedMap.LinkEntry after;

        protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
            super(next, hashCode, key, value);
        }
    }

 get操作时如果找到对应的对象,会修改相关对象的after和before的引用将该对象移到链表的末尾,表示最近刚被访问过

public Object get(Object key) {
        LinkEntry entry = (LinkEntry)this.getEntry(key);
        if(entry == null) {
            return null;
        } else {
            this.moveToMRU(entry);
            return entry.getValue();
        }
    }

 其中moveToMRU方法就是移动对象到链表的末尾

put操作时会执行以下几步:

  1. 如果链表中存在key,会替换对应的value并将该对象设置成链表的末尾
  2. 如果size没有到最大值,会根据计算hashcode放入到在数组中,并将该对象设置成链表的末尾
  3. 如果size达到最大值,会从链表的头部开始覆盖数据,并将该对象修改成链表的末尾

LRUMap是非线程安全的,如果需要线程安全可以使用Collections.synchronizeMap()获取一个线程安全的Map

或者使用goole提供的一个ConcurrentLinkedHashMap,一个基于ConcurrentHashMap实现的LRU算法,性能跟ConcurrentHashMap相差无几,源代码地址:https://github.com/ben-manes/concurrentlinkedhashmap

相关链接:

http://flychao88.iteye.com/blog/1977653 LRU算法详解和优化算法

http://janeky.iteye.com/blog/1534352 线程安全的LRUMap-ConcurrentLinkedHashMap

分享到:
评论

相关推荐

    LRU算法的实现

    近期最少使用算法

    lru算法C语言实现

    本文将详细介绍一个用C语言实现的LRU算法示例代码,并对其实现细节进行深入解析。 #### 二、LRU算法概述 LRU算法的核心思想是:当缓存满时,优先淘汰最近最少使用的数据。这里的“最近最少使用”是指在最近一段...

    LRU算法LRU算法LRU算法LRU算法

    在缓存或者数据库管理系统中,LRU算法被广泛应用,因为它的实现简单且效果良好。 LRU算法的核心思想是:当内存满时,最近最少使用的数据会被优先淘汰。也就是说,如果一个数据最近被访问过,那么它在未来被访问的...

    仿真LRU算法

    ### LRU算法仿真:深入解析与C语言实现 在计算机科学领域,LRU(Least Recently Used,最近最少使用)算法是一种广泛应用于操作系统内存管理和高速缓存管理中的页面调度策略。其核心思想是当缓存满时,优先淘汰最近...

    页面替换算法———LRU算法

    ### LRU页面替换算法 #### 一、LRU算法简介 LRU(Least Recently Used,...它不仅能够帮助用户理解LRU算法的工作原理,还能够直观地展示算法执行过程中内存状态的变化,从而更好地掌握LRU算法的应用场景和技术细节。

    LRU 页面置换算法 最近最久未使用 源代码 c/c++

    通过上述C/C++代码的解析,我们不仅了解了LRU算法的基本原理,还掌握了其具体的实现细节,这对于深入理解操作系统内存管理机制具有重要意义。 然而,值得注意的是,实际应用中LRU算法的性能可能会受到多种因素的...

    操作系统 程实现请求分页存储管理页面Optimal、FIFO、LRU置换算法

    本实验旨在通过实际编程实现请求分页存储管理中的三种页面置换算法:最优置换算法(Optimal)、先进先出置换算法(FIFO)以及最近最少使用置换算法(LRU),帮助学生深入理解和掌握虚拟存储管理的核心概念和技术。...

    虚拟内存程序模拟实现,VC编写,使用LRU算法

    ### 虚拟内存程序模拟实现,VC编写,使用LRU算法 #### 一、概述 虚拟内存技术是现代操作系统中的关键组成部分之一,它通过在物理内存与磁盘之间进行数据交换来为用户提供一个比实际物理内存大得多的虚拟地址空间。...

    页面置换算法(FIFO,LRU,OPT)

    因此,LRU算法倾向于保留那些最近被频繁访问的页面。 **实现原理:** - 维护一个双向链表或类似的结构来存储内存中的页面。 - 当一个页面被访问时,它被移动到链表的一端(通常是尾部)。 - 当内存满时,替换掉链表...

    操作系统课程设计最近最久未使用算法(LRU)

    通过此项目,不仅可以加深学生对于LRU算法的理解,还能提升其编程能力。 #### LRU算法简介 LRU算法是一种广泛应用于操作系统中的页面置换算法,其核心思想是在需要替换页面时,选择最近一段时间内最久未使用的页面...

    页面置换算法FIFO:先进先出 NUR: 最近未使用算法

    为了改进LRU,出现了LRU-K算法,该算法结合了最近K次访问的时间信息,通过调整K值来平衡算法性能。较大的K值会使得算法更接近LFU,而较小的K值则接近LRU。在实际应用中,选择合适的K值可以更好地平衡性能和资源利用...

    页面置换算法 OPT FIFO LRU

    由于提供的代码片段不完整,我们无法完全解析LRU算法的具体实现细节。不过,通常的实现方式是维护一个数据结构(如链表或哈希表)来跟踪每个页面最近的访问时间。当发生缺页中断时,查找最近最少使用的页面并将其...

    操作系统请求式分页实验报告含源码,用FIFO和LRU两种方法,动态输入页面以及物理块数,页面友好,操作简单

    - **LRU算法**:同样地,从第6位开始出现页面置换,但LRU算法会选择最近最少使用的页面进行替换。具体而言,当访问某个页面时,该页面的“最近使用”标记会被重置为0,其余页面的标记则递增1。 #### 实验总结 通过...

    采用先进先出FIFO或LUR算法实现分页管理的缺页调度.doc

    不同之处在于,在LRU算法中,当发生缺页时,程序会将最新访问的页面移动到队列的开头,而将其他页面依次向后移动,以此模拟“最近使用”的特性。 - **输出结果**:最终输出每个时间点的内存状态及是否发生了缺页中断...

    操作系统页面置换-最近最少使用(LRU)算法模拟.doc.doc

    在提供的Java程序设计中,作者实现了一个LRU算法的模拟器。这个模拟器通过用户输入的8个数字来代表要访问的页面,并通过一个二维数组`record`记录这些页面的访问历史。程序使用了四个行(`Text[][]`数组)来展示页面...

    模拟操作系统的页面置换

    5. **页面置换算法的应用**:分别使用OPT、FIFO和LRU算法对指令地址流进行处理,记录并比较不同算法下的缺页中断率。 6. **结果分析**:分析页面大小和内存块数量对缺页中断率的影响,对比不同页面置换算法的性能...

    java实现lru

    LRU算法是一种常用的缓存淘汰策略,当缓存空间已满且需要插入新的数据时,该算法会自动移除最近最少使用的数据项,为新数据腾出空间。LRU算法适用于多种场景,尤其是在内存管理和磁盘缓存方面有着广泛的应用。 ### ...

    zhongduan.rar_FIFO matlab _LRU_LRU MATLAB_lru matlab_zhongduan m

    通过编写名为"zhongduan.m"的MATLAB脚本,我们可以模拟不同的内存分配场景,如改变内存块的数量或不同进程的时间片分配,进而分析FIFO和LRU算法在这些条件下的性能差异。 在"zhongduan.m"文件中,通常会包含以下...

    页面置换算法(Optimal、FIFO、LRU)

    本文将详细介绍三种常见的页面置换算法:最佳置换算法(Optimal)、先进先出算法(FIFO)以及最近最少使用算法(LRU),并基于给定的部分代码进行解析。 #### 一、最佳置换算法(Optimal) 最佳置换算法是一种理论...

    操作系统实验三页面置换算法实验报告.docx

    该实验报告主要介绍了操作系统中的页面置换算法实验,涵盖了 FIFO、Optimal 和 LRU 等三种常见的页面置换算法。实验报告中还提供了实验源码,展示了如何使用 C 语言实现这些算法。 知识点一:页面置换算法 页面...

Global site tag (gtag.js) - Google Analytics