146. LRU缓存机制
程序员文章站
2022-07-15 16:18:19
...
思路
利用哈希表+双向链表,如图所示:
当使用get时,把要get的节点放在表尾,当使用put时,把新加的节点同样放在表尾,表示该节点是最新访问的,如果超过容量,则删除表头的节点,为新节点腾空间。
伪代码:
// key 映射到 Node(key, val)
HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;
int get(int key) {
if (key 不存在) {
return -1;
} else {
将数据 (key, val) 提到表尾;
return val;
}
}
void put(int key, int val) {
Node x = new Node(key, val);
if (key 已存在) {
把旧的数据删除;
将新节点 x 插入到表头;
} else {
if (cache 已满) {
删除链表的第一个数据腾位置;
删除 map 中映射到该数据的键;
}
将新节点 x 插入到表尾;
map 中新建 key 对新节点 x 的映射;
}
}
代码
class Node:
#创建双向链表
def __init__(self,key,val):
self.key = key
self.value = val
self.pre = None
self.tail = None
#表尾是最近使用节点,表头是长时间未使用节点
class LRUCache:
def __init__(self, capacity: int):
self.head = Node(0,0)
self.tail = Node(0,0)
self.head.next = self.tail
self.tail.pre = self.head
self.d = dict()
self.max_len = capacity
def get(self, key: int) -> int:
if key in self.d:
node = self.d[key]
self.remove(node) #删除该节点
self.add(node) #增加到表尾
return node.value
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.d:
self.remove(self.d[key])
if len(self.d) == self.max_len:
self.remove(self.head.next)
self.add(Node(key,value))
#删除链表节点
def remove(self,node):
del self.d[node.key] #删除映射关系
node.pre.next = node.next #删除链表中的该节点
node.next.pre = node.pre
#表尾增加节点
def add(self,node):
self.d[node.key] = node #更新键所对应的值
pre_tail = self.tail.pre
node.next = self.tail
self.tail.pre = node
pre_tail.next = node
node.pre = pre_tail