LRU缓存机制

1、题目

图1

2、题解

哈希表+双向链表

• 双向链表按照被使用的顺序存储键值对，靠近头部的键值为最近使用，靠近尾部的键值是最久未使用。
• 哈希表通过存储数据的键映射至双向链表的位置。

算法流程：首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动至双向链表头部。

对于get操作，首先判断key是否存在：若存在，则key对应节点为最近被使用节点；若不存在则返回-1。

对于put，同样先判断key是否存在：

• 若key不存在，根据传入key和value创建新节点，并添加至双向链表头部，同时将key和该节点添进哈希表中。然后判断双向链表的结点是否超出容量，如果超出则删除双向链表尾部结点，并清除哈希表中的对应项。
• 若key存在，先通过哈希表定位，再将对应节点值更新为value，将节点移动到双向链表头部。

class DualNode:
    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.dict = {}
        self.len = capacity
        self.head = DualNode()
        self.tail = DualNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    def get(self, key: int) -> int:
        if key not in self.dict:
            return -1
        node = self.dict[key]
        self.movetoHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.dict:
            node = DualNode(key,value)
            self.dict[key] = node
            self.addtoHead(node)
            self.size += 1
            if self.size >self.len:
                removed = self.removeTail()
                self.dict.pop(removed.key)
                self.size -= 1
        else:
            node = self.dict[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      




# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)