LRU（Least recently used，最近最少使用），数据插入队列中，经常访问的数据单元靠近列表头部，不经常访问的靠近列表尾部。列表数据就像按照时间排序一样。常用来淘汰一些长时间不使用的数据。
1. 算法流程
lru 算法用一个列表也可以实现。只是列表数据需要更新操作，那得先查找数据，列表的查找时间复杂度是 O(n)，这是个低效的操作，所以用时间复杂度为 O(1) 的哈希表 std::unordered_map 辅助实现查找。
2. 算法实现
简单实现 LRU 算法的添加，更新和删除最旧数据功能。定时测试相关接口操作。(测试源码放在 github)
2.1. 头文件
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
#pragma once
#include <iostream>
#include <list>
#include <memory>
#include <unordered_map>
class Data {
public:
Data() {}
Data(const Data& d) : m_key(d.m_key), m_value(d.m_value) {}
Data(const std::string& key, const std::string& value)
: m_key(key), m_value(value) {}
public:
std::string key() const { return m_key; }
void set_key(const std::string& key) { m_key = key; }
std::string value() const { return m_value; }
void set_value(const std::string& value) { m_value = value; }
private:
std::string m_key;
std::string m_value;
};
class Lru {
public:
Lru() {}
virtual ~Lru() {}
bool insert(const std::string& key, const std::string& value);
bool update(const std::string& key, const std::string& value);
bool remove(const std::string& key);
/* 删除列表末位节点。*/
bool pop();
std::shared_ptr<Data> get_data(const std::string& key);
private:
/* 数据存储列表。*/
std::list<std::shared_ptr<Data>> m_list;
/* 更新哈希表数据，存储节点在列表的位置信息，方便查询。*/
std::unordered_map<std::string, std::list<std::shared_ptr<Data>>::iterator> m_map;
};
2.2. 源文件
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
66
67
/* g++ -g -O0 -W -std=c++11 lru.cpp -o test && ./test */
#include "lru.h"
bool Lru::insert(const std::string& key, const std::string& value) {
if (key.empty() || value.empty() || (m_map.find(key) != m_map.end())) {
return false;
}
m_list.push_front(std::make_shared<Data>(key, value));
m_map[key] = m_list.begin();
std::cout << "insert key: " << key << " value: " << value << std::endl;
return true;
}
bool Lru::update(const std::string& key, const std::string& value) {
/* 通过哈希表，查找对应节点在列表的位置。*/
auto it = m_map.find(key);
if (it == m_map.end()) {
return false;
}
/*更新数据信息。*/
auto p = *(it->second);
p->set_value(value);
/* 先从列表删除对应节点，然后重新将节点添加到列表头部。*/
m_list.erase(it->second);
m_list.push_front(p);
/* 更新哈希表数据，存储节点在列表的位置信息，方便查询。*/
m_map[p->key()] = m_list.begin();
return true;
}
bool Lru::remove(const std::string& key) {
auto it = m_map.find(key);
if (it == m_map.end()) {
return false;
}
m_map.erase(key);
m_list.erase(it->second);
return true;
}
bool Lru::pop() {
if (m_list.empty()) {
return false;
}
/* 删除哈希表对应信息。*/
auto it = m_list.end();
auto p = *(--it);
m_map.erase(p->key());
/* 删除列表对应节点。*/
m_list.erase(it);
std::cout << "pop: " << p->key() << " " << p->value() << std::endl;
return true;
}
std::shared_ptr<Data> Lru::get_data(const std::string& key) {
auto it = m_map.find(key);
if (it != m_map.end()) {
return *(it->second);
}
return nullptr;
}
3. redis 近似 lru 算法
redis 数据库 maxmemory 数据淘汰策略，通过采样实现了近似 LRU 的算法，有兴趣的朋友可以参考：
