淘汰算法LRU
基于双链表实现LRU
原理： 将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。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
98public class LRUCache {
//缓存大小
private int cacheSize;
//缓存容器
private Hashtable<K, CacheNode<K, V>> nodes;
//当前缓存对象数量
private int currentSize;
//(实现双链表)链表头
private CacheNode first;
//(实现双链表)链表尾
private CacheNode last;
public LRUCache(int i) {
currentSize = 0;
cacheSize = i;
nodes = new Hashtable(i);//缓存容器
}
/**
* 链表节点
*
*/
private static class CacheNode<K,V> {
CacheNode prev;
CacheNode next;
K key;
V value;
CacheNode() {
}
}
public V get(K key){
CacheNode<K, V> node = nodes.get(key);
if(node!=null){
moveToHead(node);
return node.value;
}else{
return null;
}
}
public void put(K key, V value){
CacheNode<K, V> node = nodes.get(key);
if(node == null){
if(currentSize >= cacheSize){
if(last != null){
nodes.remove(last.key);
}
removeLast();
}else{
currentSize++;
}
node = new CacheNode<>();
}
node.value=value;
node.key=key;
moveToHead(node);
nodes.put(key, node);
}
private void removeLast(){
if(last!=null){
if(last.prev != null){
last.prev.next = null;
}else{
first = null;
}
last = last.prev;
}
}
private void moveToHead(CacheNode node){
if(node == first){
return;
}
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
if (last == node) {
last = node.prev;
}
if (first != null) {
node.next = first;
first.prev = node;
}
first = node;
node.prev = null;
if (last == null) {
last = first;
}
}
}
