本文介绍链接混图的相关知识
我在个人资料之前就知道过HashMap，HashMap是无序的。 如果希望按顺序保存密钥值，则必须使用链接的散列。
打包收集； import java.util.HashMap； import java.util.LinkedHashMap； import java.util.Map.Entry；/* * @ author zousy * @ versionv 1.0 * @描述* @ date 2021-03-169336049 */publicclasstestlinkedhashmap { public } linkedHashmap.put('name1'，' josan1' )； linkedHashmap.put('name2'，' josan2' )； linkedHashmap.put('name3'，' josan3' )； system.out.println (' linked hashmap遍历时的顺序：')； for (输入字符串，stringentry 3360链接hashmap.entryset () string key=(字符串) entry.getKey )； stringvalue=(string ) entry.getValue )； system.out.println (' key : ' key '，value:' value )； } HashMapString，String hashMap=new HashMapString，string(16； hashmap.put('name1)、' josan1)； hashmap.put('name2)、' josan2)； hashmap.put('name3'，' josan3' )； system.out.println('Hashmap遍历时的顺序： for (输入字符串，字符串3360 hashmap.entryset ()字符串密钥=(字符串) ) stringvalue=(string ) entry.getValue )； system.out.println (' key : ' key '，value:' value )； } }
结果表明，链接散列图有序，默认为插入顺序。
构造函数public class LinkedHashMapK，V extends HashMapK，V implements MapK，v{publiclinkedhashmap(}{super ) }； //accessOrder默认为false，迭代期间的输出顺序为插入节点的顺序。 如果为true，则输出顺序为访问节点的顺序。 访问顺序=false； } publiclinkedhashmap (initial capacity ) super (initial capacity )； 访问顺序=false； //初始化时的容量和扩展的负载因子publiclinkedhashmap (intialcapacity，float loadFactor ) super(initialcapacity，loadFactor )； 访问顺序=false； } publiclinkedhashmap (intinitial capacity，float loadFactor，booleanaccessorder (super (初始容量，loadFactor ) )； this.accessOrder=accessOrder； }publiclinkedHashmap(map？ 扩展k， 扩展虚拟机({ super )； 访问
Order = false; putMapEntries(m, false); }}LinkedHashMap 继承了HashMap，实现了Map接口。
LinkedHashMap的accessOrder变量默认为false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。
数据结构Entry的next是用于维护HashMap指定table位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。
//LinkedHashMap内部类 Entry继承HashMap的Node内部类，是一个双向链表 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); } }
该循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束。
LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法.
newNode()会在HashMap的putVal()方法里被调用，putVal()方法会在批量插入数据putMapEntries(Map<? extends K, ? extends V> m, boolean evict)或者插入单个数据public V put(K key, V value)时被调用。
LinkedHashMap重写了newNode()，在每次构建新节点时，通过linkNodeLast（p），将新节点链接在内部双向链表的尾部。
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; } private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; //tail 指向尾节点即插入的节点 tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }HashMap专门预留给LinkedHashMap的afterNodeAccess() afterNodeInsertion() afterNodeRemoval() 方法。
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { } //回调函数，新节点插入之后回调 ， 根据evict 和 判断是否需要删除最老插入的节点。如果实现LruCache会用到这个方法。 void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; //LinkedHashMap 默认返回false 则不删除节点 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } //LinkedHashMap 默认返回false 则不删除节点。 返回true 代表要删除最早的节点。通常构建一个LruCache会在达到Cache的上限是返回true protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; } 删LinkedHashMap也没有重写remove()方法，因为它的删除逻辑和HashMap并无区别。
但它重写了afterNodeRemoval()这个回调方法。该方法会在Node<K,V> removeNode()方法中回调，removeNode()会在所有涉及到删除节点的方法中被调用。
更改value时，发生hash冲突，逻辑和HashMap的put逻辑一样。
查重写了HashMap的get方法，调用getNode方法，LinkedHashMap只是增加了在成员变量(构造函数时赋值)accessOrder为true的情况下，要去回调void afterNodeAccess()函数，在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last;//原尾节点 //如果accessOrder 是true ，且原尾节点不等于e if (accessOrder && (last = tail) != e) { //节点e强转成双向链表节点p LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //p现在是尾节点， 后置节点一定是null p.after = null; //如果p的前置节点是null，则p以前是头结点，所以更新现在的头结点是p的后置节点a if (b == null) head = a; else//否则更新p的前直接点b的后置节点为 a b.after = a; //如果p的后置节点不是null，则更新后置节点a的前置节点为b if (a != null) a.before = b; else//如果原本p的后置节点是null，则p就是尾节点。 此时 更新last的引用为 p的前置节点b last = b; if (last == null) //原本尾节点是null 则，链表中就一个节点 head = p; else {//否则 更新 当前节点p的前置节点为 原尾节点last， last的后置节点是p p.before = last; last.after = p; } //尾节点的引用赋值成p tail = p; //修改modCount。 ++modCount; } } containsValueLinkedHashMap重写了该方法，相比HashMap的实现，遍历双向链表更为高效。
public boolean containsValue(Object value) { for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; }对比HashMap，是用两个for循环遍历，相对低效。
public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }总结
LinkedHashMap通过继承HashMap重写了它的一些方法，实现了有序性。accessOrder ,默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。为true时，可以在这基础之上构建一个LRUCache。LinkedHashMap不是线程安全的，内部结构是哈希表+双向链表。LinkedHashMap和HashMap一样，允许一对键值为null，key不能重复，但value可以重复。参考
LinkedHashMap源码解析（JDK8）图解LinkedHashMap原理Java集合之LinkedHashMap