使用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