维护操作顺序的哈希表
LinkedHashMap是HashMap的扩展增强，保存了操作顺序(插入顺序/访问顺序)
LinkedHashMap.java1
| public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
|
实现上包含头尾链表引用
头指向最老的数据，尾指向最年轻的数据
LinkedHashMap.java1
2
3
4
5
6
|
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;
|
链表节点结构装饰器模式扩展了HashMap的节点结构，增加两个指针用来维护双端队列
LinkedHashMap.java1
2
3
4
5
6
| static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
|
HashMap实现中预留了三个空方法，分别在操作后调用，LinkedHashMap覆写了三个方法，加入扩展逻辑
HashMap.java1
2
3
| void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
|
插入顺序
默认采取插入顺序
LinkedHashMap.java1
2
3
4
| public LinkedHashMap() {
super();
accessOrder = false;
}
|
插入逻辑并没有覆写afterNodeInsertion方法，而是覆写了新建节点方法
LinkedHashMap没有单独维护链表结构，而是把HashMap所有节点都增加前后指针直接串起来，链表数据一体
LinkedHashMap.java1
2
3
4
5
| Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
|
访问顺序
一个有趣的开关是遍历顺序的控制，false时是按插入顺序，true时是按访问顺序。通常使用的都是插入顺序，要想变成访问顺序需要在构造时配置。
LinkedHashMap.java1
2
3
4
| public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
|
访问后把Entry移到链表尾部
LinkedHashMap.java1
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
| void afterNodeAccess(Node<K,V> e) {
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;
}
}
|
局限性
注意： 如果采用了访问顺序，那么get操作也会改变内部结构，因此这种模式不能进行循环遍历
Sample1
2
3
4
5
6
7
| LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>(10, 0.75f, true);
map.put("foo", 1);
map.put("bar", 2);
map.put("baz", 3);
for (String s : map.keySet()) {
map.get(s);
}
|
LRU实现
LinkedHashMap不是抽象类，但是它留了一个protected方法，面向用户的可自定义配置方法，这个方法在put或者putAll之后会被调用，也就是说数据插入后，有机会进行后处理。配合访问顺序，LinkedHashMap可以当成是天然的LRU缓存实现
LinkedHashMap.java1
2
3
4
5
6
7
8
9
10
| protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
|
注意点：泛型，负载因子，非继承实现
Sample1
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
| public class LruCache<K, V> {
private Map<K, V> cache;
public LruCache(final int capacity) {
this.cache = new LinkedHashMap<K, V>(capacity, 1, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return this.size() > capacity;
}
};
}
public V get(K key) {
return cache.get(key);
}
public void set(K key, V value) {
cache.put(key, value);
}
public Set<K> keySet() {
return cache.keySet();
}
public static void main(String[] args) {
LruCache<String, Integer> cache = new LruCache<String, Integer>(3);
cache.set("foo", 1);
cache.set("bar", 2);
cache.set("baz", 3);
cache.get("foo");
cache.get("baz");
cache.set("quz", 4);
System.out.println(cache.keySet());
}
}
|
