146.LRU缓存机制题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/lru-cache题目利用你掌握的数据结构，设计并实现一个LRU（leastrecentlyused）缓存机制。它应该支持以下操作：getdataget和writedataput。获取数据get(key)-如果缓存中存在该键，则获取该键的值（始终为正值），否则返回-1。写入数据put(key,value)-如果键已经存在，改变它的数据值；如果键不存在，则插入“键/数据值”的集合。当缓存容量达到上限时，它应该在写入新数据之前删除最旧的未使用数据值，从而为新数据值腾出空间。进阶：你能在O(1)时间复杂度内完成这两个操作吗？示例：LRUCachecache=newLRUCache(2/*缓存容量*/);cache.put(1,1);cache.put(2,2);cache.get(1);//返回1cache.put(3,3);//此操作将使密钥2失效cache.get(2);//返回-1（未找到）cache.put(4,4);//此操作将使密钥1无效.get(1);//返回-1（未找到）cache.get(3);//返回3cache.get(4);//返回4解题思路：哈希表，双向链表首先，先解释LRU，LRU（LeastRecentlyUsed），最近最少使用。这是一种缓存消除策略。例如，通常缓存容量是有限的。如果要删除一些内容腾出空间，此时应该考虑删除哪些内容？哪些内容没有用，可以删除？哪些应该保留并且有用？LRU策略认为最近使用的数据是有用的，而长时间未使用的数据是无用的。当缓存不足时，这些长期不用的数据会先被删除。这是对LRU策略的简单描述，当然还有其他的策略，比如LFU。再看这道题，因为题中有需求，【是否可以在O(1)时间复杂度内完成获取数据get和写入数据put的操作？】这里需要考虑的是，要在时间复杂度O(1)内完成上述操作，我们要使用的数据结构条件应该具备以下特点：查找、插入、删除要快。我们知道哈希表，查找速度快，但是没有顺序。链表、插入、删除快速有序，但查找速度较慢。在这一点上，我们考虑两者的结合。这里，因为当缓存容量达到上限时，我们需要进行删除操作。此时要删除一个节点，不仅需要当前节点本身的指针，还需要前驱节点的指针。这里要求双向链表能够在删除和查找前驱时，达到O(1)的时间复杂度。那么现在，如果使用哈希表+双向链表来实现功能设计：首先，双向链表部分按照使用顺序存储键值对。最近使用过头部附近，最近未使用过尾部附近。哈希表，键映射其在双向链表中的位置。具体实现方法：get：先判断key是否存在：如果不存在，存在则返回-1，此时对应的节点定义为最近使用过的。然后先定位它在双向链表中的位置，移到头部，返回节点的值。put：同时判断key是否存在：如果不存在，则新建一个节点，将该节点添加到双向链表的头部，同时添加到哈希表中。同时还要判断双向链表是否超出容量。如果超过，则删除结束节点，并删除哈希表的相应部分。当存在时，通过哈希表定位到双向链表中的位置，更新其值，同时移动到双向链表的头部。具体实现代码如下。代码实现classNode(object):def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassDoubleLinkedList(object):def__init__(self):self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headself.size=0defadd_to_head(self,node):"""添加节点到头部"""node.next=self.head.nextnode.prev=self.headself.head.next.prev=nodeself.head.next=nodeself.size+=1defremove_node(self,node):"""删除节点"""node.prev.next=node.nextnode.next.prev=node.prevself.size-=1defremove_tail(self):"""删除尾部节点"""ifself.size==0:returnNonenode=self.tail.prevself.remove_node(node)returnnodedefget_size(self):returnself.sizeclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.hashmap={}self.cache=DoubleLinkedList()defget(self,key:int)->int:#判断key是否存在,根据key不在self.hashmap中的情况处理:return-1#通过哈希表定位其在双向链表中的位置value=self.hashmap[key].value#这里实现的逻辑体现在putoperation#put操作在key中存在时，也需要移到链表头部self.put(key,value)returnvaluedefput(self,key:int,value:int)->None:#先创建节点node=Node(key,value)#再判断key是否存在#ifkeyinself.hashmap:self.cache.remove_node(self.hashmap[key])self.cache.remove_node(self.hashmap[key])self.cache.add_to_head(node)self.hashmap[key]=nodeelse:#判断缓存容量是否不够ifself.capacity==self.cache.get_size():#删除最后一个节点tail=self.cache.remove_tail()self.hashmap.pop(tail.key)#添加到头部self.cache.add_to_head(node)self.hashmap[key]=node#你的LRUCache对象将被实例化并这样调用：#obj=LRUCache(capacity)#param_1=obj.get(key)#obj.Put(key,value)执行结果汇总使用哈希表+双向链表实现时间复杂度为O(1)的操作；双向链表按使用顺序存储键值对，最近使用的在最前面，最近用的不在最后；哈希表和键映射存储在双向链表中。欢迎关注微信公众号《书所集录》
