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

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 时发生。

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