LRU (Least Recently Used) 页面置换算法
## 算法介绍
LRU（Least Recently Used，最近最少使用）是一种常用的页面置换算法，其核心思想是：当需要置换页面时，选择最长时间未被使用的页面进行置换。这种算法基于程序的局部性原理，认为最近使用过的页面在不久的将来被再次使用的概率较大。
### 算法特点
1. 实现相对简单
2. 考虑了页面的使用频率
3. 能够较好地反映程序的局部性原理
4. 需要记录每个页面的使用时间
5. 硬件实现成本较高
### 实现方式
LRU算法可以通过以下两种主要方式实现：
1. 计数器方式：为每个页面设置一个计数器，记录该页面最后一次被访问的时间
2. 栈方式：使用一个栈来记录页面的访问顺序，最近访问的页面放在栈顶
## C++代码实现
下面是一个使用哈希表（unordered_map）和双向链表实现的LRU缓存：
```cpp
#include <unordered_map>
#include <list>
#include <iostream>
class LRUCache {
private:
struct Node {
int key;
int value;
Node(int k, int v) : key(k), value(v) {}
};
int capacity;
std::list<Node> cache;
std::unordered_map<int, std::list<Node>::iterator> map;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if (map.find(key) == map.end()) {
return -1; // 未找到
}
// 将访问的节点移到链表头部
cache.splice(cache.begin(), cache, map[key]);
return map[key]->value;
}
void put(int key, int value) {
if (map.find(key) != map.end()) {
// 如果key已存在，更新value并移到链表头部
map[key]->value = value;
cache.splice(cache.begin(), cache, map[key]);
return;
}
if (cache.size() == capacity) {
// 如果缓存已满，删除链表尾部节点
map.erase(cache.back().key);
cache.pop_back();
}
// 在链表头部插入新节点
cache.push_front(Node(key, value));
map[key] = cache.begin();
}
};
// 使用示例
int main() {
LRUCache cache(2); // 创建容量为2的LRU缓存
cache.put(1, 1);
cache.put(2, 2);
std::cout << cache.get(1) << std::endl; // 返回 1
cache.put(3, 3); // 该操作会使key=2的缓存失效
std::cout << cache.get(2) << std::endl; // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使key=1的缓存失效
std::cout << cache.get(1) << std::endl; // 返回 -1 (未找到)
std::cout << cache.get(3) << std::endl; // 返回 3
std::cout << cache.get(4) << std::endl; // 返回 4
return 0;
}
```
### 代码说明
1. 使用双向链表（std::list）存储缓存数据，最近使用的节点在链表头部
2. 使用哈希表（std::unordered_map）实现O(1)时间复杂度的查找
3. 主要操作：
- get(key)：获取缓存数据，并将访问的节点移到链表头部
- put(key, value)：添加或更新缓存数据，如果缓存已满则删除最久未使用的数据
### 时间复杂度分析
- 查找操作（get）：O(1)
- 插入操作（put）：O(1)
- 删除操作：O(1)
### 空间复杂度分析
- 空间复杂度：O(capacity)，其中capacity为缓存容量
## 应用场景
1. 操作系统的页面置换
2. 数据库缓存
3. Web服务器缓存
4. 浏览器缓存
5. 内存管理
## 优缺点分析
### 优点
1. 实现相对简单
2. 考虑了页面的使用频率
3. 能够较好地反映程序的局部性原理
### 缺点
1. 需要记录每个页面的使用时间
2. 硬件实现成本较高
3. 在极端情况下（如循环访问所有页面）性能可能下降