LRU
LRU（Least Recently Used），近期最少使用算法， 常应用于缓存中的数据淘汰， 其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高“。
实现
基于数组实现
仔细看下这个算法的定义： 近期最少使用算法，其实就是按照”近期最少使用”这个条件去淘汰相应的数据。
既然是淘汰最近最少使用的数据，姑且就可以理解为，当内存满了的那个时刻，内存中，最后一次被访问数据，应该被移除。
假如每条数据有一个属性lasttime，用来记录被访问时刻的时间，这样，每一条数据都有一个最后访问时间， 当内存满的时候，遍历所有元素，删除最后访问时间最小的那个元素：
lasttime = current_time()
lastKey = null;
if list full:
foreach each item of list:
if item.lasttime < lasttime:
lasttime = item.lasttime
lastKey = item.key
然后把lastKey指向的那条数据删除。
性能分析
这个算法是可行的。但是，当内存满时，删除最近最长时间未被使用元素的平均时间复杂度为 O(n)，因为，我们需要先找到 lasttime 为最小的数据元素，将其删除，再将这个数据元素之后的元素向前移动一格。
试想一下，假如有一千万条数据，每次删除都需要找出访问时间最早的那些数据，这是很耗资源的操作， 时间复杂度是O(N)，跟数据量成正比，数据量越大，性能越低。
不仅如此，查找一个数据元素的时间复杂度也是O(N)。
基于双向链表的实现
基于以上不足，我们可以通过使用链表来实现，这样，当缓存中数据元素的个数，超过阈值时，“删除最近最久未使用元素”操作的时间复杂度仅为 O(1)：
- 每次写入数据时，将数据放入链表头结点，时间复杂度为 O(1)。
- 使用缓存中数据时，将数据移动到头结点，时间复杂度为 O(n)。
- 缓存数量超过阈值时，移除链表尾部数据，时间复杂度为 O(1)。
这个算法同样是可行的。但是，问题在于“使用缓存中数据时，将数据移动到头结点”操作的时间复杂度为 O(n)。
基于双向链表 + Hashmap 的实现
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部。具体的方法如下：
- 对于 get 操作，首先判断 key 是否存在：
- 如果 key 不存在，则返回 −1；
- 如果 key 存在，通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
- 对于 put 操作，首先判断 key 是否存在：
- 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
- 如果 key 不存在，
- 判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。
在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
复杂度分析
时间复杂度：对于 put 和 get 都是 O(1)。
空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。
# hashmap + double linked list
# - time: O(1) for each put() and get()
# - space: O(n)
class Node(object):
def __init__(self, key, value):
# key 需要存储在 node 里，否则当 capacity 满时，从 LRUCache. left 读出 lru node 后，无法得知 key，因而无法从 hashmap 中把该 node 删除
self.key, self.value = key, value
self.left, self.right = None, None
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.m = {}
# front=most recent used, rear=LRU
self.left = Node(-1, -1)
self.right = Node(-2, -2)
self.left.right, self.right.left = self.right, self.left
# remove node from linked list
def remove(self, node):
node.left.right = node.right
node.right.left = node.left
# insert node at left
def insertToStart(self, node):
# 先更新 node 的指针
node.left = self.left
node.right = self.left.right
node.right.left = node
self.left.right = node
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.m:
return -1
node = self.m[key]
# update linked list
self.remove(node)
self.insertToStart(node)
return node.value
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self.m:
self.m[key].value = value
node = self.m[key]
# update linked list
self.remove(node)
self.insertToStart(node)
return
if len(self.m) == self.capacity:
# remove the least frequently used node
node = self.right.left
self.remove(node)
del self.m[node.key]
node = Node(key, value)
self.m[key] = node
self.insertToStart(node)