LRU缓存
LRU缓存是一种常见的缓存筛选算法，LRU的全称是Least Recently Used，即最近最少运用。在LRU缓存中，当缓存空间已满时，会根据缓存数据的拜访时刻（即最近一次被拜访的时刻）筛选最近最少运用的缓存数据。
一种常见的完成方式是运用哈希表和双向链表。哈希表用于快速查找缓存数据，而双向链表用于保护缓存数据的拜访时刻次序。详细完成过程如下：
-
初始化一个哈希表和一个双向链表。
-
当有新的缓存数据需求被增加到缓存中时，先在哈希表中查找该缓存数据是否已存在：
- 假如存在，将该缓存数据移动到链表头部，并更新哈希表中该缓存数据的方位；
- 假如不存在，将该缓存数据增加到链表头部，并在哈希表中增加该缓存数据的方位。假如此时缓存已满，删去链表尾部的数据，并从哈希表中删去该缓存数据的方位。
-
当需求拜访缓存数据时，先在哈希表中查找该缓存数据是否存在：
- 假如不存在，回来-1；
- 假如存在，将该缓存数据移动到链表头部，并更新哈希表中该缓存数据的方位。
-
当缓存数据被拜访后，需求更新该缓存数据的拜访时刻，即将该缓存数据移动到链表头部。
时刻复杂度： 增加缓存数据、拜访缓存数据的时刻复杂度均为 O(1)。
空间复杂度： 最坏情况下需求存储一切缓存数据，空间复杂度为 O(capacity)，其间 capacity 为缓存容量。
OrderedDict
道理我都讲了，假如你愿意，你可以用双向链表自己完成一个，假如你不愿意，你可以直接用python的OrderedDict。
OrderedDict是Python的标准库collections中的一个类，它是一个有序字典，具有一般字典的一切功用，并坚持字典键的刺进次序。OrderedDict中的键值对是依照刺进次序来排序的。
OrderedDict与一般字典的差异在于，OrderedDict中的元素会依照刺进次序进行排序，而不是依照键的哈希值。OrderedDict的功用基本上与字典相同，但是有几个额定的办法和参数，使得OrderedDict比字典更加灵活和有用。
常用的OrderedDict办法：
-
OrderedDict.popitem(last=True)： 回来并删去字典中的一个键值对。假如last为True，则删去最终一个刺进的键值对，不然删去第一个刺进的键值对。
-
OrderedDict.move_to_end(key, last=True)： 将指定的键移到字典的最初或结尾。假如last为True，则将键移到结尾，不然将键移到最初。
-
OrderedDict.clear()： 删去OrderedDict中的一切元素。
-
OrderedDict.copy()： 回来一个OrderedDict的浅复制。
-
OrderedDict.fromkeys(seq[, value])： 创立一个新的OrderedDict，其间包括seq中一切元素作为键，一切键的值都设置为value（默以为None）。
-
OrderedDict.items()： 回来一个包括OrderedDict一切键值对的元组列表。
-
OrderedDict.keys()： 回来一个包括OrderedDict一切键的列表。
-
OrderedDict.values()： 回来一个包括OrderedDict一切值的列表。
試一下：LRU 缓存
请你规划并完成一个满足LRU (最近最少运用) 缓存束缚的数据结构。
完成LRUCache类：
-
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存 -
int get(int key)假如关键字key存在于缓存中，则回来关键字的值，不然回来-1。 -
void put(int key, int value)假如关键字key已经存在，则变更其数据值value；假如不存在，则向缓存中刺进该组key-value。假如刺进操作导致关键字数量超越capacity，则应该逐出最久未运用的关键字。
函数get和put必须以O(1)的均匀时刻复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解说
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 回来 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 报废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 回来 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 报废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 回来 -1 (未找到)
lRUCache.get(3); // 回来 3
lRUCache.get(4); // 回来 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key in self.cache:
self.cache.move_to_end(key, last=True)
return self.cache[key]
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key, last=True)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
该代码完成了一个LRU缓存的数据结构，运用了Python中的OrderedDict类。
在初始化时，运用capacity参数来确认缓存的容量，并创立一个空的OrderedDict目标作为缓存。
在get办法中，假如给定的key在缓存中，则将其移动到OrderedDict的结尾（最近运用的方位），并回来该key对应的value值。不然，回来-1表明缓存中没有该key。
在put办法中，假如给定的key已经在缓存中，则将其移动到OrderedDict的结尾（最近运用的方位），并将其对应的value更新为给定的value。不然，在缓存中增加新的key-value对，并将其放置在OrderedDict的结尾（表明最近运用）。假如增加新的key-value对后，缓存巨细超越了容量限制，就从OrderedDict的最初（最旧的方位）删去一个key-value对，以保持缓存的容量不超越设定的值。
整个LRU缓存的完成通过OrderedDict类完成，运用了move_to_end()和popitem()办法，以及OrderedDict的默认行为（即依照增加次序保护key-value对的次序）来保护缓存中key-value对的次序。时刻复杂度为O(1)，与OrderedDict类完成的算法时刻复杂度一致。
