欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

146. LRU缓存机制

程序员文章站 2022-07-15 16:18:19
...

146. LRU缓存机制

思路

利用哈希表+双向链表,如图所示:
146. LRU缓存机制
当使用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