引子：
我们平时总会有一个电话本记录所有朋友的电话，但是，如果有朋友经常联系，那些朋友的电话号码不用翻电话本我们也能记住，但是，如果长时间没有联系了，要再次联系那位朋友的时候，我们又不得不求助电话本，但是，通过电话本查找还是很费时间的。但是，我们大脑能够记住的东西是一定的，我们只能记住自己最熟悉的，而长时间不熟悉的自然就忘记了。
其实，计算机也用到了同样的一个概念，我们用缓存来存放以前读取的数据，而不是直接丢掉，这样，再次读取的时候，可以直接在缓存里面取，而不用再重新查找一遍，这样系统的反应能力会有很大提高。但是，当我们读取的个数特别大的时候，我们不可能把所有已经读取的数据都放在缓存里，毕竟内存大小是一定的，我们一般把最近常读取的放在缓存里（相当于我们把最近联系的朋友的姓名和电话放在大脑里一样）。现在，我们就来研究这样一种缓存机制。
LRU Cache：
LRU缓存利用了这样的一种思想。LRU是Least Recently Used 的缩写，翻译过来就是“最不常使用”，也就是说，LRU缓存把最不常使用的数据移除，让给最新读取的数据。大多数情况下，最常读取的，也是读取次数最多的，所以，利用LRU缓存，我们能够提高系统的performance. LRU cache是非常频繁出现的一道面试题，一般来讲，当我们问到这道题时，面试官往往想得到的答案是利用 doubly linked list + hashtable 实现 LRU Cache, 那么我们现在就来讲一讲如何利用doubly linked list + hashtable实现LRU Cache的。
对于LRU cache，往往会有以下要求：
1. 假设Cache里面的 entry 都是按照序列保存的，那么，对于新的entry，我们把它放置在最前面。
2. 如果一个entry已经存在，我们再次访问到该entry的时候，我们需要把它放在cache的最前面。
3. 当cache满了的时候，需要把最后一个entry 从cache里面移除出去，然后再往里插入 entry。
4. 以上所有的操作复杂度必须为 O(1).
对于操作复杂度，一旦看到要求为O(1)， 一般我们都会立刻想到 hashtable, 所以，为了实现“顺序”的要求，我们需要有一个链表来连接所有的entry. 所以，在实现时，我们将Cache的所有 entry 都用doubly linked list 连接起来，当一个 entry 被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。
我们首先定义entry, 每一个entry包括键（key）和 值 （value），而且，每一个 entry 都带有两个指针分别指向它们的前一个和后一个 entry.
1 package Cache;2 3 public class Entry4 {5 Entry prev;6 Entry next;7 Object value;8 Object key;9 } 再定义一个统一的接口：
1 package Cache; 2 3 public interface MyCache 4 { 5 public void addElement(Object key, Object value); 6 public Object getElement(Object key); 7 public boolean isExist(Object key); 8 public int size(); 9 public int capacity();10 public void clear();11 } 在Hashtable里，我们需要保存该Entry, 这个时候，我们用Entry的键作为Hashtable 里的键，而Hashtable的值呢就是Entry。
1 package Cache; 2 3 import java.util.*; 4 5 public class MyLRUCache implements MyCache 6 { 7 private int cacheSize; 8 private Hashtable nodes; 9 private int currentSize; 10 private Entry first; 11 private Entry last; 12 13 public MyLRUCache(int i) 14 { 15 currentSize = 0; 16 cacheSize = i; 17 nodes = new Hashtable (i); 18 } 19 20 @Override 21 public synchronized void addElement(Object key, Object value) 22 { 23 Entry node = nodes.get(key); 24 if (node == null) 25 { 26 if (currentSize >= cacheSize) 27 { 28 nodes.remove(last.key); 29 removeLast(); 30 } else 31 currentSize++; 32 node = new Entry(); 33 } 34 node.value = value; 35 moveToHead(node); 36 nodes.put(key, node); 37 } 38 39 private synchronized void moveToHead(Entry node) 40 { 41 if (node == first) 42 return; 43 if (node.prev != null) 44 node.prev.next = node.next; 45 if (node.next != null) 46 node.next.prev = node.prev; 47 if (last == node) 48 last = node.prev; 49 if (first != null) 50 { 51 node.next = first; 52 first.prev = node; 53 } 54 first = node; 55 node.prev = null; 56 if (last == null) 57 last = first; 58 59 } 60 61 private synchronized void removeLast() 62 { 63 if (last != null) 64 { 65 if (last.prev != null) 66 last.prev.next = null; 67 else 68 first = null; 69 last = last.prev; 70 } 71 } 72 73 @Override 74 public synchronized Entry getElement(Object key) 75 { 76 Entry node = nodes.get(key); 77 if (node != null) 78 { 79 moveToHead(node); 80 return node; 81 } else 82 return null; 83 } 84 85 @Override 86 public boolean isExist(Object key) 87 { 88 Entry node = nodes.get(key); 89 if (node != null) 90 return true; 91 return false; 92 } 93 94 @Override 95 public int size() 96 { 97 return currentSize; 98 } 99 100 @Override101 public int capacity()102 {103 return cacheSize;104 }105 106 @Override107 public void clear()108 {109 first = null;110 last = null;111 currentSize = 0;112 113 }114 115 }