LRU 算法
零、基于双向链表 + HashMap 的 LRU 算法
LRU 缓存算法也叫 LRU 页面置换算法，是一种经典常用的页面置换算法。
- 访问某个节点时，将其从原来的位置删除，并重新插入到链表头部。这样就能保证链表尾部存储的就是最近最久未使用的节点，当节点数量大于缓存最大空间时就淘汰链表尾部的节点。
- 为了使删除操作时间复杂度为 O(1)，就不能采用遍历的方式找到某个节点。HashMap 存储着 Key 到节点的映射，通过 Key 就能以 O(1) 的时间得到节点，然后再以 O(1) 的时间将其从双向队列中删除。
一、基于双向链表 + HashMap 的 LRU 算法实现（Java）
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| public class LRU<K, V> implements Iterable<K> {
private Node head;
private Node tail;
private HashMap<K, Node> map;
private int maxSize;
private class Node {
Node pre;
Node next;
K k;
V v;
public Node(K k, V v) {
this.k = k;
this.v = v;
}
}
public LRU(int maxSize) {
this.maxSize = maxSize;
this.map = new HashMap<>(maxSize * 4 / 3);
head = new Node(null, null);
tail = new Node(null, null);
head.next = tail;
tail.pre = head;
}
public V get(K key) {
if(!map.containKey(key)) {
return null;
}
Node node = map.get(key);
unlink(node);
appendHead(node);
return node.v;
}
public void put(K key, V value) {
if(map.containsKey(key)) {
Node node = map.get(key);
unlink(node);
}
Node node = new Node(key, value);
map.put(key, value);
appendHead(node);
if(map.size() > maxSize) {
Node toRemove = removeTail();
map.remove(toRemove.k)
}
}
private void unlink(Node node) {
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
node.pre = null;
node.next = null;
}
private void appendHead(Node node) {
Node next = head.next;
node.next = next;
next.pre = node;
node.pre = head;
head.next = node;
}
private Node removeTail() {
Node node = tail.pre;
Node pre = node.pre;
tail.pre = pre;
pre.next = tail;
node.pre = null;
node.next = null;
return node;
}
@Override
public Iterator<K> iterator() {
return new Iterator<K>() {
private Node cur = head.next;
@Override
public boolean hasNext() {
return cur != tail;
}
@Override
public K next() {
Node node = cur;
cur = cur.next;
return node.k;
}
}
}
}
|
二、基于双向链表 + HashMap 的 LRU 算法实现（C++）
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
|
class LRU
{
public:
LRU(int capacity) : capacity(capacity)
{
}
int get(int key)
{
if(pos.find(key) != pos.end())
{
put(key, pos[key]->second);
return pos[key]->second;
}
return -1;
}
void put(int key, int value)
{
if(pos.find(key) != pos.end())
{
recent.erase(pos[key]);
}
else if(recent.size() >= capacity)
{
pos.erase(recent.back().first);
recent.pop_back();
}
recent.push_front({ key, value });
pos[key] = recent.begin();
}
private:
int capacity;
list<pair<int, int>> recent;
unordered_map<int, list<pair<int, int>>::iterator> pos;
};
|
LRU 算法实现并不难，但是要高效地实现却是有难度的，要想高效实现其中的插入、删除、查找，第一想法就是红黑树，但是红黑树也是一种折中的办法。插入、删除效率最高当属链表，查找效率当属 hash。所以，这里我们就将链表和 hash 结合起来，利用空间换时间的思想，实现 LRU 算法。
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
| class LRU
{
private:
struct Node
{
int key;
int value;
Node(int k, int v) : key(k), value(v) {}
};
public:
LRU(int c) : capacity(c) {}
int get(int key)
{
if(cacheMap.find(key) == cacheMap.end())
{
return -1;
}
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
cacheMap[key] = cacheList.begin();
return cacheMap[key]->value;
}
void set(int key, int value)
{
if(cacheMap.find(key) == cacheMap.end())
{
if(cacheList.size() == capacity)
{
cacheMap.erase(cacheList.back().key);
cacheList.pop_back();
}
cacheList.push_front(Node(key, value));
cacheMap[key] = cacheList.begin();
}
else
{
cacheMap[key]->value = value;
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
cacheMap[key] = cacheList.begin();
}
}
private:
int capacity;
list<Node> cacheList;
unordered_map<int, list<Node>::iterator> cacheMap;
};
|
C++ list::splice() 函数详解
list::splice() 实现 list 拼接的功能。将源 list 的内容部分或全部元素删除，拼插入到目的 list。
函数有以下三种声明：
1
2
3
4
5
| void splice(iterator position, list<T, Allocator>& x);
void splice(iterator position, list<T, Allocator>& x, iterator it);
void splice(iterator position, list<T, Allocator>& x, iterator first, iterator last);
|
position 是要操作的 list 对象的迭代器，list&x 是被剪的对象。
- 会在 position 后把 list&x 所有的元素剪接到要操作的 list 对象
- 只会把 it 的值剪接到要操作的 list 对象中
- 把 first 到 last 剪接到要操作的 list 对象中
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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
list<int>li1, li2;
for(int i = 1; i <= 4; i++)
{
li1.push_back(i);
li2.push_back(i+10);
}
list<int>::iterator it = li1.begin();
it++;
li1.splice(it, li2);
if(li2.empty())
{
cout<<"li2 is empty"<<endl;
}
li2.splice(li2.begin(), li1, it);
cout << *it <<" " << endl;
it = li1.begin();
advance(it, 3);
li1.splice(li1.begin(), li1, it, li1.end());
for(list<int>::iterator it = li1.begin(); it != li1.end(); ++it)
{
cout << *it <<" ";
}
cout << endl;
for(list<int>::iterator it = li2.begin(); it != li2.end(); ++it)
{
cout << *it <<" ";
}
cout << endl;
return 0;
|
输出如下所示：
1
2
3
4
5
| ubuntu@VM-0-9-ubuntu:~$ ./list
li2 is empty
2
13 14 3 4 1 11 12
2
|
