LRU算法

力扣LRU算法

原理

LRU（Leasted Recently Used）缓存机制可以通过哈希表和辅助双向链表实现

双向链表按照被使用的顺序存储了键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表存储数据的键映射到其在双向链表中的位置。

逻辑：

针对get操作：

先判断哈希表cache中是否存在该key
- 如果不存在则直接返回-1
- 如果存在，则将通过哈希表找到对应的结点并将该结点删除（removeNode）并在开头添加一个结点(（addToHead)，其中删除和添加操作只需要修改指针，因此时间复杂度为O(1)满足题目要求

针对put操作：

判断哈希表cache中是否存在该key
- 如果不存在该key则
  - 先以该key、value为键值对构建一个双向链表node
  - 将该结点node添加到链表的开头（addToHead)
  - 然后在哈希表中添加键key和值node
  - 将self.size+1，并判断当前size大小是否超过capacity
  - 如果没有超过则不进行任何操作
  - 如果超过了，则需要进行淘汰，将双线链表的末尾的结点删除并将其对应的key从哈希表中删除
- 如果存在该key
  - 则从哈希表cache中获取该key所对应的结点node
  - 然后将node的value更新为最新的
  - 然后将node结点移动到链表的最开头（moveToHead）

双向链表实现

# 双向链表
class DLinkedNode:
    def __init__(self,key=0,value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

哈希表实现

哈希表的实现在Python中使用数组即可，需要注意，头尾节点的都是一个虚拟虚拟的伪结点，他们的中间才是真正的元素

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        # 使用伪头结点和伪尾节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

代码实现

# 双向链表
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 = dict()
        # 使用伪头结点和伪尾节点
        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] # 通过哈希表找到node的位置
        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)
                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 moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeNode(self,node):
        node.prev.next = node.next
        node.next.prev = node.prev

    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)

链表的几个操作说明：

addToHead(node)：将node添加到双向链表的开头
moveToHead(node)：将node结点移动到双向链表的开头（本质上是删除removeNode+添加addToHead）
removeNode(node)：就node结点从双向链表中删除
removeTail()：删除双向链表的最后一个结点并返回该结点

补充OrderDict

在Python中的collections中，有一个有序字典完美契合本题的要求，即collections.OrderDict

特有方法：

popitem(last=True)
- 参数默认为True表示移除有序字典中的最后一个元素；如果参数为False则表示移除第一个元素；
move_to_end(key,last=True)
- 参数1为需要移动的关键字key
- 参数2为布尔值，默认为True，表示移动到末尾；如果为False的情况下，则表示移动到开头

使用该方法实现的代码：

让该类继承自collections.OrderedDict，然后就可以使用move_to_end()和popitem()两个方法了

class LRUCache(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity


    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)