使用LinkedHashMap实现LRU缓存

可能很多人已经知道了这个技术,但是对于我来说,虽然使用Java十余年了,最近才了解到LinkedHashMap这个类。使用这个类可以方便的实现一个本地的LRU Cache类。

之所以没有关注到这个类,是因为在面对本地缓存的case时,我经常会考虑guava这个框架。
最早可以搜到的一篇关于LinkedHashMap实现本地缓存的文章之一是这篇: How to set up a simple LRU cache using LinkedHashMap ,发表于2005年。文末有附了几篇关于LinkedHashMap类的介绍。

这个类实现了Hash和双向链表两种数据结构的混合。 所以通过get方法可以很快的得到相应的元素,而链表结构又可以根据access或者insert进行排序。但是这种
方式也会有性能的损耗,因为对数据的插入需要同时更新这两个数据结构,对数据的访问在accessOrder情况下也会涉及数据的移动。 我们知道数据量大的情况下对链表的更改是很耗时的,所以使用的时候要仔细考量。

好了,下面就是一个local cache的实现,抄自 A LRU Cache in 10 Lines of Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.LinkedHashMap;
import java.util.Map;
public LRUCache<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRUCache(int cacheSize) {
super(16, 0.75, true);
this.cacheSize = cacheSize;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() >= cacheSize;
}
}

主要实现removeEldestEntry方法,这个方法如果返回true,则会移除最老的数据。这只会在调用put或者putAll时发生。

很重要的一点, 此类不是线程安全的,所以使用的时候你需要加锁。

参考文档

  1. A LRU Cache in 10 Lines of Java
  2. How to set up a simple LRU cache using LinkedHashMap
  3. LinkedHashMap as LRU cache
  4. https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html