LRU(Least recently used,最近最少使用)是溢出淘汰中最近常被人提起或使用的算法,算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。LRU的使用比较广泛,只要是涉及到缓存数据存储长度的溢出淘汰,都可以看到LRU算法的实现。在很多成熟的框架中也有它的身影,如MyBatis的LruCache,或是SpringMVC中d的AbstractCachingViewResolver等等等等。但是在上述我提到的这两个框架的LRU算法的实现中,都一致的采用了LinkedHashMap。而且实现手法上几乎一致,确实也比较精妙,故在此做个记录。
先来看看MyBatis的LruCache的实现:
public void setSize(final int size) {
keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
private static final long serialVersionUID = 4267176411845948333L;
@Override
protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
boolean tooBig = size() > size;
if (tooBig) {
eldestKey = eldest.getKey();
}
// 返回true或false告诉 LinkedHashMap要不要删除此最老键值
return tooBig;
}
};
}
下面时SpringMVC中的实现:
/** Fast access cache for Views, returning already cached instances without a global lock. */
private final Map<Object, View> viewAccessCache = new ConcurrentHashMap<>(DEFAULT_CACHE_LIMIT);
/** Map from view key to View instance, synchronized for View creation. */
@SuppressWarnings("serial")
private final Map<Object, View> viewCreationCache =
new LinkedHashMap<Object, View>(DEFAULT_CACHE_LIMIT, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Object, View> eldest) {
if (size() > getCacheLimit()) {
viewAccessCache.remove(eldest.getKey());
return true;
}
else {
return false;
}
}
};
其实这两段代码都非常的简单,LinkedHashMap内部其实就是每次访问或者插入一个元素都会把元素放到链表末尾,再通过覆盖 LinkedHashMap的removeEldestEntry方法,从而使用最不经常使用数据排在了链表头。当长度超过限制时,移除链表头的数据,来实现LRU。