LRU 算法：
LRU 算法原理：
LRU（Least Recently Used），这种算法认为最近使用的数据是热点数据，下一次有很大概率会再次使用这个数据。而最近很少被使用的数据，很大概率下一次不会使用。所以当缓存容量满时，优先淘汰掉最近最少使用的数据。
LRU 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。
假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。
总结一下LRU算法具体实现步骤：
- 新数据插入时，直接插入到列表的头部
- 缓存数据命中时，将命中的数据移动到列表头部
- 缓存满时，移除列表尾部的数据。
LRU 算法实现：
使用双向链表加散列表（HashMap）结构，就能很好的保证了查询效率在O(1)的时间复杂度。
整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。
下面展示了，预设大小是 3 的，LRU存储的在存储和访问过程中的变化。为了简化图复杂度，图中没有展示 HashMap部分的变化，仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下：
save(“key1”, 7) save(“key2”, 0) save(“key3”, 1) save(“key4”, 2) get(“key2”) save(“key5”, 3) get(“key2”) save(“key6”, 4)
相应的 LRU 双向链表部分变化如下：
总结一下核心操作的步骤：
save(key, value)：首先在HashMap找到Key对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过tail淘汰掉队尾的节点，同时在HashMap中移除Key。get(key)：通过HashMap找到LRU链表节点，把节点插入到队头，返回缓存的值。
首先需要定义节点Node类：
class DLinkedNode { int key; int value; DLinkedNode pre; DLinkedNode post; }
在LRUCache内部为了一个索引Map，目的是为了put和get时都能实现O(1)的时间复杂度：
private HashMap<Integer, DLinkedNode> cache = new HashMap<>();
内部维护了一个DLinkedNode双向链表，用于记录访问的时间先后：
// DLinkedNode个数： private int count; // 缓存容量： private int capacity; private DLinkedNode head; private DLinkedNode tail;
两个核心的方法get和put。
完整代码实现：
public class LRUCache { private HashMap<Integer, DLinkedNode> cache = new HashMap<>(); private int count; private int capacity; private DLinkedNode head; private DLinkedNode tail; public LRUCache(int capacity) { this.count = 0; this.capacity = capacity; head = new DLinkedNode(); head.pre = null; tail = new DLinkedNode(); tail.post = null; head.post = tail; tail.pre = head; } public int get(String key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; // should raise exception here. } // move the accessed node to the head; this.moveToHead(node); return node.value; } public void set(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { DLinkedNode newNode = new DLinkedNode(); newNode.key = key; newNode.value = value; this.cache.put(key, newNode); this.addNode(newNode); ++count; if (count > capacity) { // pop the tail DLinkedNode tail = this.popTail(); this.cache.remove(tail.key); --count; } } else { // update the value. node.value = value; this.moveToHead(node); } } /** * Always add the new node right after head; */ private void addNode(DLinkedNode node) { node.pre = head; node.post = head.post; head.post.pre = node; head.post = node; } /** * Remove an existing node from the linked list. */ private void removeNode(DLinkedNode node) { DLinkedNode pre = node.pre; DLinkedNode post = node.post; pre.post = post; post.pre = pre; } /** * Move certain node in between to the head. */ private void moveToHead(DLinkedNode node) { this.removeNode(node); this.addNode(node); } // pop the current tail. private DLinkedNode popTail() { DLinkedNode res = tail.pre; this.removeNode(res); return res; } }
