LRU缓存机制-python

问题:

# 运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 
#
#
#
# 实现 LRUCache 类:
#
#
# LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
# int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
# void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上
# 限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
#

题解:

#### 方法一:哈希表 + 双向链表

**算法**

LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

- 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。

- 哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。

这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在 *O(1)* 的时间内完成 `get` 或者 `put` 操作。具体的方法如下:

- 对于 `get` 操作,首先判断 `key` 是否存在:

- 如果 `key` 不存在,则返回 *-1*;

- 如果 `key` 存在,则 `key` 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。

- 对于 `put` 操作,首先判断 `key` 是否存在:

- 如果 `key` 不存在,使用 `key` 和 `value` 创建一个新的节点,在双向链表的头部添加该节点,并将 `key` 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项;

- 如果 `key` 存在,则与 `get` 操作类似,先通过哈希表定位,再将对应的节点的值更新为 `value`,并将该节点移到双向链表的头部。

上述各项操作中,访问哈希表的时间复杂度为 *O(1)*,在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 *O(1)*。而将一个节点移到双向链表的头部,可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作,都可以在 *O(1)* 时间内完成。

参考代码:
# leetcode submit region begin(Prohibit modification and deletion)
class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {}
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = DLinkedNode(key, value)
            self.cache[key ] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key) # 删除hash表中的对应项
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

 

上一篇:SSM框架下,使用ajax请求上传文件(doc\docx\excel\图片等)


下一篇:146. [C++]LRU 缓存机制