LeetCode-146-LRU缓存机制-Python

146. LRU缓存机制

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/lru-cache

题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

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

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 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 作废cache.get(1);       // 返回 -1 (未找到)cache.get(3);       // 返回  3cache.get(4);       // 返回  4

解题思路

思路：哈希表、双向链表

首先，先解释一下 LRU，LRU（Least Recently Used），最近最少使用。它是一种缓存淘汰策略。

比如，正常来说缓存容量是有限的，如果希望删除一些内容时腾出空间时，这个时候就应该考虑删除哪些内容？哪些内容是没用的，可以删除的？哪些应该保留，是有用的？

LRU 这种策略，就认为最近使用的数据是有用的，而哪些长时间未使用的就是没用的，当缓存不足时，就会优先删除这些长时间未使用的。

这就是 LRU 这个策略的简单描述，当然还有其他的策略，比如 LFU 等。

再看本题，因为题目有个要求，【是否可以在 O(1) 时间复杂度内完成获取数据 get 和写入数据 put 操作？】

在这里就应该考虑，要实现时间复杂度 O(1) 内完成上面的操作，我们要使用的数据结构条件就应该具有以下的特点：查找、插入、删除都要快。

我们知道哈希表，查找速度快，但是没有顺序之分。而链表，插入删除快，有顺序，但是查找慢。此时，我们考虑将两者结合使用。

在这里，因为当缓存容量达到上限的时候，我们需要执行删除操作，此时删除节点，不仅要当前节点本身的指针，还需要前驱节点的指针，这里则需要使用双向链表，才能够在删除并查找前驱时，实现 O(1) 的时间复杂度。

那么现在来看，如果使用哈希表+双向链表实现功能设计：

• 首先双向链表部分，按照使用顺序存储键值对。靠近头部为最近使用，靠近尾部为非最近使用。
• 哈希表，键映射其在双向链表的位置。

具体实现的方法：

• get：首先要判断 key 是否存在：

  • 不存在返回 -1
  • 存在时，此时对应的节点则定为最近使用。那么先定位它在双向链表的位置，将其移动到头部，返回该节点的值。

• put：同样判断 key 是否存在：

  • 不存在，创建新节点，在双向链表头部添加该节点，同时也要添加到哈希表中。同时还需要判断双向链表容量是否超出，如果超出，将末尾节点删除，同时删除哈希表对应部分。
  • 存在时，通过哈希表定位在双向链表的位置，更新它的值，同时移动到双向链表头部。

具体的实现代码如下。

代码实现

class Node(object):    def __init__(self, key=0, value=0):        self.key = key        self.value = value        self.prev = None        self.next = Noneclass DoubleLinkedList(object):    def __init__(self):        self.head = Node(0, 0)        self.tail = Node(0, 0)        self.head.next = self.tail        self.tail.prev = self.head        self.size = 0        def add_to_head(self, node):        """添加节点到头部        """        node.next = self.head.next        node.prev = self.head        self.head.next.prev = node        self.head.next = node        self.size += 1        def remove_node(self, node):        """删除节点        """        node.prev.next = node.next        node.next.prev = node.prev        self.size -= 1        def remove_tail(self):        """删除尾部节点        """        if self.size == 0:            return None        node = self.tail.prev        self.remove_node(node)        return node        def get_size(self):        return self.sizeclass LRUCache:    def __init__(self, capacity: int):        self.capacity = capacity        self.hashmap = {}        self.cache = DoubleLinkedList()    def get(self, key: int) -> int:        # 判断 key 是否存在，分情况处理        if key not in self.hashmap:            return -1        # 通过哈希表定位其在双向链表的位置        value = self.hashmap[key].value        # 这里实现的逻辑在 put 操作体现        # put 操作在键存在时，同样需要移至链表头部        self.put(key, value)        return value    def put(self, key: int, value: int) -> None:        # 先创建节点        node = Node(key, value)        # 同样判断 key 是否存在        # 分情况处理        if key in self.hashmap:            self.cache.remove_node(self.hashmap[key])            self.cache.add_to_head(node)            self.hashmap[key] = node        else:            # 判断缓存容量是否不够            if self.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# Your LRUCache object will be instantiated and called as such:# obj = LRUCache(capacity)# param_1 = obj.get(key)# obj.put(key,value)

实现结果

总结

• 使用哈希表+双向链表，实现题意要求时间复杂度为 O(1) 的操作；
• 双向链表按照使用顺序存储键值对，最近使用在头部，非最近使用在尾部；
• 哈希表，键映射其存储在双向链表的位置。

欢迎关注微信公众号《书所集录》