LRU

LRU（Least recently used，最近最少使用）是溢出淘汰中最近常被人提起或使用的算法，算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。LRU的使用比较广泛，只要是涉及到缓存数据存储长度的溢出淘汰，都可以看到LRU算法的实现。在很多成熟的框架中也有它的身影，如MyBatis的LruCache，或是SpringMVC中d的AbstractCachingViewResolver等等等等。但是在上述我提到的这两个框架的LRU算法的实现中，都一致的采用了LinkedHashMap。而且实现手法上几乎一致，确实也比较精妙，故在此做个记录。
先来看看MyBatis的LruCache的实现：

public void setSize(final int size) {
    keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) {
      private static final long serialVersionUID = 4267176411845948333L;
      @Override
      protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
        boolean tooBig = size() > size;
        if (tooBig) {
          eldestKey = eldest.getKey();
        }
        // 返回true或false告诉 LinkedHashMap要不要删除此最老键值
        return tooBig;
      }
    };
  }

下面时SpringMVC中的实现：

	/** Fast access cache for Views, returning already cached instances without a global lock. */
	private final Map<Object, View> viewAccessCache = new ConcurrentHashMap<>(DEFAULT_CACHE_LIMIT);

	/** Map from view key to View instance, synchronized for View creation. */
	@SuppressWarnings("serial")
	private final Map<Object, View> viewCreationCache =
			new LinkedHashMap<Object, View>(DEFAULT_CACHE_LIMIT, 0.75f, true) {
				@Override
				protected boolean removeEldestEntry(Map.Entry<Object, View> eldest) {
					if (size() > getCacheLimit()) {
						viewAccessCache.remove(eldest.getKey());
						return true;
					}
					else {
						return false;
					}
				}
			};

其实这两段代码都非常的简单，LinkedHashMap内部其实就是每次访问或者插入一个元素都会把元素放到链表末尾，再通过覆盖 LinkedHashMap的removeEldestEntry方法，从而使用最不经常使用数据排在了链表头。当长度超过限制时，移除链表头的数据，来实现LRU。