问题：
# 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
#
#
#
# 实现 LRUCache 类：
#
#
# LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
# int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
# void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上
# 限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
#
题解：
#### 方法一：哈希表 + 双向链表
**算法**
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 *O(1)* 的时间内完成 `get` 或者 `put` 操作。具体的方法如下：
- 对于 `get` 操作，首先判断 `key` 是否存在：
- 如果 `key` 不存在，则返回 *-1*；
- 如果 `key` 存在，则 `key` 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
- 对于 `put` 操作，首先判断 `key` 是否存在：
- 如果 `key` 不存在，使用 `key` 和 `value` 创建一个新的节点，在双向链表的头部添加该节点，并将 `key` 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 如果 `key` 存在，则与 `get` 操作类似，先通过哈希表定位，再将对应的节点的值更新为 `value`，并将该节点移到双向链表的头部。
上述各项操作中，访问哈希表的时间复杂度为 *O(1)*，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 *O(1)*。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 *O(1)* 时间内完成。
参考代码：
# leetcode submit region begin(Prohibit modification and deletion) class DLinkedNode: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.cache = {} self.head = DLinkedNode() self.tail = DLinkedNode() self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.size = 0 def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self.moveToHead(node) return node.value def put(self, key: int, value: int) -> None: if key not in self.cache: node = DLinkedNode(key, value) self.cache[key ] = node self.addToHead(node) self.size += 1 if self.size > self.capacity: removed = self.removeTail() self.cache.pop(removed.key) # 删除hash表中的对应项 self.size -= 1 else: node = self.cache[key] node.value = value self.moveToHead(node) def addToHead(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def removeNode(self, node): node.prev.next = node.next node.next.prev = node.prev def moveToHead(self, node): self.removeNode(node) self.addToHead(node) def removeTail(self): node = self.tail.prev self.removeNode(node) return node