简体中文LinkedHashMap
LinkedHashMap(链表散列映射)是HashMap的导出类，像LinkedHashSet与HashSet的关系一样。
其与HashMap的差别在于其使用LinkedList来维护键值对插入的顺序，其插入机制和HashMap是一致的。
LinkedHashMap和HashMap的性能相差不大，与HashSet和LinkedHashSet
一致：
| 集合 | 特征 |
|---|---|
HashMap | HashMap基于散列表，插入和查询键值对的开销是固定的 |
LinkedHashMap | 和HashMap类似，不过其使用LinkedList维护内部次序，因此其迭代顺序是插入顺序或者LRU（最近最少使用）次序，性能稍差于HashMap |
元素排序 #
一般地，LinkedHashMap使用插入顺序（ insertion order ）。但有特殊情况，LinkedHashMap提供构造参数accessOrder，来根据访问顺序（ access order ）对映射条目进行迭代。
主要构造器：
1/**
2 * Constructs an empty LinkedHashMap instance with the
3 * specified initial capacity, load factor and ordering mode.
4 *
5 * @param initialCapacity the initial capacity
6 * @param loadFactor the load factor
7 * @param accessOrder the ordering mode - true for
8 * access-order, false for insertion-order
9 * @throws IllegalArgumentException if the initial capacity is negative
10 * or the load factor is nonpositive
11 */
12public LinkedHashMap(int initialCapacity,
13 float loadFactor,
14 boolean accessOrder) {
15 super(initialCapacity, loadFactor);
16 this.accessOrder = accessOrder;
17}
当使用访问顺序时，映射条目的会按照最少访问——最多访问的顺序迭代，也就是说每次有效访问，受到影响的条目都会“移动”到链表的尾部，这个性质非常适合 “最近最少使用”（LRU）高速缓存。
有效访问 #
那么哪些方法是有效访问呢？
- put
- get
- putIfAbsent
- getOrdefault
- compute
- computeIfAbsent
- computeIfPresent
- merge
- replace
其中，replace方法只有成功替换值之后才是有效访问
1static {
2 map.put("hebe", "不醉不会");
3 map.put("andy", "谢谢你的爱");
4 map.put("lala", "寻人启事");
5 map.put("yoga", "成全");
6}
7static void accessOrderTest() {
8 Map<String, String> lhm = new LinkedHashMap<>(8, 0.75f, true);
9 lhm.putAll(map);
10 System.out.println("entry in access order:");
11 // 有效访问会将entry移动至队尾
12 lhm.replace("yoga", "说谎");
13 // Java 8新增方法
14 lhm.computeIfPresent("hebe", (k, v) -> "魔鬼中的天使");
15 lhm.put("chua", "坠落");
16 lhm.get("lala");
17 lhm.forEach((k, v) -> System.out.println("\t" + k + ": " + v));
18}
19/* output:
20entry in access order:
21 andy: 谢谢你的爱
22 yoga: 说谎
23 hebe: 魔鬼中的天使
24 chua: 坠落
25 lala: 寻人启事
26*///:~
值得一提的是，对LinkedHashMap的视图操作不影响迭代顺序：
1static void viewTest() {
2 Map<String, String> lhm = new LinkedHashMap<>(8, 0.75f, true);
3 lhm.putAll(map);
4 lhm.forEach((k, v) -> System.out.println("\t" + k + ": " + v));
5 Set<Map.Entry<String, String>> entries = lhm.entrySet();
6 // 视图操作不会影响映射的排序
7 Iterator<Map.Entry<String, String>> i = entries.iterator();
8 for (Map.Entry<String, String> entry : entries) {
9 entry.setValue("魔鬼中的天使");
10 break;
11 }
12 System.out.println("------");
13 lhm.forEach((k, v) -> System.out.println("\t" + k + ": " + v));
14 i.next();
15}
16/* output:
17 hebe: 不醉不会
18 lala: 寻人启事
19 yoga: 成全
20 andy: 谢谢你的爱
21------
22 hebe: 魔鬼中的天使
23 lala: 寻人启事
24 yoga: 成全
25 andy: 谢谢你的爱
26*///：～
移除最老K-V对 #
关于LinkedHashMap的一个重要的用途，还有一个重要的方法，利用好此方法可以将LinkedHashMap作为缓存使用。
1protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
2 return false;
3}
这个方法在put或者putAll方法插入新条目到映射之后被调用，也就是说，使用put更新已有key的value不会触发此操作1。
如果方法返回false，不执行操作；返回true，则移除参数eldest条目。
参数 eldest是映射的“最旧的”元素——当前最先插入/最少访问的元素，即队头元素：
1void afterNodeInsertion(boolean evict) { // possibly remove eldest
2 LinkedHashMap.Entry<K,V> first;
3 // if true，移除队头元素
4 if (evict && (first = head) != null && removeEldestEntry(first)) {
5 K key = first.key;
6 removeNode(hash(key), key, null, false, true);
7 }
8}
不重写的前提下，removeEldestEntry方法始终返回false——也就是说永远不会作任何操作，可以继承此方法（从访问权限修饰符也知道），改变方法行为。
此法可以用来在put和putAll之后操作映射，如此做之后，此法一定要返回false，不再允许映射有后续的操作，原因很简单——若在操作时就remove了eldest，返回true之后该如何？
removeEldestEntry可以作用于插入顺序和访问顺序的LinkedeHashMap中：
1private static void eldestRemoveTest() {
2 class Access<K, V> extends LinkedHashMap<K, V> {
3 @Override
4 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
5 return size() > 1;
6 }
7 }
8 Access<Integer, String> access = new Access<>();
9 access.put(1, "apple");
10 // Access中始终只有最后插入的一个条目
11 access.put(2, "google");
12 access.forEach((k, v) -> System.out.println(k + ": " + v));
13}
14/* output
152: google
16*///:~
上例中，每次put后调用removeEldestEntry方法，最终映射中只有最后插入的条目。
1static void lruCacheTest() {
2 class Cache<K, V> extends LinkedHashMap<K, V> {
3 private final int count = 50;
4
5 private Cache(int initialCapacity, float loadFactor, boolean accessOrder) {
6 super(initialCapacity, loadFactor, accessOrder);
7 }
8
9 /**
10 * 此方法总是返回false
11 *
12 * @param eldest
13 * @return false
14 */
15 @Override
16 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
17 Set<Map.Entry<K, V>> entries = entrySet();
18 // lambda表达式中使用外部变量需要保证线程安全
19 AtomicInteger vs = new AtomicInteger();
20 entries.removeIf(next -> {
21 V value = next.getValue();
22 if (value instanceof Integer) {
23 if ((Integer) value > 0) {
24 vs.addAndGet((Integer) value);
25 return (Integer) value < 10;
26 }
27 }
28 return false;
29 });
30 // 打印次数反映此法的调用次数
31 System.out.println(vs.intValue() == count);
32 //若在此方法中对集合进行修改，那么必须返回false
33 return false;
34 }
35 }
36 Cache<Integer, Integer> cache = new Cache<>(8, 0.75f, true);
37 // 初始化映射集， afterNodeInsertion
38 cache.put(1, 0);
39 cache.put(2, 0);
40 cache.put(3, 0);
41 cache.put(4, 0);
42 cache.put(5, 0);
43 for (int i = 0; i < cache.count; i++) {
44 int key = new Random().nextInt(50) % 5 + 1;
45 int value = cache.get(key);
46 if (i == cache.count - 1) {
47 //保证最后一次访问removeEldestEntry方法
48 cache.remove(key);
49 }
50 // 将值增1，实现计数器效果
51 // 此处不能使用compute方法，因此法会调用afterNodeInsertion
52 // 设计的目的在最后一次put之后调用afterNodeInsertion方法，而使用compute会调用2次
53// cache.put(key, cache.compute(key, (k, v) -> Integer.sum(value, 1)));
54 cache.put(key, ++value);
55
56 }
57 System.out.println("-------");
58
59 cache.forEach((k, v) -> System.out.println(k + ": " + v));
60}
61/* output:
62false
63false
64false
65false
66false
67true
68-------
691: 11
702: 12
714: 14
72*///:~
上例对一个容量为5的LinkedList进行50次随机访问，每次访问后记录访问次数（用value自增），最后删除访问次数不到10次的条目。可以看到，removeEldestEntry方法调用了6次，最后映射集中只有访问次数大于10次的键值对了。
如何链接节点 #
我们知道，LinkedHashMap在HashMap的基础上使用LinkedList（并不是集合框架中的LinkedList，独立实现）将键值对链接起来，因此键值对才能够被有序迭代，那么这一动作是在什么时候发生的呢？
这一过程涉及到2个方法：
1// 覆盖了HashMap的newNode方法
2Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
3 LinkedHashMap.Entry<K,V> p =
4 new LinkedHashMap.Entry<K,V>(hash, key, value, e);
5 // 链接节点
6 linkNodeLast(p);
7 return p;
8}
9// link at the end of list
10private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
11 LinkedHashMap.Entry<K,V> last = tail;
12 tail = p;
13 if (last == null)
14 head = p;
15 else {
16 p.before = last;
17 last.after = p;
18 }
19}
上面的两个方法可以看到，每次插入键值对到映射中时，总会和前一个节点建立连接。
回调方法 #
LinkedHashMap中有3个重要的回调方法，是LinkedHashMap维护链表以及实现顺序迭代的重要依赖。
afterNodeRemoval #
1// 删除键值对之后调用
2void afterNodeRemoval(Node<K,V> e) { // unlink
3 LinkedHashMap.Entry<K,V> p =
4 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
5 p.before = p.after = null;
6 if (b == null){
7 // e = head
8 head = a;
9 }else{
10 // 将b.after指向a
11 b.after = a;
12 }
13 if (a == null){
14 // e = tail
15 tail = b;
16 }else{
17 // 将a.before指向b
18 a.before = b;
19 }
20 // 连接完成
21}
afterNodeInsertion #
1// 插入新节点之后调用
2void afterNodeInsertion(boolean evict) { // possibly remove eldest
3 LinkedHashMap.Entry<K,V> first;
4 // 注意判断条件，需要removeEldestEntry方法返回true
5 // removeEldestEntry方法默认返回false
6 //因此默认行为是不删除节点
7 if (evict && (first = head) != null && removeEldestEntry(first)) {
8 K key = first.key;
9 // 移除队头节点
10 removeNode(hash(key), key, null, false, true);
11 //will call afterNodeRemoval
12 }
13}
afterNodeAccess #
如果构造LinkedHashMap时指定构造参数accessOrder=true，那么此法将访问的节点移动至队尾
1void afterNodeAccess(Node<K,V> e) { // move node to last
2 LinkedHashMap.Entry<K,V> last;
3 // 访问顺序，且访问节点不为tail
4 if (accessOrder && (last = tail) != e) {
5 LinkedHashMap.Entry<K,V> p =
6 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
7 // 置空p.after，因要将p放到队尾
8 p.after = null;
9 if (b == null){
10 // b == null说明e==head
11 head = a;
12 }else{
13 // 将e的前一节点与e的后一节点连接
14 b.after = a;
15 }
16 if (a != null){
17 // 将e的后一节点与e的前一节点连接
18 a.before = b;
19 }else{
20 // 这个条件会被满足吗？
21 last = b;
22 }
23 if (last == null){
24 // 这个条件会被满足吗
25 head = p;
26 }else {
27 // 将p作为最后节点
28 p.before = last;
29 last.after = p;
30 }
31 tail = p;
32 ++modCount;
33 }
34}
上述方法的流程图为：
实际上使用
put方法更新已有键值对时，触发的是另一个方法：afterNodeAccess，此方法将条目移动至队尾（如果使用访问顺序）。 ↩︎
