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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
| /**
* 基于跳表实现的LRU缓存
* 结合时间戳和跳表实现O(log n)的LRU
*/
public class SkipListLRUCache<K, V> {
/**
* 缓存项
*/
static class CacheEntry<K, V> {
K key;
V value;
long timestamp;
CacheEntry(K key, V value, long timestamp) {
this.key = key;
this.value = value;
this.timestamp = timestamp;
}
}
/**
* 时间戳跳表节点
*/
static class TimestampNode<K, V> {
CacheEntry<K, V> entry;
TimestampNode<K, V>[] forward;
@SuppressWarnings("unchecked")
TimestampNode(CacheEntry<K, V> entry, int level) {
this.entry = entry;
this.forward = new TimestampNode[level + 1];
}
@SuppressWarnings("unchecked")
TimestampNode(int level) {
this.forward = new TimestampNode[level + 1];
}
}
private final int capacity;
private final Map<K, TimestampNode<K, V>> keyToNode;
private final TimestampNode<K, V> header;
private int level;
private int size;
private final Random random;
private long currentTime;
public SkipListLRUCache(int capacity) {
this.capacity = capacity;
this.keyToNode = new HashMap<>();
this.header = new TimestampNode<>(16);
this.level = 0;
this.size = 0;
this.random = new Random();
this.currentTime = 0;
}
/**
* 获取缓存值
*/
public V get(K key) {
TimestampNode<K, V> node = keyToNode.get(key);
if (node == null) {
return null;
}
// 更新访问时间
V value = node.entry.value;
remove(node);
put(key, value);
return value;
}
/**
* 放入缓存
*/
public void put(K key, V value) {
// 如果key已存在，删除旧节点
if (keyToNode.containsKey(key)) {
TimestampNode<K, V> oldNode = keyToNode.get(key);
remove(oldNode);
}
// 如果达到容量限制，删除最旧的节点
if (size >= capacity) {
removeOldest();
}
// 插入新节点
CacheEntry<K, V> entry = new CacheEntry<>(key, value, ++currentTime);
insertNode(entry);
}
/**
* 插入新节点到跳表
*/
private void insertNode(CacheEntry<K, V> entry) {
TimestampNode<K, V>[] update = new TimestampNode[17];
TimestampNode<K, V> current = header;
// 查找插入位置
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null &&
current.forward[i].entry.timestamp < entry.timestamp) {
current = current.forward[i];
}
update[i] = current;
}
int newLevel = randomLevel();
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = header;
}
level = newLevel;
}
TimestampNode<K, V> newNode = new TimestampNode<>(entry, newLevel);
for (int i = 0; i <= newLevel; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
keyToNode.put(entry.key, newNode);
size++;
}
/**
* 删除最旧的节点
*/
private void removeOldest() {
TimestampNode<K, V> oldest = header.forward[0];
if (oldest != null) {
remove(oldest);
}
}
/**
* 删除指定节点
*/
private void remove(TimestampNode<K, V> nodeToRemove) {
TimestampNode<K, V>[] update = new TimestampNode[17];
TimestampNode<K, V> current = header;
// 查找要删除的节点
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null &&
current.forward[i].entry.timestamp < nodeToRemove.entry.timestamp) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current == nodeToRemove) {
for (int i = 0; i <= level; i++) {
if (update[i].forward[i] != current) break;
update[i].forward[i] = current.forward[i];
}
while (level > 0 && header.forward[level] == null) {
level--;
}
keyToNode.remove(nodeToRemove.entry.key);
size--;
}
}
private int randomLevel() {
int level = 0;
while (random.nextDouble() < 0.5 && level < 16) {
level++;
}
return level;
}
/**
* 显示缓存状态
*/
public void display() {
System.out.println("LRU缓存状态 (按时间戳排序):");
TimestampNode<K, V> current = header.forward[0];
while (current != null) {
System.out.println(" " + current.entry.key + " -> " +
current.entry.value + " (time: " +
current.entry.timestamp + ")");
current = current.forward[0];
}
System.out.println("缓存大小: " + size + "/" + capacity);
}
}
|