最近最久未用置换算法用到的数据结构
时间: 2023-12-04 17:41:17 浏览: 81
最近最久未用(LRU)置换算法用到的数据结构是一个双向链表和一个哈希表。其中,双向链表用于存储页面,按照访问时间从旧到新排序,链表头为最近最久未使用的页面,链表尾为最近刚被访问的页面。哈希表用于快速查找页面是否在链表中,并记录其在链表中的位置。当需要置换页面时,选择链表头的页面进行置换即可。
以下是最近最久未用(LRU)置换算法的数据结构示例:
```python
class Node:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def move_node_to_tail(self, key):
node = self.hashmap[key]
node.prev.next = node.next
node.next.prev = node.prev
node.next = self.tail
node.prev = self.tail.prev
self.tail.prev.next = node
self.tail.prev = node
def get(self, key: int) -> int:
if key in self.hashmap:
self.move_node_to_tail(key)
return self.hashmap[key].value
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
self.hashmap[key].value = value
self.move_node_to_tail(key)
else:
if len(self.hashmap) == self.capacity:
del self.hashmap[self.head.next.key]
self.head.next = self.head.next.next
self.head.next.prev = self.head
node = Node(key, value)
self.hashmap[key] = node
node.next = self.tail
node.prev = self.tail.prev
self.tail.prev.next = node
self.tail.prev = node
```