共计 7003 个字符，预计需要花费 18 分钟才能阅读完成。
一、前言
LinkedHashMap 继承于 HashMap，因而，倡议在学习本篇内容前，先学习 HashMap 系列，这样使得更加容易了解。
HashMap 系列
（一）HashMap 系列：负载因子 0.75
（二）HashMap 系列：树化阀值 8，进化阀值 6
（三）HashMap 系列：2 次方扩容
（四）HashMap 系列：put 元素（不看完将悔恨毕生！）
二、LinkedHashMap 应用
可能很多人会说，LinkedHashMap 谁不会用？你真的确定你会用？
上例子之前，先写几个工具办法，以便前面了解不便：
public class Main {
// 字符串左对齐（未思考中英文长度，仅便于观看）private static String spaceFill(Object object) {return String.format("%-20s", object);
}
// 反射获取 HashMap 中的数组对象
// 啥？你不晓得数组对象名称？// 倡议去看看源码，或是看看我写的 HashMap 系列
private static Map.Entry<Integer, String>[] getArray(Object object, Field field) throws Exception {return (Map.Entry<Integer, String>[]) field.get(object);
}
// 反射获取 Map.Entry
// 因为 HashMap.Node 是公有动态类
private static Map.Entry<Integer, String> getObject(Object object, String name) throws Exception {Field field = getField(object.getClass(), name);
return (Map.Entry<Integer, String>) field.get(object);
}
// 反射获取指定字段
private static Field getField(Class<?> clazz, String name) {if (clazz == null) {return null;}
Field field = null;
try {field = clazz.getDeclaredField(name);
field.setAccessible(true);
} catch (NoSuchFieldException e) {field = getField(clazz.getSuperclass(), name);
}
return field;
}
}
复制代码好了，下面的工具办法曾经实现，前面的所有例子都会应用下面的办法。
咱们来看两个例子：
2.1、例子一
public class Main {public static void main(String[] args) {
// 个别大家都应用默认构造函数
LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
map.put(1, "chris");
map.put(2, "qingye");
map.put(3, "24854015@qq.com");
// 反射获取 table 数组对象
Field field = getField(map.getClass(), "table");
if (field != null && field.getType().isArray()) {
try {
// 类型强转
Map.Entry<Integer, String>[] table = getArray(map, field);
for (int i = 0; i < table.length; i ++) {if (table[i] != null) {
// LinkedHashMap.Node 特有的 before & after 指针
Map.Entry<Integer, String> before = getObject(table[i], "before");
Map.Entry<Integer, String> after = getObject(table[i], "after");
if (before == null) {System.out.print("This is Head");
} else if (after == null) {System.out.print("This is Tail");
} else {System.out.print("ttt");
}
System.out.println("[" + i + "] =>" + spaceFill(table[i]) + ", before =>" + spaceFill(before) + ", after =>" + spaceFill(after));
}
}
} catch (Exception e) {}}
}
}
复制代码输入后果：
This is Head [1] => 1=chris , before => null , after => 2=qingye
[2] => 2=qingye , before => 1=chris , after => 3=24854015@qq.com
This is Tail [3] => 3=24854015@qq.com , before => 2=qingye , after => null
复制代码2.2、例子二
public class Main {public static void main(String[] args) {
// 指定构造函数来初始化
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "chris");
map.put(2, "qingye");
map.put(3, "24854015@qq.com");
map.get(1); // 留神：这里仅仅 get 了一下
Field field = getField(map.getClass(), "table");
if (field != null && field.getType().isArray()) {
try {Map.Entry<Integer, String>[] table = getArray(map, field);
for (int i = 0; i < table.length; i ++) {if (table[i] != null) {Map.Entry<Integer, String> before = getObject(table[i], "before");
Map.Entry<Integer, String> after = getObject(table[i], "after");
if (before == null) {System.out.print("This is Head");
} else if (after == null) {System.out.print("This is Tail");
} else {System.out.print("ttt");
}
System.out.println("[" + i + "] =>" + spaceFill(table[i]) + ", before =>" + spaceFill(before) + ", after =>" + spaceFill(after));
}
}
} catch (Exception e) {}}
}
}
复制代码输入后果：
This is Tail [1] => 1=chris , before => 3=24854015@qq.com , after => null
This is Head [2] => 2=qingye , before => null , after => 3=24854015@qq.com
[3] => 3=24854015@qq.com , before => 2=qingye , after => 1=chris
复制代码WTF？！产生了啥？怎么 [1] 元素从『Head』变成了『Tail』？这就是 LinkedHashMap 的其妙之处！
三、深刻解读 LinkedHashMap 的神秘
3.1、LinkedHashMap 与 HashMap 的关系
本篇结尾也说了，前者继承于后者，因而，LinkedHashMap 的 putXXX 和 getXXX 都间接继承于 HashMap，并没有重载，其 put & get 的逻辑也就和 HashMap 一样。HashMap 的 put & get 是啥逻辑？如果大家遗记了，倡议去看看我写的（四）HashMap 系列：put 元素（不看完将悔恨毕生！）。既然是继承，同样的，它们的数组构造也就简直统一（99% 的统一）：
数据结构：数组 + 链表 <—> 红黑树
那 1% 的不统一在哪？
3.2、Map.Entry
HashMap 的节点实现了 Map.Entry：
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
复制代码那 LinkedHashMap 的节点呢？
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
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);
}
}
}
复制代码额，真是简略的令人发指啊！仅仅多了两个索引（指针）节点：before & after！
3.3、HashMap.TreeNode
之前再讲 HashMap 时，并没有提到 TreeNode 这个类型，因为波及到 LinkedHashMap，所以有所调整，这里进行补充：
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);
}
}
复制代码完满的继承：
3.4、before & after
依据这两个字段的名称，咱们就能很容易的猜测出，别离指向前一个节点和后一个节点（事实上，咱们结尾的两个例子，曾经证实了这种关系），那么，具体是如何在数据结构或者说，节点对象上体现出关联关系的呢？
画图很辛苦 …… LinkedHashMap 之所以加了 before 与 after 节点索引，次要目标：
- 双向链表（即能够双向拜访），从头结点能够始终遍历到最初一个节点，而不须要中途定位到桶；
- 能够依照插入程序来拜访（默认），【例子一】；
四、LinkedHashMap 非凡之处
/**
* The iteration ordering method for this linked hash map: true for access-order, false for insertion-order.
*/
final boolean accessOrder;
复制代码该字段含意：
- true 时，遍历双向链表中元素是依照拜访程序来遍历（LRU）；
- false 时，遍历双向链表中的元素是依照插入程序来遍历（默认）；
Android 零碎中的 LRU 的实现，其实就是基于 LinkedHashMap，并采纳了【例子二】的形式来初始化对象实例。
五、LinkedHashMap 索引的源码实现
咱们同样从 put 元素还是剖析源码，还记得咱们剖析 HashMap 的 putVal 时，有两个空函数么？
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
......
else {
......
if (e != null) { // 元素曾经存在
......
afterNodeAccess(e); // 调整节点程序
return oldValue;
}
}
......
afterNodeInsertion(evict); // 新增元素，调整节点程序
return null;
}
}
复制代码5.1、LinkedHashMap.afterNodeAccess
该办法会被多个其它办法触发，例如：put 一个已存在的节点对象，get 对象，replace 对象等等，该办法就是判断是否须要调整的遍历拜访程序。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// accessOrder = true，示意 LRU
// 将要挪动的节点曾经在最初一个，那么就不必调整了
if (accessOrder && (last = tail) != e) {
// p 指向 e 自身，b 指向 e 前一个，a 指向 e 后一个
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
// 如果 e 的前一个为 null，示意 e 是头节点，那么将头节点指向 e 的下一个元素
if (b == null)
head = a;
else
b.after = a; // 否则 e 的上一个元素，其下一个指向从 e 改为 e 的下一个
// a 为 null 则示意 e 是尾节点
// 否则将 e 的下一个元素，其上一个指向从 e 改为 e 的上一个
if (a != null)
a.before = b;
else
last = b; // 否则，尾节点指向 e 的上一个元素
// 总之，下面判断：b，a 不为 null，则互指
// 如果 last 为 null，则示意整个 LinkedHashMap 只有一个元素
if (last == null)
head = p;
else {
// 否则，将 p 移至最初一个（拜访程序上，即逻辑上最初一个，理论地位不会变）p.before = last;
last.after = p;
}
tail = p; // 最初，尾指向最初一个元素
++modCount;
}
}
}
复制代码5.2、LinkedHashMap.afterNodeInsertion
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 新增节点后，调用此办法判断是否须要移除最老的节点
// 因为 accessOrder = true 时，拜访次数多的节点肯定是在链尾，而拜访次数起码的则在链头
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 如果须要移除最老的，则先从链头开始移除
// 移除节点，调用的是 HashMap.removeNode 办法
// 同样是从数组开始，再红黑树，再链表查找，删除，调整
removeNode(hash(key), key, null, false, true);
}
}
}
复制代码5.3、LinkedHashMap.removeEldestEntry
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 该办法在 LinkedHashMap 中，默认返回 false，即不移除最老的元素
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}
}
复制代码那为啥我还始终提到 LRU 呢？因为，咱们如果本人基于 LinkedHashMap 来实现 LRU，就能够重载此办法，返回 true，这样就达到了 LRU 的成果。
好了，LinkedHashMap 就聊到这里！
参考：《2020 最新 Java 根底精讲视频教程和学习路线！》
链接：https://juejin.cn/post/692396…
正文完
