阿狗工具
146. LRU缓存机制（难度：中等）
题目描述：
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
算法分析：
由于题目要求时间复杂度为O(1)，所以我的需要的数据结构要符合下述几个条件：
（1）查询一个结点是否已经存在缓存区中
（2）缓存区溢出，需要将最早未访问的结点进行删除
（3）缓存区的某个结点被再次访问，需要将该节点标记为最新的结点。
（4）对缓存区中的结点进行排序或做标记，记录他们最新访问的顺序。
（5）在插入或者移动结点
在上述所有操作中，都要满足时间复杂度为O(1)。
问题一：解决记录结点顺序：双向链表
首先，分析需要记录缓存区中所有结点的最新访问顺序，有三种数据结构：
（1）数组，使用数组可以将缓存区中的结点按照访问顺序进行排序，但是，在访问了之前缓存区中的结点，需要将之前的结点进行移动到数组末尾，显然需要移动数组后面的所有结点，不符合O(1)的时间复杂度。因此不满足。
（2）单链表，使用链表可以将缓存区中的结点按照访问顺序进行排序，我们在写入数据时，若是新数据，则直接插入到链表末尾；若是缓存区中已经存在的结点，则将其指针进行移动，将该节点作为末尾结点，时间复杂度都是O(1)。但是在进行指针移动时，需要之间该节点的前置和后置结点，后置结点可以之间获取到，但是前置结点就需要遍历整个链表进行获取，因此，单链表也是不符合条件的。
（3）双向链表，上述分析，应该可以很轻易的想到双向链表，利用双向链表可以对前置结点进行记录。
问题二：解决判断新节点是否已经在缓存区
由于时间复杂度限制为O(1)，需要在一堆结点中一步判断出是否存在该节点，不用想，肯定是hash表。
因此，我们的数据结构定为：hash表 + 双向链表
解法一：利用JDK中的LinkedHashMap
在JDK中存在一种数据结构，叫做LinkedHashMap，他的底层结构就是HashMap + 双向链表，他是在HashMap的基础上，进行了扩展，可以通过两种方式进行排序：
- 按照插入顺序进行排序
- 按照读取的顺序进行排序（这道题我们想要的）
他的底层是通过一个双向链表来维持这种排序的，在每次插入、删除，都会调用函数进行=双向链表的维护。下面是LinkedHashMap中三个方法：
（1）void afterNodeAccess(Node<K,V> p) { }
其作用是在访问元素之后，将该元素放到双向链表的尾巴处，该方法只有在按照读取顺序排序才会执行。
（2）void afterNodeRemoval(Node<K,V> p) { }
其作用是在HashMap中删除元素之后，将元素从双向链表中删除。
（3）void afterNodeInsertion(boolean evict) { }
其作用是在新插入元素之后，判断是否需要移除最久未使用的结点（也就是双向链表中排在最前面的结点）。也是我们这道题中必须的方法。
LinkedHashMap中的构造函数：
/**
* 无参构造函数，默认accessOrder是false表示按照插入顺序排序
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity 表示map 的默认容量。
* @param loadFactor 表示加载因子 (默认即可)
* @param accessOrder 表示双向链表的排序方式，false：表示按照插入顺序进行排序；true：表示按照读取顺序进行排序。
*/
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap的三个关键方法：
/**
* 在新插入元素之后，判断是否需要移除最久未使用的结点（也就是双向链表中排在最前面的结点）。
* @param evict 是根据 HashMap 的 putVal 方法, evict 一直是 true
* removeEldestEntry表示移除规则，在LinkedHashMap中一直默认是false。
* 在LinkedHashMap中相当于什么都没做，因此需要重写removeEldestEntry方法。
*/
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
/**
* 该方法是移动结点到双向链表末尾
* @param e 表示当前操作的结点
* （1）使用 get 方法访问结点，会触发调用该方法
* （2）使用 put 方法插入结点，如果key存在，相当于访问结点，会触发该方法。
* （3）只有 accessOrder 为 true，打开按照最近最少访问排序，才能调用该方法
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
//last存放尾巴结点
LinkedHashMap.Entry<K,V> last;
//判断e结点不为尾巴结点
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//将p结点的后置结点为null
p.after = null;
//若p为头节点，则直接将p的后置结点设为头节点，否则将p前置结点的后置结点设为p的后置结点
if (b == null)
head = a;
else
b.after = a;
//若p不为尾巴结点，则p的后置结点的前置结点设为p的前置结点，否则，将p的前置结点直接设为尾巴结点
if (a != null)
a.before = b;
else
last = b;
//若last为null，表示链表为空，或者是p是头节点，则把p设为头节点，否则，将p插入链表尾结点后面。
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
//将p设为尾巴结点。
tail = p;
//将总数++
++modCount;
}
}
/**
* LinkedHashMap中的移除规则，默认返回的是false。
* 我们可以通过重新该方法来，进行我们的缓存策略，变为移除最近最少被访问的结点删除。
* 我们直接将返回结果改为 return size() > capacity;
* 其中capacity是缓存的大小。当当前的大小大于LinkedHashMap的大小，移除最近最少被访问的结点。
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
分析到这块，可以开始我们的算法编写了，哈哈哈，能看到这块，说明你已经离成功很近了！！！！
算法设计：
我们可以继承LinkedHashMap，重写removeEldestEntry方法，重新缓存机制。
import java.util.LinkedHashMap;
public class LRUCache extends LinkedHashMap<Integer, Integer> {
private Integer capacity = 0;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
/**
* 重新删除结点的条件
*/
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
return size()>this.capacity;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
解法二：手撕代码（HashMap + 双向链表）
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
//定义双向链表结点
class LinkedNode{
int key;
int value;
LinkedNode prev;
LinkedNode next;
public LinkedNode() {
// TODO Auto-generated constructor stub
}
public LinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
//定义hashmap
private Map<Integer, LinkedNode> cacheMap = new HashMap<>();
private int size;
private int maxSize;
private LinkedNode head,tail;
public LRUCache(int maxSize) {
this.size = 0;
this.maxSize = maxSize;
head = new LinkedNode();
tail = new LinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
LinkedNode node = cacheMap.get(key);
//如果该结点不存在
if(node == null) {
return -1;
}
//如果该结点存在，先通过hashmap查看在双向链表中的位置，然后在移动结点到头部
moveToHead(node);
return node.value;
}
public void put(int key,int value) {
LinkedNode node = cacheMap.get(key);
//如果key不存在
if(node == null) {
//创建一个新的结点
LinkedNode newNode = new LinkedNode(key,value);
//添加到哈希表
cacheMap.put(key, newNode);
//添加到双向链表的头部
addToHead(newNode);
this.size++;
//如果超出容量，删除双向链表的尾巴节点
if(size>this.maxSize) {
LinkedNode head = removeTail();
//删除hash表中的结点
cacheMap.remove(head.key);
this.size--;
}
}else {
//如果key存在，先通过hash定位，然后修改value，再将结点移动到双链表的尾巴结点。
node.value = value;
moveToHead(node);
}
}
//删除尾巴结点
private LinkedNode removeTail() {
LinkedNode node = tail.prev;
removeNode(node);
return node;
}
//删除结点
private void removeNode(LinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
//移动结点到头节点
private void addToHead(LinkedNode newNode) {
newNode.prev = head;
newNode.next = head.next;
head.next.prev = newNode;
head.next = newNode;
}
//移动结点到头节点
private void moveToHead(LinkedNode node) {
removeNode(node);
addToHead(node);
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/