|
使用哈希链表实现，而哈希链表由双向链表和哈希表构建。
参考自算法就像搭乐高：带你手撸 LRU 算法
class Node:
"""
节点类
"""
def __init__(self, k, v):
self.k = k
self.v = v
self.next = None
self.prev = None
class DoubleList:
"""
双向链表
"""
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 addLast(self, x):
"""
尾部添加节点
:param x:
:return:
"""
x.next = self.tail
x.prev = self.tail.prev
self.tail.prev.next = x
self.tail.prev = x
self.size += 1
def remove(self, x):
"""
删除节点
:param x:
:return:
"""
x.prev.next = x.next
x.next.prev = x.prev
self.size -= 1
def removeFirst(self):
"""
删除列表的第一个节点
:return:
"""
first = self.head.next
if first == self.tail:
return None
self.remove(first)
return first
def length(self):
"""
列表长度
:return:
"""
return self.size
class LRUCache:
"""
LRU类
"""
def __init__(self, capacity):
self.capacity = capacity
self.cache = DoubleList()
self.map = {}
def get(self, key):
"""
获取key
:param key:
:return:
"""
if not self.map.get(key):
return -1
self.makeRecently(key)
return self.map.get(key).v
def put(self, key, val):
"""
添加或修改类
:param key:
:param val:
:return:
"""
if self.map.get(key):
self.deleteKey(key)
self.addRecently(key, val)
return
if self.cache.length() == self.capacity:
self.removeLeaseRecently()
self.addRecently(key, val)
def makeRecently(self, key):
"""
将节点提升为最近使用的
:param key:
:return:
"""
node = self.map.get(key)
self.cache.remove(node)
self.cache.addLast(node)
def deleteKey(self, key):
"""
删除key
:param key:
:return:
"""
node = self.map.get(key)
self.cache.remove(node)
self.map.pop(key)
def removeLeaseRecently(self):
"""
删除最久未使用的
:return:
"""
node = self.cache.removeFirst()
self.map.pop(node.k)
def addRecently(self, key, val):
"""
添加最新使用的
:param key:
:param val:
:return:
"""
node = Node(key, val)
self.cache.addLast(node)
self.map[key] = node
lru = LRUCache(2)
print(lru.get(1))
lru.put(1, 2)
print(lru.get(1))
lru.put(2, 3)
lru.put(3, 4)
print(lru.cache.tail.prev.k, lru.cache.tail.prev.v)
|