Java实现简单的LRU缓存

应用程序经常需要在内存里缓存一些数据。Java里最常用的类是HashMap和Hashtable 。如果需要做一些更复杂的缓存，你可以使用JBoss Cache, OSCache或者EHCache。即使是使用其他的缓存系统，你可能仍然想要在本地用对象缓存一些数据，以便快速访问。在做这些缓存的时候经常会遇到一个令人讨厌的问题，就是要很小心的控制缓存大小以防止其占用过多内存的，如果缓存不停的增长就会影响程序的性能。

一个简单的解决方法就是给内存缓存设置一个最大的限制，采用LRU（最近最少使用）替换算法进行替换。这种方法可以对内存使用有个预期并且只在缓存里存储最近的使用过的数据。

自从JDK1.4，一种新的集合类LinkedHashMap被引入进来。LinkedHashMap有很多优点：

l 它能维持数据项的顺序。一个专门的构造函数（LinkedHashMap(Map<? extends K,? extends V> m) )可以实现遍历的顺序和插入的顺序可以保持一致。这个场景下用TreeMap就比较贵了。

l 它还有个removeEldestEntry(Map.Entry)方法，可以重写这个方法来表明替换的策略，这就是我们用来创建LRU缓存的主要方法。

Ok，下面是一段使用LinkedHashMap实现的LRU缓存：

import java.util.*;

public class SimpleLRU {

  private static final int MAX_ENTRIES = 50;

  private Map mCache = new LinkedHashMap(MAX_ENTRIES, .75F, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
      return size() > MAX_ENTRIES;
    }
  };

  public SimpleLRU() {
    for(int i = 0; i < 100; i++) {
      String numberStr = String.valueOf(i);
      mCache.put(numberStr, numberStr);

      System.out.print("\rSize = " + mCache.size() + "\tCurrent value = " + i + "\tLast Value in cache = " + mCache.get(numberStr));
      try {
        Thread.sleep(10);
      } catch(InterruptedException ex) {
      }
    }

    System.out.println("");
  }

  public static void main(String[] args) {
    new SimpleLRU();
  }
}

这段代码创建了一个包含50个长度的简单的LRU缓存的实现。代码最神奇的部分就是在创建LinkedHashMap时，使用了true参数来表示维持访问顺序，并且重写了removeEldestEntry方法。运行程序，就可以看到cache size不断增加直到50，就不再增加，而开始替换最近最少使用的值。最后显示如下：

Size = 50       Current value = 99      Last Value in cache = 99