LRU(Least Recently Used)最近最少使用-P

LRU缓存

假设：长期不被使用的数据，在未来不被使用到的几率也不大。因此，当数据所占内存达到一定阈值时，我们就要移除掉最近最少使用的数据。

数据结构：哈希链表
哈希表由若干个Key-value组成，在“逻辑上”，这些key-value无所谓排列顺序，谁先谁后都一样

在哈希链表中，这些Key-value不再是彼此无关的存在，而是被一个链条串了起来，每一个key-value都具有它的前驱、后继，就像双向链表中的节点一样。使原本无序的哈希表变得有序。

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)

使用双向链表，存储具体的值，链表的最大容量为缓存的大小；
使用哈希表，其中键用于存储页号，值用于存储链表的地址
1、访问：
1.1 所需页面不存在内存中，返回 -1
1.2 所需页面在内存中，把最近使用的页面移动到链表的头部，把最近没有使用的页面放到链表的尾部
2、缓存：
2.1 被添加的元素已存在 更新元素值并已到链表头部
2.2 被添加的元素不存在
2.2.1 链表容量达到上限 删除尾部元素
2.2.2 链表容量未达上限 添加至链表头部

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
    
    def remove_this(self):
        if self.prev:
            self.prev.next = self.next
        if self.next:    
            self.next.prev = self.prev
        self.prev = None
        self.next = None
        return self.key
    
    def put_prev(self, Node):
        Node.prev = self.prev
        self.prev.next = Node
        self.prev = Node
        Node.next = self
    
       
class LRUCache: # 哈希链表

    def __init__(self, capacity: int):
        self.dict = dict()
        self.capacity=capacity
        self.cur_num = 0
        self.head = Node(0,0)
        self.tail = Node(0,0)

        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.dict.keys():
            return -1
        else:
            cur_node = self.dict[key]
            cur_node.remove_this()
            self.tail.put_prev(cur_node)
            return cur_node.value

    def put(self, key: int, value: int) -> None:
        cur_node = Node(key, value)
        if key in self.dict.keys():
            self.dict[key].remove_this()
            self.dict[key] = cur_node
            self.tail.put_prev(cur_node)
        elif self.cur_num < self.capacity:        
            self.tail.put_prev(cur_node)
            self.dict[key] = cur_node
            self.cur_num += 1                 
        else:
            del_key = self.head.next.remove_this()
            del self.dict[del_key]
            self.tail.put_prev(cur_node)
            self.dict[key] = cur_node
        return