Java实现LRU缓存的实例详解

Java实现LRU缓存的实例详解

1.Cache

Cache对于代码系统的加速与优化具有极大的作用，对于码农来说是一个很熟悉的概念。可以说，你在内存中new 了一个一段空间（比方说数组，list）存放一些冗余的结果数据，并利用这些数据完成了以空间换时间的优化目的，你就已经使用了cache。

有服务级的缓存框架，如memcache，Redis等。其实，很多时候，我们在自己同一个服务内，或者单个进程内也需要缓存，例如，lucene就对搜索做了缓存，而无须依赖外界。那么，我们如何实现我们自己的缓存？还要带自动失效的，最好还是LRU（Least Recently Used）。

当你思考怎么去实现，你可能会想得很远。为了LRU，需要把刚使用的数据存入栈，或者纪录每个数据最近使用的时间，再来的定时扫描失效的线程….其实，Java本身就已经为我们提供了LRU Cache很好的实现，即LinkedHashMap。

2.LinkedHashMap分析

很多没有去细究过其内部实现的人，只是将其当作一个普通的hashMap来对待。LinkedHashMap是一个双向链表，加上HashTable的实现。表现出来与普通HashMap的一个区别就是LinkedHashMap会记录存入其中的数据的顺序，并能按顺取出。
为了实现，一个hash表，自然应该先申请在一片连续的内存空间上。当需要存入数据的时候，根据相应的hash值存入。而LinkedHashMap在这个基础上，为每个entry设置了before与after属性，形了一个双向链表，记录了他们put进入的前后顺序。

不仅如此，每当通过get来获得某个元素后，get方法内部，会在最后通过afternodeAccess方法来调整链表的指向:

void afterNodeAccess(Node<K,V> e) { // move node to last  LinkedHashMap.Entry<K,V> last;  if (accessOrder && (last = tail) != e) {    LinkedHashMap.Entry<K,V> p =      (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;    p.after = null;    if (b == null)      head = a;    else      b.after = a;    if (a != null)      a.before = b;    else      last = b;    if (last == null)      head = p;    else {      p.before = last;      last.after = p;    }    tail = p;    ++modCount;  }}