当缓存数据达到预设的上限后，就会优先淘汰近期最少使用的缓存对象，原理是使用双端队列存放元素，哈希表判断数据是否存在

思路

  • 维护一个双端队列用于存放元素，哈希表判断元素是否存在，越接近队列表尾部的元素表示越少被使用到
  • 插入一个元素时，如果元素已存在则将其移动到队列头部，并更新哈希表Key所对应的Value值，如果不存在，则：
    • 如果缓存容量已达到最大值，则将队列尾部节点删除掉，将新的数据放入队列头部
    • 如果缓存容量未达到最大值，则直接将新的数据放入队列头部

  • 查询一个数据时，我们可以使用哈希表来记录每个Key所对应的位置，时间复杂度为O(1)。

    1. # 自建双端列表、哈希表
    2. class LRUCache:
    3.   def __init__(self, capacity):
    4.       self.dicts = {}
    5.       self.queue = []
    6.       # capacity是总大容量
    7.       self.capacity = capacity
    9.   def get(self, key):
    10.       if key in self.dicts:
    11.           # 将其移动到双向队列的头部，最后返回该节点的值
    12.           self.queue.remove(key)
    13.           self.queue.append(key)
    14.           return self.dicts[key]
    15.       else:
    16.           return -1
    18.   def put(self, key, value):
    19.       # 判断再次插入缓存会不会满
    20.       if len(self.dicts) < self.capacity:
    21.           if key in self.dicts:
    22.               # 将其移动到双向队列的头部
    23.               self.dicts[key] = value
    24.               self.queue.remove(key)
    25.               self.queue.append(key)
    26.           else:
    27.               # 直接放到头部
    28.               self.dicts[key] = value
    29.               self.queue.append(key)
    30.       # 如果满了就可能就需要干掉尾部的一些元素
    31.       else:
    32.           if key in self.dicts:
    33.               # 将其移动到双向队列的头部
    34.               self.dicts[key] = value
    35.               self.queue.remove(key)
    36.               self.queue.append(key)
    37.           else:
    38.               # 缓存满了就干掉尾部的一些元素，再放到头部
    39.               self.dicts.pop(self.queue[0])
    40.               self.queue.remove(self.queue[0])
    41.               self.dicts[key] = value
    42.               self.queue.append(key)