zhuyonge 2016-01-02
在项目中用到了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操作时会执行以下几步:
LRUMap是非线程安全的,如果需要线程安全可以使用Collections.synchronizeMap()获取一个线程安全的Map
或者使用goole提供的一个ConcurrentLinkedHashMap,一个基于ConcurrentHashMap实现的LRU算法,性能跟ConcurrentHashMap相差无几,源代码地址:https://github.com/ben-manes/concurrentlinkedhashmap
相关链接: