146. LRU缓存机制（难度：中等）
标题链接：https://leetcode-cn.com/problems/lru-cache/
标题描述：
运用你所把握的数据结构，计划和实现一个 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); // 返回 1cache.put(3, 3); // 该使用会使得关键字 2 取消cache.get(2); // 返回 -1 (未找到)cache.put(4, 4); // 该使用会使得关键字 1 取消cache.get(1); // 返回 -1 (未找到)cache.get(3); // 返回 3cache.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中的构造函数： |
