在项目中用到了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操作时会执行以下几步:
- 如果链表中存在key,会替换对应的value并将该对象设置成链表的末尾
- 如果size没有到最大值,会根据计算hashcode放入到在数组中,并将该对象设置成链表的末尾
- 如果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
相关推荐
近期最少使用算法
本文将详细介绍一个用C语言实现的LRU算法示例代码,并对其实现细节进行深入解析。 #### 二、LRU算法概述 LRU算法的核心思想是:当缓存满时,优先淘汰最近最少使用的数据。这里的“最近最少使用”是指在最近一段...
在缓存或者数据库管理系统中,LRU算法被广泛应用,因为它的实现简单且效果良好。 LRU算法的核心思想是:当内存满时,最近最少使用的数据会被优先淘汰。也就是说,如果一个数据最近被访问过,那么它在未来被访问的...
### LRU算法仿真:深入解析与C语言实现 在计算机科学领域,LRU(Least Recently Used,最近最少使用)算法是一种广泛应用于操作系统内存管理和高速缓存管理中的页面调度策略。其核心思想是当缓存满时,优先淘汰最近...
### LRU页面替换算法 #### 一、LRU算法简介 LRU(Least Recently Used,...它不仅能够帮助用户理解LRU算法的工作原理,还能够直观地展示算法执行过程中内存状态的变化,从而更好地掌握LRU算法的应用场景和技术细节。
通过上述C/C++代码的解析,我们不仅了解了LRU算法的基本原理,还掌握了其具体的实现细节,这对于深入理解操作系统内存管理机制具有重要意义。 然而,值得注意的是,实际应用中LRU算法的性能可能会受到多种因素的...
本实验旨在通过实际编程实现请求分页存储管理中的三种页面置换算法:最优置换算法(Optimal)、先进先出置换算法(FIFO)以及最近最少使用置换算法(LRU),帮助学生深入理解和掌握虚拟存储管理的核心概念和技术。...
### 虚拟内存程序模拟实现,VC编写,使用LRU算法 #### 一、概述 虚拟内存技术是现代操作系统中的关键组成部分之一,它通过在物理内存与磁盘之间进行数据交换来为用户提供一个比实际物理内存大得多的虚拟地址空间。...
因此,LRU算法倾向于保留那些最近被频繁访问的页面。 **实现原理:** - 维护一个双向链表或类似的结构来存储内存中的页面。 - 当一个页面被访问时,它被移动到链表的一端(通常是尾部)。 - 当内存满时,替换掉链表...
通过此项目,不仅可以加深学生对于LRU算法的理解,还能提升其编程能力。 #### LRU算法简介 LRU算法是一种广泛应用于操作系统中的页面置换算法,其核心思想是在需要替换页面时,选择最近一段时间内最久未使用的页面...
为了改进LRU,出现了LRU-K算法,该算法结合了最近K次访问的时间信息,通过调整K值来平衡算法性能。较大的K值会使得算法更接近LFU,而较小的K值则接近LRU。在实际应用中,选择合适的K值可以更好地平衡性能和资源利用...
由于提供的代码片段不完整,我们无法完全解析LRU算法的具体实现细节。不过,通常的实现方式是维护一个数据结构(如链表或哈希表)来跟踪每个页面最近的访问时间。当发生缺页中断时,查找最近最少使用的页面并将其...
- **LRU算法**:同样地,从第6位开始出现页面置换,但LRU算法会选择最近最少使用的页面进行替换。具体而言,当访问某个页面时,该页面的“最近使用”标记会被重置为0,其余页面的标记则递增1。 #### 实验总结 通过...
不同之处在于,在LRU算法中,当发生缺页时,程序会将最新访问的页面移动到队列的开头,而将其他页面依次向后移动,以此模拟“最近使用”的特性。 - **输出结果**:最终输出每个时间点的内存状态及是否发生了缺页中断...
在提供的Java程序设计中,作者实现了一个LRU算法的模拟器。这个模拟器通过用户输入的8个数字来代表要访问的页面,并通过一个二维数组`record`记录这些页面的访问历史。程序使用了四个行(`Text[][]`数组)来展示页面...
5. **页面置换算法的应用**:分别使用OPT、FIFO和LRU算法对指令地址流进行处理,记录并比较不同算法下的缺页中断率。 6. **结果分析**:分析页面大小和内存块数量对缺页中断率的影响,对比不同页面置换算法的性能...
LRU算法是一种常用的缓存淘汰策略,当缓存空间已满且需要插入新的数据时,该算法会自动移除最近最少使用的数据项,为新数据腾出空间。LRU算法适用于多种场景,尤其是在内存管理和磁盘缓存方面有着广泛的应用。 ### ...
通过编写名为"zhongduan.m"的MATLAB脚本,我们可以模拟不同的内存分配场景,如改变内存块的数量或不同进程的时间片分配,进而分析FIFO和LRU算法在这些条件下的性能差异。 在"zhongduan.m"文件中,通常会包含以下...
本文将详细介绍三种常见的页面置换算法:最佳置换算法(Optimal)、先进先出算法(FIFO)以及最近最少使用算法(LRU),并基于给定的部分代码进行解析。 #### 一、最佳置换算法(Optimal) 最佳置换算法是一种理论...
该实验报告主要介绍了操作系统中的页面置换算法实验,涵盖了 FIFO、Optimal 和 LRU 等三种常见的页面置换算法。实验报告中还提供了实验源码,展示了如何使用 C 语言实现这些算法。 知识点一:页面置换算法 页面...