在项目中用到了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
相关推荐
近期最少使用算法
介绍LFU使用数据的访问频率,有利于数据的总体优化使用,但不利于数据访问方式的变化和猝... .LRU-K算法则是使用最后第K次访问时间来扩展LRU算法,依靠K值的大小进行平衡.它们都是对访问时间的修正,是对LRU算法的改进.
1.问题描述:假设有一个6x6的棋盘,每个格子里有一个奖品(每...解析:所谓LRU算法,是指在发生缺页并且没有空闲主存块时,把最近最少使用的页面换出主存块,腾出地方来调入新页面。提示:可用列表切片模拟LRU算法的用法。
开发知乎的第一步,首先熟悉看知乎的API以及Json数据的解析,才能进行下一步。
文显示模块用LRU算法的Cache管理字模,支持平滑字体显示(反锯齿),MMX指令优 化,成倍提高绘制速度。强大的可扩展GUI系统,模仿VCL的层次和接口,使用起来 类似在C++ Builder下的开发,实现了各种常用控件。另有...
文显示模块用LRU算法的Cache管理字模,支持平滑字体显示(反锯齿),MMX指令优 化,成倍提高绘制速度。强大的可扩展GUI系统,模仿VCL的层次和接口,使用起来 类似在C++ Builder下的开发,实现了各种常用控件。另有...
异步加载的练习demo 主要涉及知识点: 1.解析json格式数据,主要包括图片,文本 2.使用线程和AsynTask俩种异步方式从网络下载图片...4.使用Lru缓存算法 5.改进加载:仅在listview滑动停止后才加载可见项,滑动中不加载
支持小文件内存缓存(LRU算法,可配置尺寸) 支持304木有修改(静态服务器最重要的就是这个了吧) 支持gzip、deflate压缩 支持分段下载(支持部分,可用迅雷等多线程下载工具) 提供动态解析的接口 最后由于是本人...
中文显示模块用LRU算法的Cache管理字模,支持平滑字体显示(反锯齿),MMX指令优化,成倍提高绘制速度。强大的可扩展GUI系统,模仿VCL的层次和接口,使用起来类似在C++ Builder下的开发,实现了各种常用控件。另有...
通过用c++语言来模拟实现操作系统的页面置换算法,包括FIFO、LRU、LFU、时钟算法、NRU、OPT
实现的算法最佳随机的先进先出LRU 钟NFU NFU 老化去做提升配置能力配置文件(json 解析器?或者只是 VAR=meh。我有点喜欢的功能集) 从文件中读取页面调用或在配置文件中定义(硬编码页面引用不是 beuno) 最优算法...
经典题目解析&golang版代码 简单难度 中等难度 困难难度 算法专项 KMP 算法 动态规划: 887. 鸡蛋掉落 5. 最长回文子串 494. 目标和 322. 零钱兑换 279. 完全平方数 198. 打家劫舍 152. 乘积最大子序列 139. 单词拆分...
LRU算法 9 Window、ViewRootImpl ... 待续 ... 待续 ... Binder Framework 梳理Android Binder的IPC机制,如何进行进程间通信 序号 文章名 概述 0 Linux IPC 机制 & 为何选 Binder 1 Android 中的序列化 2 使用AIDL...
力扣算法解题,java语言 题解 简单 序号(力扣题序号) 题名 题解 两数之和 整数反转 相同的树 最长回文串 链表的中间节点 三维形体的表面积 卡牌分组 可以被一步捕获的棋子数 不用加号的加法 最小的K个数 不用加减...
Dom解析器示例 观察者模式示例 异体平衡算法 快速排序示例 递归示例 日期格式示例 从适当的位置删除字符串中的重复项。 反向链接的第一个例子 跳过总和。 字符串中所有可能的组合 所有Tree遍历示例。 添加以字符...
FinalBitmap的内存管理使用lru算法, 没有使用弱引用(android2.3以后google已经不建议使用弱引用,android2.3后强行回收软引用和弱引用,详情查看android官方文档), 更好的管理bitmap内存。FinalBitmap可以...
实例25 模拟LRU页面置换算法 79 实例26 大整数阶乘新思路 82 实例27 银行事件驱动模拟程序 84 实例28 模拟迷宫探路 87 实例29 实现高随机度随机序列 89 实例30 停车场管理系统 91 第3部分 文本屏幕与...
每片文章都结合了 「解析 + 视频 + 代码」 三大模块,工程量非常之大 为了防止更新速度过快,文章质量下降的问题,宁可更新速度慢,也要保证质量 不求快,只求优质,每篇文章将以 2 ~ 3 天的周期进行更新,力求保持...
25 模拟LRU页面置换算法 26 大整数阶乘新思路 27 银行事件驱动模拟程序 28 模拟迷宫探路 29 实现高随机度随机序列 30 停车场管理系统 31 菜单实现 32 窗口制作 33 模拟屏幕保护程序 ...