- 浏览: 197317 次
文章分类
- 全部博客 (224)
- jsp (5)
- jsf (7)
- web (11)
- js (12)
- COBOL (5)
- php (7)
- jconsole (1)
- java (11)
- ajax (1)
- PHP魔法方法 (1)
- 项目管理工具 (3)
- 项目管理 (2)
- svn (8)
- redmine (1)
- mysql (4)
- qrcode,php (1)
- qrcode (1)
- 多进程 (3)
- html (1)
- excel (2)
- seasar2 (1)
- db (1)
- entity (1)
- IOS8 (1)
- SWIFT (1)
- 正则表达式 (1)
- RabbitVCS (1)
- url (1)
- thinkphp (2)
- c++ (5)
- win32 API函数 (1)
- htaccess (1)
- makefile (3)
- C/C++ (12)
- Linux (1)
- miui (2)
- unix (1)
- wechat (1)
- websocket (1)
- SpringMVC (3)
- VSAM (1)
- centos (2)
- wamp (1)
- server (1)
- 优酷视频上传并去除广告 (1)
- owncload (1)
- cloud (1)
- ubuntu (1)
- pdf转换成word (1)
- 微信,weixin (1)
- 行业系统 (3)
- 超级外卖源代码 (0)
- 软件专利 (1)
- 申请 (1)
- vba (1)
- UML (1)
- 程序切片 (1)
- 股票心得 (1)
- 威客建站 (1)
- 微信开发学习路线 (1)
- 远程开机 (1)
- spring mvc (1)
- JEECMS (1)
- Node.js (1)
- ThinkJS (1)
- maven (2)
- MyEclipse+Tomcat+MAVEN+SVN (1)
- Spring+SpringMVC+MyBatis (1)
- wampserver (0)
- RESTful (1)
- hibernate (4)
- Spring+SpringMVC (1)
- 响应式布局 (1)
- 响应式布局模板 (1)
- Aptana (3)
- 遗传算法 (1)
- 进化算法 (1)
- bower (1)
- HTML5 (1)
- Android官方培训课程 (1)
- MySQL锁 (1)
- 扫描枪 (1)
- 微信公众平台 (1)
- 企业号 (1)
- ddns (1)
- java获取外网ip (1)
- DDNS,阿里云,云解析,万网域名,阿里云域名 (1)
- SEO (1)
- Jboss (2)
- wildfly (1)
- WildFly8 (2)
- NT Kernel (1)
- 反向代理 (1)
- Spring嵌套事务 (1)
- apache (3)
- 防止浏览器记住用户名及密码的简单实用方法 (1)
- 时间戳 (1)
- 字体 (1)
- 网络爬虫准 (1)
- 屏蔽后退按钮 (1)
- java web (1)
- JavaMail (1)
- windows服务 (1)
- Freemarker (1)
- TortoiseGit (2)
- oschina (1)
- JSON (1)
- Boost (1)
- MUI (1)
- github (1)
- Python2.7 (1)
- Python3.0 (1)
- Odoo (1)
- java socket (1)
- OpenERP (2)
- werkzeug (1)
- JNA (2)
- proxifier (1)
- WebService (1)
- 企业应用集成 (1)
- vmware (1)
- Navicate (1)
- 三体 (1)
- oracle同步 (1)
- 微信 (3)
- java设计模式 (1)
- 工具 (1)
- JavaScript跨域 (1)
- LB (1)
- 负载均衡 (1)
- AngularJS (1)
- HBuilder (1)
- Echarts (1)
- Json Web Token (1)
- PassportSDK (1)
- ubuntu kylin xterm 乱码 (1)
- ubuntu kylin17 安装字体教程 (1)
- wps (1)
- jetbrains (1)
- MySQL5.7 (1)
- Nginx (1)
- JDK (1)
最新评论
-
cuiyadll:
谢谢楼上的推荐
实战:jQuery Mobile开发HTML5移动应用 -
marty:
使用JQueryMobile,推薦使用這免費開發工具,提供可視 ...
实战:jQuery Mobile开发HTML5移动应用 -
men_clslji:
按照目前的方法只是防止刷新页面时不再执行X(添加),而toke ...
有了上一篇博文,类似地顺便说说表单防重复提交。
引自:http://www.blogjava.net/xmatthew/archive/2012/06/28/380150.html
jar包下载地址:
http://commons.apache.org/proper/commons-collections/download_collections.cgi?Preferred=http%3A%2F%2Fmirror.bit.edu.cn%2Fapache%2F
本文通过对Apache Commons Collections 项目中LRUMap这个集合类的源代码进行详细解读,为帮助大家更好的了解这个集合类的实现原理以及使用如何该集合类。
首先介绍一下LRU算法. LRU是由Least Recently Used的首字母组成,表示最近最少使用的含义,一般使用在对象淘汰算法上。也是比较常见的一种淘汰算法。
LRUMap 则是实现的LRP算法的Map集合类,它继承于AbstractLinkedMap 抽象类。LRUMap的使用说明如下:
LRUMap的初始化时需要指定最大集合元素个数,新增的元素个数大于允许的最大集合个数时,则会执行LRU淘汰算法。所有的元素在LRUMap中会根据最近使用情况进行排序。最近使用的会放在元素的最前面(LRUMap是通过链表来存储元素内容). 所以LRUMap进行淘汰时只需要删除链表最后一个即可(即header.after所指的元素对象)
那么那些操作会影响元素的使用情况:
1. put 当新增加一个集合元素对象,则表示该对象是最近被访问的
2. get 操作会把当前访问的元素对象作为最近被访问的,会被移到链接表头
注:当执行containsKey和containsValue操作时,不会影响元素的访问情况。
LRUMap也是非线程安全。在多线程下使用可通过 Collections.synchronizedMap(Map)操作来保证线程安全。
LRUMap的一个简单使用示例:
上面的示例,当增加”a3”值时,会淘汰最近最少使用的”a2”, 最后输出的结果为:
{a1=1, a3=3}
下面根据LRUMap的源码来解读一下LRUMap的实现原理
整体类图
LRUMap类的关键代码说明如下:
1. get操作
moveToMRU方法代码如下:
2. put新增操作
由于继承的AbstractLinkedMap,所以put操作会调用addMapping 方法,完整代码如下:
当集合的个数超过指定的最大个数时,会调用 reuseMapping函数,把要删除的对象的key和value更新为新加入的值,并再次加入到链接表中,并重新排定次序。
reuseMapping函数代码如下:
上面的代码中:
removeEntry 方法是删除最近最少使用的节点在链接中的引用
reuseEntry方法则把该节点的key和value赋新加入的节点的key和value值
addEntry 方法则把该节点加入到链接表,并保障相关的链接顺序
LRUMap的主要源码实现就解读到这里,实现思路还是比较好理解的。
LRUMap的使用场景会比较多,例如可以很方便的帮我们实现基于内存的 LRU 缓存服务实现。
jar包下载地址:
http://commons.apache.org/proper/commons-collections/download_collections.cgi?Preferred=http%3A%2F%2Fmirror.bit.edu.cn%2Fapache%2F
本文通过对Apache Commons Collections 项目中LRUMap这个集合类的源代码进行详细解读,为帮助大家更好的了解这个集合类的实现原理以及使用如何该集合类。
首先介绍一下LRU算法. LRU是由Least Recently Used的首字母组成,表示最近最少使用的含义,一般使用在对象淘汰算法上。也是比较常见的一种淘汰算法。
LRUMap 则是实现的LRP算法的Map集合类,它继承于AbstractLinkedMap 抽象类。LRUMap的使用说明如下:
LRUMap的初始化时需要指定最大集合元素个数,新增的元素个数大于允许的最大集合个数时,则会执行LRU淘汰算法。所有的元素在LRUMap中会根据最近使用情况进行排序。最近使用的会放在元素的最前面(LRUMap是通过链表来存储元素内容). 所以LRUMap进行淘汰时只需要删除链表最后一个即可(即header.after所指的元素对象)
那么那些操作会影响元素的使用情况:
1. put 当新增加一个集合元素对象,则表示该对象是最近被访问的
2. get 操作会把当前访问的元素对象作为最近被访问的,会被移到链接表头
注:当执行containsKey和containsValue操作时,不会影响元素的访问情况。
LRUMap也是非线程安全。在多线程下使用可通过 Collections.synchronizedMap(Map)操作来保证线程安全。
LRUMap的一个简单使用示例:
public static void main(String[] args) { LRUMap lruMap = new LRUMap(2); lruMap.put("a1", "1"); lruMap.put("a2", "2"); lruMap.get("a1");//mark as recent used lruMap.put("a3", "3"); System.out.println(lruMap); }
上面的示例,当增加”a3”值时,会淘汰最近最少使用的”a2”, 最后输出的结果为:
{a1=1, a3=3}
下面根据LRUMap的源码来解读一下LRUMap的实现原理
整体类图
LRUMap类的关键代码说明如下:
1. get操作
public Object get(Object key) { LinkEntry entry = (LinkEntry) getEntry(key); if (entry == null) { return null; } moveToMRU(entry); //执行LRU操作 return entry.getValue(); }
moveToMRU方法代码如下:
protected void moveToMRU(LinkEntry entry) { if (entry.after != header) { modCount++; // remove 从链接中移除当前节点 entry.before.after = entry.after; entry.after.before = entry.before; // add first 把节点增加到链接头部 entry.after = header; entry.before = header.before; header.before.after = entry; header.before = entry; } else if (entry == header) { throw new IllegalStateException("Can't move header to MRU" + " (please report this to commons-dev@jakarta.apache.org)"); } }
2. put新增操作
由于继承的AbstractLinkedMap,所以put操作会调用addMapping 方法,完整代码如下:
protected void addMapping(int hashIndex, int hashCode, Object key, Object value) { if (isFull()) { LinkEntry reuse = header.after; boolean removeLRUEntry = false; if (scanUntilRemovable) { while (reuse != header && reuse != null) { if (removeLRU(reuse)) { removeLRUEntry = true; break; } reuse = reuse.after; } if (reuse == null) { throw new IllegalStateException( "Entry.after=null, header.after" + header.after + " header.before" + header.before + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); } } else { removeLRUEntry = removeLRU(reuse); } if (removeLRUEntry) { if (reuse == null) { throw new IllegalStateException( "reuse=null, header.after=" + header.after + " header.before" + header.before + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); } reuseMapping(reuse, hashIndex, hashCode, key, value); } else { super.addMapping(hashIndex, hashCode, key, value); } } else { super.addMapping(hashIndex, hashCode, key, value); } }
当集合的个数超过指定的最大个数时,会调用 reuseMapping函数,把要删除的对象的key和value更新为新加入的值,并再次加入到链接表中,并重新排定次序。
reuseMapping函数代码如下:
protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) { // find the entry before the entry specified in the hash table // remember that the parameters (except the first) refer to the new entry, // not the old one try { int removeIndex = hashIndex(entry.hashCode, data.length); HashEntry[] tmp = data; // may protect against some sync issues HashEntry loop = tmp[removeIndex]; HashEntry previous = null; while (loop != entry && loop != null) { previous = loop; loop = loop.next; } if (loop == null) { throw new IllegalStateException( "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); } // reuse the entry modCount++; removeEntry(entry, removeIndex, previous); reuseEntry(entry, hashIndex, hashCode, key, value); addEntry(entry, hashIndex); } catch (NullPointerException ex) { throw new IllegalStateException( "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) + " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize + " Please check that your keys are immutable, and that you have used synchronization properly." + " If so, then please report this to commons-dev@jakarta.apache.org as a bug."); } }
上面的代码中:
removeEntry 方法是删除最近最少使用的节点在链接中的引用
reuseEntry方法则把该节点的key和value赋新加入的节点的key和value值
addEntry 方法则把该节点加入到链接表,并保障相关的链接顺序
/** * Adds an entry into this map, maintaining insertion order. * <p> * This implementation adds the entry to the data storage table and * to the end of the linked list. * * @param entry the entry to add * @param hashIndex the index into the data array to store at */ protected void addEntry(HashEntry entry, int hashIndex) { LinkEntry link = (LinkEntry) entry; link.after = header; link.before = header.before; header.before.after = link; header.before = link; data[hashIndex] = entry; }
LRUMap的主要源码实现就解读到这里,实现思路还是比较好理解的。
LRUMap的使用场景会比较多,例如可以很方便的帮我们实现基于内存的 LRU 缓存服务实现。
发表评论
-
Java WebService 简单实例
2016-07-07 22:03 403前言:朋友们开始以下教程前,请先看第五大点的注意事项,以避免 ... -
遗传算法使用Java实现
2015-12-10 10:03 734本文引自:http://luchi007.iteye ... -
Jeewx 微信插件开发框架,松耦合开发微信HTML5活动
2015-10-30 16:58 1061P3-Weixin (JAVA SAAS模式插件开发利器) ... -
java 二维数组如何存入数据库
2015-07-09 10:51 884using System; using System.Li ... -
一些好的RMI/corba文章选编
2014-05-28 18:23 5711 java中rmi和corba的区别 http://blog ... -
共享内存在Java中的实现和应用
2014-05-28 11:14 5021 共享内存对应应用开 ... -
Java利用Zxing生成二维码
2014-04-03 21:57 977Zxing是Google提供的关于条码(一维码、二维码)的解析 ... -
Eclipse Memory Analyzer简介
2014-01-14 17:29 969Eclipse Memory Analyzer是一 ... -
java正则表达式语法
2014-01-14 16:41 645java正则表达式语法 -
Java中的ArrayList的容量
2014-01-14 16:39 695List接口的大小可变数组的实现。实现了所有可选列表操作,并允 ...
相关推荐
LRU算法实现LRU算法实现LRU算法实现LRU算法实现LRU算法实现
(1) LRU:内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。 (2) LRU算法:LRU是Least Recently Used的...
这是自己在os课实验上自己写的一个页面替换算法cpp文件,里面包含了FIFO与LRU置换算法的实现程序。简单正确,同时加上了代码注释,一目了然。
LRU算法的java实现
近期最少使用算法
该资源是Java实现LRU算法的相关代码,将页面序号和进程分配的模块数,运行出具体的变化过程,真实可靠,可实现。
详细介绍了四种LRU算法,并有代码实现。
使用c语言是实现的LRU算法,带测试用例,供大家学习参考使用
操作系统中的一个算法 C++实现的,Lru算法
C语言写的lru算法,验证过了,可以用。大概还是不错的
计算机系统结构实验虚拟存储。用lru和fifo 实现页面置换,计算命中率
用C语言实现的OPT和LRU算法,下载后直接用VC++6.0打开即可编译运行。亲测可用。
基于python的LRU算法设计与实现
lru算法,供大家参考欢迎下载使用,并提出意见
用C语言的堆栈实现LRU算法,简单、易懂
LRU页面置换算法实现 一请求分页存储系统,进程P共有5页,访问串为3,2,1,0,3,2,4,3,2,1,0,4,试采用LRU算法和LFU算法分析,当分配页面数为3时,发生的缺页中断次数
1.资源包含LRU算法整个项目,可直接在vs2019上运行项目,如果版本不对可选择把项目中cpp文件复制到自己的vs中运行 2.LRU 算法的设计原则是:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也...
简单数组实现LRU算法
/**** 用于LRU入栈 *****/ void PUSH1(seqstack *s,datatype x,int nc_size){ // s->pop++; while(s->pop){ s->pop++; if(s->data[s->pop]==x){ for(int i=s->pop;i;i++){ s->data[i]=s->data[i+1]; } } } ...
使用LRU算法实现页面置换算法。LRU算法基于一种假设,长期不使用的数据,在未来的使用性也不大。因此,当数据占用内存达到一定的阙值时,我们要移除最近最少使用的数据。LRU算法中,使用了一种有趣的数据结构,叫做...