利用LinkedHashMap实现LRU

LRU：Least recently used, 最近最少使用，一般在设计缓存中间件时常用到该原则。
设计缓存时需要考虑以下几点：
1，为了快速获取缓存数据，考虑使用哈希表；
2，为了达到LRU的目的，需要保证数据有序，这又和哈希表产生冲突。
链表能达到有序的目的，但是检索慢；哈希表检索快，但是无序。
Java提供的LinkedHashMap恰好具备这两个特性，LinkedHashMap是HashMap的子类，在完全继承HashMap的哈希特性之外，还具有双向链表的数据结构，以保证数据的顺序。

图片来源于https://blog.csdn.net/justloveyou_/article/details/71713781

每个put进来的Entry既要放到哈希表中对应的位置，也要将其插入双向链表的尾部。所以LinkedHashMap中的Entry数据结构相比HashMap，除了hash、key、value、next属性之外，还有before、after属性用于维护LinkedHashMap的双向链表。

图片来源于https://blog.csdn.net/justloveyou_/article/details/71713781

accessOrder：LinkedHashMap中一个重要的成员变量，boolean类型，有相应的构造方法。true表示按照访问顺序迭代，false时表示按照插入顺序迭代。如果我们想要达到LRU的效果，在构造LinkedHashMap时，accessOrder就应该赋值true。

removeEldestEntry：LinkedHashMap中一个重要的方法，默认返回false，表示是否删除最旧的元素，如果要实现LUR，就要override该方法，告诉LinkedHashMap什么情况下删除旧元素，譬如，当整个LinkedHashMap的size达到设定的阈值，需要删除旧元素。

代码：

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);//accessOrder设置为true，表示按照访问顺序迭代
    this.cacheSize = cacheSize;
  }

  //覆盖方法，当LinkedHashMap的size达到缓存阈值时，删除旧元素
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() >= cacheSize;
  }
}