运用掌握的数据结构，设计和实现一个LRU(最近最少使用）缓存机制。

LRU，Least Recently Used，即最近最少使用，是一种常用的页面置换算法。

LRU是操作系统为最大化页面命中率而广泛采用的一种页面置换算法。该算法的思路是，发生页面中断时，选择未使用时间最长的页面置换出去。

功能：

  • 获取数据 get(key) - 如果关键字key存在于缓存中，则获取关键字的值，否则返回-1。
  • 写入数据put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组。当缓存容量达到上限时，它应该再写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

分析

  1. 使用双向链表实现的队列，队列的最大容量为缓存的大小。在使用过程中，把最近使用的页面移动到队列头，最近没有使用的页面将被放在队列尾的位置。
  2. 使用一个哈希表，把页号作为键，把缓存在队列中的结点的地址作为值。
  1. class DLinkedNode:
  3.     def __init__(self, key=0, value=0) -> None:
  4.         self.key = key
  5.         self.value = value
  6.         self.prev = None
  7.         self.next = None
  10. class LRUCache:
  11.     def __init__(self, capacity: int) -> None:
  12.         self.cache = dict()
  13.         #  使用伪头部和伪节点
  14.         self.head = DLinkedNode()
  15.         self.tail = DLinkedNode()
  16.         self.head.next = self.tail
  17.         self.tail.next = self.head
  18.         self.capacity = capacity
  19.         self.size = 0
  21.     def get(self, key: int) -> int:
  22.         if key not in self.cache:
  23.             return -1
  24.         #  如果key存在，先通过哈希表定位，再移动头部
  25.         node = self.cache[key]
  26.         self.moveToHead(node)
  27.         return node.value
  29.     def put(self, key: int, value: int) -> None:
  30.         if key not in self.cache:
  31.             #  如果key不存在，创建一个新的节点
  32.             node = DLinkedNode(key, value)
  33.             #  添加哈希表
  34.             self.cache[key] = node
  35.             #  添加至双向链表的头部
  36.             self.addToHead(node)
  37.             self.size += 1
  38.             if self.size > self.capacity:
  39.                 #  如果超出容量，删除双向链表的尾部节点
  40.                 removed = self.removeTail()
  41.                 #  删除哈希表中对应的项
  42.                 self.cache.pop(removed.key)
  43.                 self.size -= 1
  44.         else:
  45.             #  如果key存在，先通过哈希表定位，再修改value，并移到头部
  46.             node = self.cache[key]
  47.             node.value = value
  48.             self.moveToHead(node)
  50.     def addToHead(self, node):
  51.         #  头结点添加node
  52.         node.prev = self.head
  53.         node.next = self.head.next
  54.         self.head.next.prev = node
  55.         self.head.next = node
  57.     def removeNode(self, node):
  58.         #  双向链表删除数据
  59.         node.prev.next = node.next
  60.         node.next.prev = node.prev
  62.     def moveToHead(self, node):
  63.         self.removeNode(node)
  64.         self.addToHead(node)
  66.     def removeTail(self):
  67.         node = self.tail.prev
  68.         self.removeNode(node)
  69.         return node
  73. # Your LRUCache object will be instantiated and called as such:
  74. # obj = LRUCache(capacity)
  75. # param_1 = obj.get(key)
  76. # obj.put(key,value)