LinkedHashMap 实现LRU缓存
参考
LinkedHashMap是HashMap的子类，但是内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于双向链表中。LinkedHashMap支持两种顺序插入顺序 、 访问顺序
插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序
访问顺序：所谓访问指的是get/put操作，对一个键执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 其中参数accessOrder就是用来指定是否按访问顺序，如果为true，就是访问顺序。
LRU(Least Recently Used): 最近最少使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int maxEntries;
public LRUCache(int maxEntries) {
super(16, 0.75f, true);
this.maxEntries = maxEntries;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxEntries;
}
}
|
在LinkedHashMap添加元素后，会调用removeEldestEntry防范，传递的参数时最久没有被访问的键值对，如果方法返回true，这个最久的键值对就会被删除。LinkedHashMap中的实现总返回false，该子类重写后即可实现对容量的控制。
1
2
3
4
5
6
7
| LRUCache<String,Object> cache = new LRUCache<>(3);
cache.put("a","abstract");
cache.put("b","basic");
cache.put("c","call");
cache.get("a");
cache.put("d","滴滴滴");
System.out.println(cache); // 输出为：{c=call, a=abstract, d=滴滴滴}
|
相比HashMap，LinkedHashMap还实现了三个方法，当且仅当 accessOrder=True 时会被调用到
1
2
3
| void afterNodeAccess(Node<K,V> p) { } //访问节点之后调用的方法
void afterNodeInsertion(boolean evict) { } //插入节点之后调用的方法
void afterNodeRemoval(Node<K,V> p) { } //删除节点之后调用的方法
|
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
| 在get()方法中调用afterNodeAccess()方法，具体作用是：在对节点进行访问之后，会更新链表，将节点移动到链表的尾部，表示最近被访问过。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
|
1
2
3
4
5
6
7
8
9
| LinkedHashMap的put()是调用的父类HashMap的put()方法
这个方法是在HashMap中的put()方法中被调用，在LinkedHashMap中被实现，具体作用是：在插入新节点后，因为缓存不够，需要删除最近最少使用的节点。要成功调用这个方法，还需要用户覆写 removeEldestEntry(first) 方法
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 当LinkedHashMap成功调用removeNode()方法，删除节点之后，会调用本方法
具体作用是：在removeNode方法中，只是删除了HashMap中的节点，并没有在链表中删除。所以在removeNode中，回调了这个方法，将该节点从链表中删除（这里是删除的头结点，因为头结点是最早进入或者最近最久未使用的）。
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
|
