实现思路和上文提到的一致，说下重点：
- 数据是直接利用 HashMap 来存放的。
- 内部使用了一个双向链表来存放数据，所以有一个头结点 header，以及尾结点 tailer。
- 每次写入头结点，删除尾结点时都是依赖于 header tailer，如果看着比较懵建议自己实现一个链表熟悉下，或结合下文的对象关系图一起理解。
- 使用数据移动到链表头时，第一步是需要在双向链表中找到该节点。这里就体现出链表的问题了。查找效率很低，最差需要
O(N)。之后依赖于当前节点进行移动。
- 在写入头结点时有判断链表大小等于 2 时需要删除初始化的头尾结点。这是因为初始化时候生成了两个双向节点，没有数据只是为了形成一个数据结构。当真实数据进来之后需要删除以方便后续的操作（这点可以继续优化）。
- 以上的所有操作都是线程不安全的，需要使用者自行控制。
下面是对象关系图：
初始化时
写入数据时
LRUMap<String,Integer> lruMap = new LRUMap(3) ; lruMap.put("1",1) ;
lruMap.put("2",2) ;
lruMap.put("3",3) ;
lruMap.put("4",4) ;
获取数据时
数据和上文一样：
Integer integer = lruMap.get("2");
通过以上几张图应该是很好理解数据是如何存放的了。
实现三
其实如果对 Java 的集合比较熟悉的话，会发现上文的结构和 LinkedHashMap 非常类似。
对此不太熟悉的朋友可以先了解下 LinkedHashMap 底层分析 。
所以我们完全可以借助于它来实现：
public class LRULinkedMap<K,V> { /** * 最大缓存大小 */ private int cacheSize; private LinkedHashMap<K,V> cacheMap ; public LRULinkedMap(int cacheSize) { this.cacheSize = cacheSize; cacheMap = new LinkedHashMap(16,0.75F,true){ @Override protected boolean removeEldestEntry(Map.Entry eldest) { if (cacheSize + 1 == cacheMap.size()){ return true ; }else { return false ; } } }; } public void put(K key,V value){ cacheMap.put(key,value) ; } public V get(K key){ return cacheMap.get(key) ; } public Collection<Map.Entry<K, V>> getAll() { return new ArrayList<Map.Entry<K, V>>(cacheMap.entrySet()); } }
这次就比较简洁了，也就几行代码（具体的逻辑 LinkedHashMap 已经帮我们实现好了）
实际效果:
@Test public void put() throws Exception { LRULinkedMap<String,Integer> map = new LRULinkedMap(3) ; map.put("1",1); map.put("2",2); map.put("3",3); for (Map.Entry<String, Integer> e : map.getAll()){ System.out.print(e.getKey() + " : " + e.getValue() + "\t"); } System.out.println(""); map.put("4",4); for (Map.Entry<String, Integer> e : map.getAll()){ System.out.print(e.getKey() + " : " + e.getValue() + "\t"); } } //输出 1 : 1 2 : 2 3 : 3 2 : 2 3 : 3 4 : 4
使用时：
@Test public void get() throws Exception { LRULinkedMap<String,Integer> map = new LRULinkedMap(4) ; map.put("1",1); map.put("2",2); map.put("3",3); map.put("4",4); for (Map.Entry<String, Integer> e : map.getAll()){ System.out.print(e.getKey() + " : " + e.getValue() + "\t"); } System.out.println(""); map.get("1") ; for (Map.Entry<String, Integer> e : map.getAll()){ System.out.print(e.getKey() + " : " + e.getValue() + "\t"); } } } //输出 1 : 1 2 : 2 3 : 3 4 : 4 2 : 2 3 : 3 4 : 4 1 : 1
LinkedHashMap 内部也有维护一个双向队列，在初始化时也会给定一个缓存大小的阈值。初始化时自定义是否需要删除最近不常使用的数据，如果是则会按照实现二中的方式管理数据。
其实主要代码就是重写了 LinkedHashMap 的 removeEldestEntry 方法:
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
它默认是返回 false，也就是不会管有没有超过阈值。
所以我们自定义大于了阈值时返回 true，这样 LinkedHashMap 就会帮我们删除最近最少使用的数据。
总结
以上就是对 LRU 缓存的实现，了解了这些至少在平时使用时可以知其所以然。
当然业界使用较多的还有 guava 的实现，并且它还支持多种过期策略。
