|
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
package
com.hanchao.test0809;
import
java.util.Hashtable;
public
class
LRUCache {
/**
* 链表节点
* @author Administrator
*
*/
class
CacheNode {
CacheNode prev;
//前一节点
CacheNode next;
//后一节点
Object value;
//值
Object key;
//键
CacheNode() {
}
}
private
int
cacheSize;
private
Hashtable nodes;
//缓存容器
private
int
currentSize;
private
CacheNode first;
//链表头
private
CacheNode last;
//链表尾
public
LRUCache(
int
i) {
currentSize =
0
;
cacheSize = i;
nodes =
new
Hashtable(i);
//缓存容器
}
/**
* 获取缓存中对象
* @param key
* @return
*/
public
Object get(Object key) {
CacheNode node = (CacheNode) nodes.get(key);
if
(node !=
null
) {
moveToHead(node);
return
node.value;
}
else
{
return
null
;
}
}
/**
* 添加缓存
* @param key
* @param value
*/
public
void
put(Object key, Object value) {
CacheNode node = (CacheNode) 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);
}
/**
* 将缓存删除
* @param key
* @return
*/
public
Object remove(Object key) {
CacheNode node = (CacheNode) nodes.get(key);
if
(node !=
null
) {
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 == node)
first = node.next;
}
return
node;
}
public
void
clear() {
first =
null
;
last =
null
;
}
/**
* 删除链表尾部节点
* 表示 删除最少使用的缓存对象
*/
private
void
removeLast() {
//链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
if
(last !=
null
) {
if
(last.prev !=
null
)
last.prev.next =
null
;
else
first =
null
;
last = last.prev;
}
}
/**
* 移动到链表头，表示这个节点是最新使用过的
* @param node
*/
private
void
moveToHead(CacheNode node) {
if
(node == first) {
//如果当前节点就是链表的头，不做处理
return
;
}
if
(node.prev !=
null
) {
//如果当前节点的前一个元素不为null,把前一个元素的下一个指向当前元素的下一个元素
node.prev.next = node.next;
}
if
(node.next !=
null
) {
//如果当前节点的后一个元素不为null,把后一个元素的前一个指向当前元素的前一个元素
node.next.prev = node.prev;
}
if
(last == node) {
//如果当前元素为最后一个元素，则最后一个元素变成当前元素的前一个元素
last = node.prev;
}
if
(first !=
null
) {
//如果第一个算不为null,则当前元素的下一个指向为原来的第一个元素
//原来的第一个元素的前一个元素变成当前元素
node.next = first;
first.prev = node;
}
first = node;
node.prev =
null
;
if
(last ==
null
) {
last = first;
}
}
}
|
参考：http://gogole.iteye.com/blog/692103
http://blog.chinaunix.net/uid-26147414-id-3435752.html
http://dennis-zane.iteye.com/blog/128278
