LRU算法
原理
LRU(Leasted Recently Used)缓存机制可以通过哈希表和辅助双向链表实现
- 双向链表按照被使用的顺序存储了键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。
- 哈希表存储数据的键映射到其在双向链表中的位置。
逻辑:
针对get
操作:
- 先判断哈希表cache中是否存在该key
- 如果不存在则直接返回-1
- 如果存在,则将通过哈希表找到对应的结点并将该结点删除(
removeNode
)并在开头添加一个结点((addToHead
),其中删除和添加操作只需要修改指针,因此时间复杂度为O(1)满足题目要求
针对put
操作:
- 判断哈希表cache中是否存在该key
- 如果不存在该key则
- 先以该key、value为键值对构建一个双向链表node
- 将该结点node添加到链表的开头(
addToHead
)
- 然后在哈希表中添加键key和值node
- 将self.size+1,并判断当前size大小是否超过capacity
- 如果没有超过则不进行任何操作
- 如果超过了,则需要进行淘汰,将双线链表的末尾的结点删除并将其对应的key从哈希表中删除
- 如果存在该key
- 则从哈希表cache中获取该key所对应的结点node
- 然后将node的value更新为最新的
- 然后将node结点移动到链表的最开头(
moveToHead
)
双向链表实现
1 2 3 4 5 6 7
| class DLinkedNode: def __init__(self,key=0,value=0): self.key = key self.value = value self.prev = None self.next = None
|
哈希表实现
哈希表的实现在Python中使用数组即可,需要注意,头尾节点的都是一个虚拟虚拟的伪结点,他们的中间才是真正的元素
1 2 3 4 5 6 7 8 9 10 11
| class LRUCache:
def __init__(self, capacity: int): self.cache = dict() self.head = DLinkedNode() self.tail = DLinkedNode() self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.size = 0
|
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| 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 = dict() 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) 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 moveToHead(self, node): self.removeNode(node) self.addToHead(node)
def removeNode(self,node): node.prev.next = node.next node.next.prev = node.prev
def removeTail(self): node = self.tail.prev self.removeNode(node) return node
|
链表的几个操作说明:
addToHead(node)
:将node添加到双向链表的开头
moveToHead(node)
:将node结点移动到双向链表的开头(本质上是删除removeNode
+添加addToHead
)
removeNode(node)
:就node结点从双向链表中删除
removeTail()
:删除双向链表的最后一个结点并返回该结点
补充OrderDict
在Python中的collections中,有一个有序字典完美契合本题的要求,即collections.OrderDict
特有方法:
使用该方法实现的代码:
让该类继承自collections.OrderedDict,然后就可以使用move_to_end()
和popitem()
两个方法了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class LRUCache(collections.OrderedDict):
def __init__(self, capacity: int): super().__init__() self.capacity = capacity
def get(self, key: int) -> int: if key not in self: return -1 self.move_to_end(key) return self[key]
def put(self, key: int, value: int) -> None: if key in self: self.move_to_end(key) self[key] = value if len(self) > self.capacity: self.popitem(last=False)
|