相关题目
146. LRU 缓存
要让 put 和 get ⽅法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：
1、显然 cache 中的元素必须有时序，以区分最近使⽤的和久未使⽤的数据，当容量满了之后要删除最久未使⽤的那个元素腾位置。
2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val。
3、每次访问 cache 中的某个 key，需要将这个元素变为最近使⽤的，也就是说 cache 要⽀持在任意位置快速插⼊和删除元素。
哈希表查找快，但是数据⽆固定顺序；链表有顺序之分，插⼊删除快，但是查找慢，所以结合⼆者的⻓处，可以形成⼀种新的数据结构：哈希链表 LinkedHashMap
在Python中，可以使用collections模块中的OrderedDict类来实现类似于Java中LinkedHashMap的功能。
本文最后还提供了一种 结合双向链表和哈希表的 从零开始的实现，供参考。
// 使用 LinkedHashMap 实现
class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
// 将 key 变为最近使⽤
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsKey(key)) {
// 修改 key 的值
cache.put(key, val);
// 将 key 变为最近使⽤
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使⽤的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
// 将新的 key 添加链表尾部
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
// 删除 key，重新插⼊到队尾
cache.remove(key);
cache.put(key, val);
}
}
# 使用 OrderedDict 实现
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cc = capacity
self.d = OrderedDict()
def get(self, key: int) -> int:
if key in self.d:
self.d.move_to_end(key)
return self.d[key]
return -1
def put(self, key: int, value: int) -> None:
if key in self.d:
del self.d[key]
self.d[key] = value
if len(self.d) > self.cc:
self.d.popitem(last=False)
# 手撸LRU算法，结合双向链表和哈希表，LinkedHashMap
# 先定义双向链表节点
class DoubleListNodeLRU:
next, last = None, None
def __init__(self, k, v):
self.k = k
self.v = v
class NodeLRU:
head, tail = None, None
size = None
def __init__(self):
# head tail 为 头尾虚拟节点
self.head = DoubleListNodeLRU(0, 0)
self.tail = DoubleListNodeLRU(0, 0)
self.head.next = self.tail
self.tail.last = self.head
self.size = 0
# 链表尾部添加节点 时间 O(1)
def addLast(self, x: DoubleListNodeLRU):
x.last = self.tail.last
x.next = self.tail
self.tail.last.next = x
self.tail.last = x
self.size += 1
# 删除链表中的 x 节点（x ⼀定存在）
# 由于是双链表且给的是⽬标Node节点，时间O(1)
def remove(self, x: DoubleListNodeLRU):
x.last.next = x.next
x.next.last = x.last
self.size -= 1
# 删除链表中第⼀个节点，并返回该节点，时间 O(1)
def removeFirst(self):
if self.head.next == self.tail:
return None
first = self.head.next
self.remove(first)
return first
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
# key -> node(key, val)
self.map = dict()
self.cache = NodeLRU()
# 将某个 key 提升为最近使⽤的
def makeRecently(self, k):
node = self.map.get(k)
self.cache.remove(node)
self.cache.addLast(node)
# 添加最近使⽤的元素
def addRecently(self, k, v):
node = DoubleListNodeLRU(k, v)
self.cache.addLast(node)
self.map[k] = node
# 删除某⼀个 key
def deletekey(self, k):
node = self.map[k]
self.map.pop(k)
self.cache.remove(node)
def removeLeastRecently(self):
deleteNode = self.cache.removeFirst()
deletekey = deleteNode.k
self.map.pop(deletekey)
def get(self, k):
if k not in self.map:
return -1
self.makeRecently(k)
return self.map.get(k).v
def put(self, k, v):
if k in self.map:
self.deletekey(k)
self.addRecently(k, v)
return
if self.cache.size == self.cap:
self.removeLeastRecently()
self.addRecently(k, v)