LRU缓存机制的实现
2020-07-19 本文已影响0人
siliconx
LRU(Least Recently Used)是一种缓存替换策略。现实生活中，缓存的大小总是有限的，为了合理地利用缓存，在缓存满了以后需要利用合适的替换策略把某些内容从缓存中移出，以腾出空间给新的元素。LRU就是其中一种常见的策略，它把缓存中最不常访问到的数据移出。
为了实现LRU，可以利用哈希表+双向链表。哈希表以键值对的形式保存元素，并以O(1)的时间复杂度取出元素；双向链表用于记录每个元素的使用情况。具体如下：
- 每次缓存新元素时，都把它放在表尾（如果缓存中已存在该元素，把它移动到表尾）
- 每次获取元素时，也把该元素移动到表尾
- 这样就可以保证链表第一个元素始终是最不常使用的元素，在缓存满时只需要移除第一个元素即可
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.cache = {}
self.head = Node(-1, -1)
self.tail = self.head
def get(self, key: int) -> int:
if key in self.cache:
e = self.cache[key]
# 把元素移到表尾
self.move2end(e)
return e.value
return -1
def put(self, key: int, value: int) -> None:
if key not in self.cache:
if self.size < self.capacity:
self.size += 1
else:
# 满了，移除第一个元素
out = self.head.next_
if out != self.tail:
self.head.next_ = out.next_
out.next_.prev = self.head
else:
self.head.next_ = None
self.tail = self.head
self.cache.pop(out.key)
# 添加新元素到表尾
e = Node(key, value)
self.tail.next_ = e
e.prev = self.tail
self.tail = e
self.cache[key] = e
else:
e = self.cache[key]
e.value = value
# 把元素移到表尾
self.move2end(e)
def move2end(self, e):
"""把e移到链表末尾."""
if e != self.tail:
prev = e.prev
next_ = e.next_
prev.next_ = e.next_
next_.prev = prev
self.tail.next_ = e
e.prev = self.tail
e.next_ = None
self.tail = e
class Node:
def __init__(self, key, value):
self.prev = None
self.next_ = None
self.key = key
self.value = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
