HashMap居然可以和它直接合体？？？

LinkedHashMap集合继承于HashMap，学习LinkedHashMap重点对比 LinkedHashMap 与 HashMap 的异同
特别强调两者的 Entry（节点）数据结构、数据结构的不同带来的特性差异、HashMap 的后置处理机制及最少访问删除策略。

LinkedHashMap = HashMap + LinkedList ？
就像这幅图一样？

1. Entry（节点）数据结构

1.1. HashMap.Node

1. static class Node<K,V> implements Map.Entry<K,V> {
2.     final int hash;
3.     final K key;
4.     V value;
5.     Node<K,V> next;
6.     // … 构造、getKey/getValue/setValue、equals/hashCode 等 …
7. }

复制代码

字段说明：hash：key 的哈希值，key、value：存储的键值对，next：链表或树化时的链表指针。

1.2. LinkedHashMap.Entry

1. // 头节点
2. transient LinkedHashMap.Entry<K,V> head;
3. // 尾节点
4. transient LinkedHashMap.Entry<K,V> tail;
5. // 节点类
6. static class Entry<K,V> extends HashMap.Node<K,V> {
7.     Entry<K,V> before, after;  // 双向链表指针
9.     Entry(int hash, K key, V value, Node<K,V> next) {
10.         super(hash, key, value, next);
11.     }
12. }

复制代码

新增字段说明：before、after：维护插入/访问顺序的双向链表；
链表头尾：在 LinkedHashMap 中，维护一个 head 和 tail 指针，插入时追加到尾部。

LinkedHashMap 数据结构就像它的名称一样Linked + HashMap，它是在HashMap的基础上，维护了一个双向链表。这个双向链表就像LinkedList一样，可以维护节点插入的顺序。
LinkedHashMap 数据结构是两种形态共存的数据结构

• 你可以忽略双向链表，把它看做普通的HashMap；
  
• 也可以忽略HashMap，把它看作是双向链表。
  

如果你不想使用LinkedHashMap，但又想要维护HashMap的插入顺序，那你可以在HashMap.put元素后，同时将该元素保存到LinkedList.add集合，但这样就需要你确保集合一致性，比如插入和删除。这么想想，还不如直接用LinkedHashMap集合较为稳妥。

其实LinkedHashMap 一部分源码为的就是维护HashMap与双向链表的一致性，及操作过程做的一些扩展。比如：节点创建时的双向链表尾部插入和HashMap的后置处理。
1.3. 两者对比

特性HashMapLinkedHashMap底层数据结构数组 + 链表/红黑树数组 + 链表/红黑树 + 双向链表迭代顺序不保证顺序按插入顺序（或访问顺序，可选）内存开销较小较大（每个节点额外维护链表指针）适用场景一般的键值存取需要按插入或访问顺序遍历 (如 LRU 缓存)1.4. 详细的数据结构案例

通过下面的案例图，清楚地看见每个节点的指向。
假设插入顺序为：22、23、45、89、25、38、49、28
插入完成后的数据结构如图，
图中信息含义： 当前节点信息只显示key值，next为下一个映射冲突节点；before为双链结构的上一节点，after为双链结构的下一节点；绿色虚线是整个LinkedHashMap的双链结构的连接关系。

可以清楚地看到，相比HashMap每个节点都需要多维护before和after节点，LinkedHashMap也就需要更多的空间。
2. 节点创建和转化重写

2.1. 创建Entry节点

链表节点创建的同时，通过linkNodeLast(p) 方法，维护双链结构的尾部插入

1. Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
2.         LinkedHashMap.Entry<K,V> p =
3.                 new LinkedHashMap.Entry<K,V>(hash, key, value, e);
4.         linkNodeLast(p);
5.         return p;
6. }

复制代码

2.2. 树节点创建

红黑树节点创建的同时，通过linkNodeLast(p)  方法，维护双链结构的尾部插入

1. TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
2.         TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
3.         linkNodeLast(p);
4.         return p;
5. }

复制代码

2.3. 节点转化

树节点转化为Entry节点和Entry节点转化树节点都做了重写，通过transferLinks(q, t);方法完成节点转化

1. Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
2.         LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
3.         LinkedHashMap.Entry<K,V> t =
4.                 new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
5.         transferLinks(q, t);
6.         return t;
7. }
9. TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
10.         LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
11.         TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
12.         transferLinks(q, t);
13.         return t;
14. }

复制代码

这些都是多态的简单应用，HashMap 引用指向不同的实例化子类，实现不同的功能。
3. HashMap 的后置处理（post-processing）

HashMap 本身在节点插入、访问、删除后并不做额外操作。LinkedHashMap 则通过重写以下钩子方法，在插入、访问或删除时维护自己的双链表结构。
3.1. 插入后

仅在evict=true 并且removeEldestEntry(first)==true时，插入后才需要移除头部节点

1. void afterNodeInsertion(boolean evict) { // possibly remove eldest
2.         LinkedHashMap.Entry<K,V> first;
3.         if (evict && (first = head) != null && removeEldestEntry(first)) {
4.                 K key = first.key;
5.                 removeNode(hash(key), key, null, false, true);
6.         }
7. }

复制代码

3.2. 访问后

仅在 accessOrder = true 时，访问后需调整顺序；需要在LinkedHashMap 的构造方法中设定accessOrder的值。

1. void afterNodeAccess(Node<K,V> e) {
2.     LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
3.     // 将 p 移到双向链表尾部
4.     moveNodeToLast(p);
5. }

复制代码

3.3. 删除后

只要节点作删除，LinkedHashMap集合就必须删除双链表上的Entry 节点

1. void afterNodeRemoval(Node<K,V> e) {
2.     // 将 e 从双向链表中摘除
3.     unlinkNode((LinkedHashMap.Entry<K,V>)e);
4. }

复制代码

这三步合称为 后置处理，保证在 put、get、remove 等操作时，链表结构的正确维护。
但是、
为什么LinkedHashMap集合在插入完成后，需要多做一步删除头节点的操作呢？
为什么访问完成后需要将访问节点移动到双链表的尾部呢？
4. 最少访问删除策略



来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！