操作系统中存在虚拟内存的概念，每个进程都会分配到类似4G这样的内存大小，
但其实物理内存只有4G的大小，所以进程分配到的并不是实际的大小，所以叫他虚拟内存。
虚拟内存用页表进行管理，当进程需要的页不在内存中会发生缺页中断，
将需要的页面调入内存中，如果此时内存又满了，自然就会有之前的页被淘汰出去，
至于淘汰的是哪一个页，这就是页面置换算法所负责的了。
常见的页面置换算法有：
- OPT置换算法（理想置换算法）
- FIFO置换算法（先进先出置换算法）
- LRU置换算法（最近最久未被使用置换算法）
- CLOCK置换算法（时钟置换算法，又称NRU最近未用置换算法）
具体的算法细节可以分别百度，这里就说下LRU吧。
LRU基本思想就是一个页面如果最近很少使用，那么他在将来也会很少被使用，所以最近的最少使用的缓存会被置换出去。
我们用Java数据结构如何模拟呢？
缓存容器很容易可以想到用Map来存储，Map的size到达阈值后就把相应的数据remove掉。
那怎么获取Map中最近最久不被访问的数据呢？
可以给每个缓存加个时间戳，put数据进去的时候记录当前时间戳，然后get数据的时候再更新成当前时间，
put没有空闲空间时执行淘汰策略，就是找到时间戳离当前最久的数据，把他淘汰。
但是要找到这个最久的时间戳不容易，最差需要O(N)的时间复杂度。
所以这里用Map+链表的方式可以很巧妙的实现这个需求。
Map和链表之间互不影响，Map维护他key-value的数据结构，保证取数据时常数级别的时间复杂度，链表维护缓存的优先级，新数据put到链表的头部，get操作时也会把get到的节点移动到链表头部，这样当空间不足时只需要把链表的尾部淘汰掉就ok了，而且链表节点的移动删除都是O(1)级别的，不会有性能上的不足。
其实JDK自带的LinkedHashMap数据结构很好的实现了上述，不过他是个大家伙，下面就自己实现一个简单一点的。
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
| import java.util.HashMap;
import java.util.Map;
class LRUNode {
public String key;
public String value;
public LRUNode pre;
public LRUNode next;
public LRUNode(String key, String value) {
this.key = key;
this.value = value;
}
}
class LRUCache {
private Map<String, LRUNode> cache = new HashMap<>();
private int capacity;
private LRUNode head;
private LRUNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public void put(String key, String value) {
LRUNode node = cache.get(key);
if (node != null) {
node.value = value;
removeNode(node);
} else {
node = new LRUNode(key, value);
if (cache.size() >= capacity) {
cache.remove(tail.key);
removeNode(tail);
}
cache.put(key, node);
}
setHead(node);
}
public String get(String key) {
if (cache.containsKey(key)) {
LRUNode node = cache.get(key);
removeNode(node);
setHead(node);
return node.value;
}
return null;
}
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append('[');
LRUNode node = head;
while (node != null) {
str.append("{" + node.key + "," + node.value + "}");
if (node.next != null) {
str.append(" -> ");
}
node = node.next;
}
str.append(']');
return str.toString();
}
private void setHead(LRUNode node) {
if (head != null) {
node.next = head;
head.pre = node;
}
node.pre = null;
head = node;
if (tail == null) {
tail = node;
}
}
private void removeNode(LRUNode node) {
if (node.pre == null) {
head = node.next;
} else {
node.pre.next = node.next;
}
if (node.next == null) {
tail = node.pre;
} else {
node.next.pre = node.pre;
}
node.pre = null;
node.next = null;
}
}
|
下面再写个main方法测试一下效果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Main {
public static void main(String args[]) {
LRUCache cache = new LRUCache(5);
cache.put("1号", "01");
System.out.println(cache.toString());
cache.put("2号", "02");
System.out.println(cache.toString());
cache.put("3号", "03");
System.out.println(cache.toString());
cache.put("4号", "04");
System.out.println(cache.toString());
cache.put("5号", "05");
System.out.println(cache.toString());
cache.put("6号", "06");
System.out.println(cache.toString());
cache.get("2号");
System.out.println(cache.toString());
cache.put("7号", "07");
System.out.println(cache.toString());
}
}
|
输出：
[{1号,01}]
[{2号,02} -> {1号,01}]
[{3号,03} -> {2号,02} -> {1号,01}]
[{4号,04} -> {3号,03} -> {2号,02} -> {1号,01}]
[{5号,05} -> {4号,04} -> {3号,03} -> {2号,02} -> {1号,01}]
[{6号,06} -> {5号,05} -> {4号,04} -> {3号,03} -> {2号,02}]
[{2号,02} -> {6号,06} -> {5号,05} -> {4号,04} -> {3号,03}]
[{7号,07} -> {2号,02} -> {6号,06} -> {5号,05} -> {4号,04}]
可以看到第一次页面置换时把1号缓存置换出去了，然后正常情况下次应该把2号给置换出去，但是我在下次put之前进行了get(“2号”)的操作，相当于使用了一次2号缓存，所以看到2号被提到了链表最前边，这样下次put其实是把3号给置换了出去。
