面试官请说下对理解HashMap及LinkedHashMap的理解（八股文）

　　HashMap是Map族中最为常用的一种，也是Java Collection Framework的重要成员。HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Node节点链入一个双向链表的HashMap。
　　下面基于JDK 1.8的源码来学习HashMap及LinkedHashMap的数据结构、原理。不同JDK版本之间也许会有些许差异，但不影响原理学习，JDK8相比以前对HashMap的修改比较大。  1、HashMap概述
　　Map是 Key-Value键值对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。HashMap是Java Collection Framework的重要成员，也是Map族(如下图所示)中我们最为常用的一种。
　　简单地说，HashMap是基于哈希表的Map接口的实现，以Key-Value的形式存在，即存储的对象是 Node (同时包含了Key和Value) 。
　　在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地，HashMap最多只允许一条Node的key为Null，但允许多条Node的value为Null。此外，HashMap是Map 的一个非同步的实现。
　　以下是HashMap的类继承图
　　必须指出的是，虽然容器号称存储的是 Java 对象，但实际上并不会真正将 Java 对象放入容器中，只是在容器中保留这些对象的引用。也就是说，Java 容器实际上包含的是引用变量，而这些引用变量指向了我们要实际保存的 Java 对象。  1.1、HashMap定义及构造函数
　　JDK中的定义为  public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {     //... }
　　HashMap 一共提供了四个构造函数，其中 默认无参的构造函数 和 参数为Map的构造函数 为 Java Collection Framework 规范的推荐实现，其余两个构造函数则是 HashMap 专门提供的。  public HashMap(int initialCapacity) {     this(initialCapacity, DEFAULT_LOAD_FACTOR); } //仅仅将负载因子初始化为默认值 public HashMap() {     this.loadFactor = DEFAULT_LOAD_FACTOR;      // all other fields defaulted }
　　HashMap(int initialCapacity, float loadFactor)构造函数意在构造一个指定初始容量和指定负载因子的空HashMap，其源码如下：  public HashMap(int initialCapacity, float loadFactor) {     if (initialCapacity < 0)         throw new IllegalArgumentException(＂Illegal initial capacity: ＂ +                                            initialCapacity);     //容量最大为2的30次方     if (initialCapacity > MAXIMUM_CAPACITY)         initialCapacity = MAXIMUM_CAPACITY;     if (loadFactor <= 0 || Float.isNaN(loadFactor))         throw new IllegalArgumentException(＂Illegal load factor: ＂ +                                            loadFactor);     this.loadFactor = loadFactor;     //这里调用函数计算触发扩容的阈值，threshold/loadFactor就是容量     this.threshold = tableSizeFor(initialCapacity); }
　　以上构造函数的最后一行就是jdk8的修改，实际上在jdk7之前的版本，这个构造方法最后一行就是：  table = new Entry[capacity];
　　但是jdk8的最后一行并没有立刻new出一个数组，而是调用了tableSizeFor方法，将结果赋值给了threshold变量。tableSizeFor方法源码如下，从注释就可以看出来，其目的是要获得大于cap的最小的2的幂。比如cap=10，则返回16。  /**  * Returns a power of two size for the given target capacity.  */ static final int tableSizeFor(int cap) {     int n = cap - 1;     n |= n >>> 1;     n |= n >>> 2;     n |= n >>> 4;     n |= n >>> 8;     n |= n >>> 16;     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } 1.2、HashMap的数据结构
　　我们知道，在Java中最常用的两种结构是数组和链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap就是这种应用的一个典型。
　　实际上，经典的HashMap就是一个链表数组，只是jdk1.8再次对经典hashMap的数据结构作了小幅调整，如下是当前HaspMap的数据结构：
　　在JDK1.6和JDK1.7中，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的key-value键值对都存储在一个链表里。但是当数组中一个位置上的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
　　而在JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值8时，并且数组总容量超过64时，将链表转换为红黑树，这样大大减少了查找时间。从链表转换为红黑树后新加入键值对的效率降低，但查询、删除的效率都变高了。而当发生扩容或remove键值对导致原有的红黑树内节点数量小于6时，则又将红黑树转换成链表。
　　每一个HashMap都有一个Node类型的table数组，其中Node类型的定义如下：  static class Node implements Map.Entry {     final int hash;         // 声明 hash 值为 final 的     final K key;            // 声明 key 为 final 的     V value;                // 键值对的值     Node next;         // 指向下一个节点的引用      Node(int hash, K key, V value, Node next) {         this.hash = hash;         this.key = key;         this.value = value;         this.next = next;     } }
　　Node为HashMap的内部类，实现了Map.Entry接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。事实上，Node是构成哈希表的基石，是哈希表所存储的元素的具体形式。值得注意的是，int类型的hash值及引用变量key都被声明成final，即不可变。  1.3、HashMap的快速存取
　　在HashMap中，我们最常用的两个操作就是：put(Key,Value)和get(Key)。我们都知道，HashMap中的Key是唯一的，那它是如何保证唯一性的呢？
　　我们首先想到的是用equals比较，没错，这样是可以实现的，但随着元素的增多，put和get的效率将越来越低，这里的时间复杂度是O(n)。也就是说，假如HashMap有1000个元素，那么put时就需要比较1000次，这是相当耗时的，远达不到HashMap快速存取的目的。
　　实际上，HashMap很少会用到equals方法，因为其内通过一个哈希表管理所有元素，利用哈希算法可以快速的存取元素。当我们调用put方法存值时，HashMap首先会调用Key的hashCode方法，然后基于此值获取Key的哈希码，通过哈希码快速找到某个位置，这个位置可以被称之为 bucketIndex。
　　根据equals方法与hashCode的协定可以知道，如果两个对象的hashCode不同，那么equals一定为 false；如果其hashCode相同，equals也不一定为true。所以，理论上，hashCode 可能存在碰撞的情况，当碰撞发生时，这时会取出bucketIndex桶内已存储的元素（如果该桶next引用不空，即有了链表也要遍历链表），并通过hashCode()和equals()来逐个比较以判断Key是否已存在。
　　如果已存在，则使用新Value值替换旧Value值，并返回旧Value值；如果不存在，则存放新的键值对到链表中。因此，在HashMap中，equals()方法只有在哈希码碰撞时才会被用到。
　　结合源码来看HashMap的put操作：  public V put(K key, V value) {     return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                boolean evict) {     Node[] tab; Node p; int n, i;     //第一次put元素时，table数组为空，先调用resize生成一个指定容量的数组     if ((tab = table) == null || (n = tab.length) == 0)         n = (tab = resize()).length;     //hash值和n-1的与运算结果为桶的位置，如果该位置空就直接放置一个Node     if ((p = tab[i = (n - 1) & hash]) == null)         tab[i] = newNode(hash, key, value, null);     //如果计算出的bucket不空，即发生哈希冲突，就要进一步判断     else {         Node e; K k;         //判断当前Node的key与要put的key是否相等         if (p.hash == hash &&             ((k = p.key) == key || (key != null && key.equals(k))))             e = p;         //判断当前Node是否是红黑树的节点         else if (p instanceof TreeNode)             e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);         //以上都不是，说明要new一个Node，加入到链表中         else {             for (int binCount = 0; ; ++binCount) {              //在链表尾部插入新节点，注意jdk1.8是在链表尾部插入新节点                 if ((e = p.next) == null) {                     p.next = newNode(hash, key, value, null);                     // 如果当前链表中的元素大于树化的阈值，进行链表转树的操作                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                         treeifyBin(tab, hash);                     break;                 }                 //在链表中继续判断是否已经存在完全相同的key                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k))))                     break;                 p = e;             }         }         //走到这里，说明本次put是更新一个已存在的键值对的value         if (e != null) { // existing mapping for key             V oldValue = e.value;             if (!onlyIfAbsent || oldValue == null)                 e.value = value;             //在hashMap中，afterNodeAccess方法体为空，交给子类去实现             afterNodeAccess(e);             return oldValue;         }     }     ++modCount;     //如果当前size超过临界值，就扩容。注意是先插入节点再扩容     if (++size > threshold)         resize();     //在hashMap中，afterNodeInsertion方法体为空，交给子类去实现     afterNodeInsertion(evict);     return null; }
　　通过上述源码我们可以清楚了解到HashMap保存数据的过程。先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则查找是否存在相同的key，若存在则覆盖原来key的value， 否则将该元素保存在链表尾部，注意JDK1.7中采用的是头插法，即每次都将冲突的键值对放置在链表头，这样最初的那个键值对最终就会成为链尾，而JDK1.8中使用的是尾插法。  此外，若table在该处没有元素，则直接保存。
　　对于hash函数，具体的来看下源码  static final int hash(Object key) {     int h;     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
　　以上可以看到 key==null 时，直接返回0，所以HashMap中键为NULL的键值对，一定在第一个桶中。
　　h >>> 16 是用来取出h的高16位(>>>是无符号右移) 如下展示： 0000 0100 1011 0011  1101 1111 1110 0001   >>> 16    0000 0000 0000 0000  0000 0100 1011 0011
　　通过之前putVal的源码可以知道，HashMap是用 (length - 1) & hash 来计算数组下标的。绝大多数情况下length一般都小于2^16 即小于65536。所以hash & (length-1)； 结果始终是hash的低16位与（length-1）进行& 运算。要是能让hash的高16位也参与运算，会让得到的下标更加散列。
　　如何让高16也参与运算呢。方法就是让hashCode()和自己的高16位进行 ^ 运算。由于与运单和或运单都会使得结果偏向0或者1，并不是均匀的概念，所以用异或。
　　结合源码来看HashMap的get操作：  public V get(Object key) {     Node e;     return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node getNode(int hash, Object key) {     Node[] tab; Node first, e; int n; K k;     if ((tab = table) != null && (n = tab.length) > 0 &&         (first = tab[(n - 1) & hash]) != null) {         if (first.hash == hash && // always check first node             ((k = first.key) == key || (key != null && key.equals(k))))             return first;         if ((e = first.next) != null) {          //如果是红黑树，就调用树的查找方法，否则遍历链表直到找到             if (first instanceof TreeNode)                 return ((TreeNode)first).getTreeNode(hash, key);             do {                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k))))                     return e;             } while ((e = e.next) != null);         }     }     return null; }
　　在这里能够根据key快速的取到value，除了和HashMap的数据结构密不可分外，还和Node有莫大的关系。在前面就已经提到过，HashMap在存储过程中并没有将key/value分开来存储，而是当做一个整体key-value来处理的，这个整体就是Node对象。  1.4 为什么HashMap的底层数组长度总是2的n次方
　　当底层数组的length为2的n次方时，  hash & (length - 1)  就相当于对length取模，其效率要比直接取模高得多，这是HashMap在效率上的一个优化。
　　我们希望HashMap中的元素存放的越均匀越好。最理想的效果是，Node数组中每个位置都只有一个元素，这样，查询的时候效率最高，不需要遍历单链表，也不需要通过equals去比较Key，而且空间利用率最大。
　　那如何计算才会分布最均匀呢？正如上一节提到的，HashMap采用了一个分两步走的哈希策略：  使用  hash()  方法用于对Key的hashCode进行重新计算，以防止质量低下的hashCode() 函数实现。由于hashMap的支撑数组长度总是2的倍数，通过右移可以使低位的数据尽量的不同，从而使Key的hash值的分布尽量均匀；使用 hash & (length - 1)  方法进行取余运算，以使每个键值对的插入位置尽量分布均匀；
　　由于length是2的整数幂，length-1的低位就全是1，高位全部是0。在与hash值进行低位&运算时，低位的值总是与原来hash值相同，高位&运算时值为0。这就保证了不同的hash值发生碰撞的概率比较小，这样就会使得数据在table数组中分布较均匀，查询速度也较快。  1.5 HashMap的扩容
　　随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证HashMap的效率， 系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（ table数组长度*加载因子 ）。 但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。
　　首先回答一个问题，在插入一个临界节点时，HashMap是先扩容后插入还是先插入后扩容？这样选取的优势是什么？
　　答案是： 先插入后扩容。通过查看putVal方法的源码可以发现是先执行完新节点的插入后，然后再做size是否大于threshold的判断的。  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                boolean evict) {   ...     //如果插入新结点后的size超过了临界值，就扩容，注意是先插入节点再扩容     if (++size > threshold)         resize();     //在hashMap中，afterNodeInsertion方法体为空，交给子类去实现     afterNodeInsertion(evict);     return null; }
　　为什么是先插入后扩容？源码已经很清楚的表达了扩容原因，调用put不一定是新增数据，还可能是覆盖掉原来的数据，这里就存在一个key的比较问题。推荐：Java面试题宝典
　　以先扩容为例， 先比较是否是新增的数据，再判断增加数据后是否要扩容，这样比较会浪费时间，而先插入后扩容，就有可能在中途直接通过return返回了（本次put是覆盖操作，size不变不需要扩容），这样可以提高效率的。
　　JDK1.8相对于JDK1.7对HashMap的实现有较大改进，做了很多优化，链表转红黑树是其中的一项，其实扩容方法JDK1.8也有优化，与JDK1.7有较大差别。
　　JDK1.8中resize方法源码如下：  final Node[] resize() {     Node[] oldTab = table;     int oldCap = (oldTab == null) ? 0 : oldTab.length;     int oldThr = threshold;     int newCap, newThr = 0;     if (oldCap > 0) {      // 原来的容量就已经超过最大值就不再扩容了，就只好随你碰撞去吧         if (oldCap >= MAXIMUM_CAPACITY) {             threshold = Integer.MAX_VALUE;             return oldTab;         }         // 没超过最大值，就扩容为原来的2倍         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                  oldCap >= DEFAULT_INITIAL_CAPACITY)             newThr = oldThr << 1; // double threshold     }     else if (oldThr > 0) // initial capacity was placed in threshold         newCap = oldThr;     else {               // zero initial threshold signifies using defaults         newCap = DEFAULT_INITIAL_CAPACITY;         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);     }     // 计算新的resize上限，即新的threshold值     if (newThr == 0) {         float ft = (float)newCap * loadFactor;         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                   (int)ft : Integer.MAX_VALUE);     }     threshold = newThr;     @SuppressWarnings({＂rawtypes＂,＂unchecked＂})         Node[] newTab = (Node[])new Node[newCap];     table = newTab;     if (oldTab != null) {      // 把旧的bucket都移动到新的buckets中         for (int j = 0; j < oldCap; ++j) {             Node e;             if ((e = oldTab[j]) != null) {                 oldTab[j] = null;                 if (e.next == null)                     newTab[e.hash & (newCap - 1)] = e;                 else if (e instanceof TreeNode)                     ((TreeNode)e).split(this, newTab, j, oldCap);                 else { // preserve order                     Node loHead = null, loTail = null;                     Node hiHead = null, hiTail = null;                     Node next;                     do {                         next = e.next;                         //原来的桶索引值                         if ((e.hash & oldCap) == 0) {                             if (loTail == null)                                 loHead = e;                             else                                 loTail.next = e;                             loTail = e;                         }                         else {                             if (hiTail == null)                                 hiHead = e;                             else                                 hiTail.next = e;                             hiTail = e;                         }                     } while ((e = next) != null);                     // 扩容后，键值对在新table数组中的位置与旧数组中一样                     if (loTail != null) {                         loTail.next = null;                         newTab[j] = loHead;                     }                     // 扩容后，键值对在新table数组中的位置与旧数组中不一样                     // 新的位置=原来的位置 + oldCap                     if (hiTail != null) {                         hiTail.next = null;                         newTab[j + oldCap] = hiHead;                     }                 }             }         }     }     return newTab; }
　　必要的位置已经加了注释。最让人疑惑的有两个点：  为什么 （e.hash & oldCap）== 0 时就放入lo链表，否则就是hi链表;为什么  j + oldCap 就是键值对在新的table数组中的位置；
　　其实这里包含着一些数学技巧。类似于上一小节为什么HashMap中数组的长度总是取2的整数次幂。
　　查看源码，我们发现扩容时，使用的是2次幂的扩展即长度扩为原来2倍，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
　　看下图可以明白这句话的意思，n为table的长度，图中上半部分表示扩容前的key1和key2两个Node的索引位置，图中下半部分表示扩容后key1和key2两个Node新的索引位置。
　　元素在重新计算hash之后，因为n变为2倍，那么n-1在高位多1bit，因此新的index就会发生这样的变化：
　　因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成＂原索引+oldCap＂，这个设计确实非常的巧妙，既省去了重新hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了，这一块就是JDK1.8新增的优化点。  1.6 HashMap为什么引入红黑树而不是AVL树
　　上面这个问题也可以理解为：有了二叉查找树、平衡树（AVL）为啥还需要红黑树？
　　二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：  若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 任意节点的左、右子树也分别为二叉查找树; 没有键值相等的节点（no duplicate nodes）
　　因为一棵由N个结点随机构造的二叉查找树的高度为logN，所以顺理成章，二叉查找树的一般操作的执行时间为O(logN)。但二叉查找树若退化成了一棵具有N个结点的线性链后，则这些操作最坏情况运行时间为O(N)。
　　可想而知，我们不能让这种情况发生，为了解决这个问题，于是我们引申出了平衡二叉树，即AVL树，它对二叉查找树做了改进，在我们每插入一个节点的时候，必须保证每个节点对应的左子树和右子树的树高度差不超过1。如果超过了就对其进行左旋或右旋，使之平衡。
　　虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logN)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
　　显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。 红黑树是不符合AVL树的平衡条件的，即每个节点的左子树和右子树的高度最多差1的二叉查找树，但是提出了为节点增加颜色，红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，相较于AVL树为了维持平衡的开销要小得多。
　　AVL树是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多， 所以红黑树的插入效率相对于AVL树更高。单单在查找方面比较效率的话，由于AVL高度平衡，因此AVL树的查找效率比红黑树更高。
　　对主要的几种平衡树作个比较，发现红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。实际应用中，若搜索的频率远远大于插入和删除，那么选择AVL，如果发生搜索和插入删除操作的频率差不多，应该选择红黑树。  1.7 HashMap的线程不安全
　　所有人都知道HashMap是线程不安全的，我们应该使用ConcurrentHashMap。但是为什么HashMap是线程不安全的呢？
　　首先需要强调一点， HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环和数据丢失是在JDK1.7中出现的问题，在JDK1.8中已经得到解决，然而1.8中仍会有数据覆盖的问题，即在并发执行HashMap的put操作时会发生数据覆盖的情况。
　　首先扩容会造成HashMap的线程不安全，根源就在JDK1.7的transfer函数中。transfer方法将原有Entry数组的元素拷贝到新的Entry数组里。JDK1.7中HashMap的transfer函数源码如下：  void transfer(Entry[] newTable) {  //src引用了旧的Entry数组  Entry[] src = table;   int newCapacity = newTable.length;  //遍历旧的Entry数组  for (int j = 0; j < src.length; j++) {   //取得旧Entry数组的每个元素   Entry e = src[j];    if (e != null) {   src[j] = null;   //释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）   do {    Entry next = e.next;    int i = indexFor(e.hash, newCapacity);     //重新计算每个元素在数组中的位置    e.next = newTable[i]; //标记[1]    newTable[i] = e; //将元素放在数组上    e = next;     //访问下一个Entry链上的元素    } while (e != null);   }  } }
　　这段代码是HashMap的扩容操作，重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。 头插法会将链表的顺序翻转，这也是在多线程环境下会形成死循环的关键点。  扩容造成死循环和数据丢失的详细过程这里不再赘述，可以搜索很多分析这个过程的文章。
　　JDK1.8的源码中已经没有transfer函数，因为JDK1.8直接在resize函数中完成了数据迁移。此外JDK1.8在进行元素插入时使用的是尾插法。为什么多线程环境下JDK1.8的HashMap会出现数据覆盖的情况呢，我们来看一下JDK1.8中的putVal源码：  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                boolean evict) {     Node[] tab; Node p; int n, i;     //第一次put元素时，table数组为空，先调用resize生成一个指定容量的数组     if ((tab = table) == null || (n = tab.length) == 0)         n = (tab = resize()).length;     //hash值和n-1的与运算结果为桶的位置，如果该位置空就直接放置一个Node     if ((p = tab[i = (n - 1) & hash]) == null)         tab[i] = newNode(hash, key, value, null);     //如果计算出的bucket不空，即发生哈希冲突，就要进一下判断     else {         Node e; K k;         //判断当前Node的key与要put的key是否相等         if (p.hash == hash &&             ((k = p.key) == key || (key != null && key.equals(k))))             e = p;         //判断当前Node是否是红黑树的节点         else if (p instanceof TreeNode)             e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);         //以上都不是，说明要new一个Node，加入到链表中         else {             for (int binCount = 0; ; ++binCount) {              //进入这个if说明是到达链表尾部                 if ((e = p.next) == null) {                     p.next = newNode(hash, key, value, null);                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                         treeifyBin(tab, hash);                     break;                 }                 //在链表中继续判断是否已经存在完全相同的key                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k))))                     break;                 p = e;             }         }         //走到这里，说明本次put是更新一个已存在的键值对的value         if (e != null) { // existing mapping for key             V oldValue = e.value;             if (!onlyIfAbsent || oldValue == null)                 e.value = value;             //在hashMap中，afterNodeAccess方法体为空，交给子类去实现             afterNodeAccess(e);             return oldValue;         }     }     //下面两个自增操作都不是原子的     ++modCount;     if (++size > threshold)         resize();     //在hashMap中，afterNodeInsertion方法体为空，交给子类去实现     afterNodeInsertion(evict);     return null; }
　　其中 if((p = tab[i = (n - 1) & hash]) == null) 是判断是否出现hash碰撞，假设两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完这行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所以此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。
　　除此之外，还有就是代码的末尾部分有个++size，我们这样想，还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的size大小为10，当线程A执行到size自增这行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，由于size不是volatile修改的变量，然后线程A再次拿到CPU后不会再从主内存中加载一次size的值，而是使用自己工作内存中的副本，继续执行加1，当执行完put操作后，还是将size=11写回主内存，此时，线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。推荐：Java面试题宝典  2、LinkedHashMap概述
　　HashMap是Java Collection Framework的重要成员，也是Map族中我们最为常用的一种。不过遗憾的是，HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。
　　庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序==。特别地，==该迭代顺序可以是插入顺序，也可以是访问顺序。
　　因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap和保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。
　　更直观地，下图很好地还原了LinkedHashMap的原貌：HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。特别需要注意的是，next用于维护HashMap各个桶中的Entry链，before、after用于维护LinkedHashMap的双向链表，虽然它们的作用对象都是Entry，但是各自分离，是两码事儿。
　　特别地，由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。
　　此外，LinkedHashMap 也是 Map 的一个非同步的实现。此外，LinkedHashMap还可以用来实现LRU (Least recently used, 最近最少使用)算法。  2.1、LinkedHashMap定义及构造函数
　　本质上，HashMap和双向链表合二为一即是LinkedHashMap。JDK1.8中LinkedHashMap的定义源码如下：  public class LinkedHashMap     extends HashMap     implements Map {  /**   * HashMap.Node subclass for normal LinkedHashMap entries.   */  static class Entry extends HashMap.Node {   //再加两个引用，分别指向前一个插入的Entry与后一个插入的Entry      Entry before, after;      Entry(int hash, K key, V value, Node next) {          super(hash, key, value, next);      }  }    /**   * The head (eldest) of the doubly linked list.   * 头节点引用   */  transient LinkedHashMap.Entry head;    /**   * The tail (youngest) of the doubly linked list.   * 尾节点引用   */  transient LinkedHashMap.Entry tail;    /**   * The iteration ordering method for this linked hash map: true   * for access-order, false for insertion-order.   * true表示按照访问顺序迭代，false时表示按照插入顺序    * @serial   */  final boolean accessOrder;   ...  }
　　LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了Entry。LinkedHashMap中的Entry继承了HashMap.Node，但增加了两个指针before 和 after，它们分别用于维护双向链接列表。 特别需要注意的是，next用于维护HashMap各个Node的连接顺序，before、after用于维护Entry插入的先后顺序。
　　LinkedHashMap的5大构造函数都是在HashMap的构造函数的基础上实现的，分别如下：  public LinkedHashMap(int initialCapacity, float loadFactor) {     super(initialCapacity, loadFactor);     accessOrder = false; }   public LinkedHashMap(int initialCapacity) {     super(initialCapacity);     accessOrder = false; }   public LinkedHashMap() {     super();     accessOrder = false; }   public LinkedHashMap(Map<? extends K, ? extends V> m) {     super();     accessOrder = false;     putMapEntries(m, false); }  public LinkedHashMap(int initialCapacity,                      float loadFactor,                      boolean accessOrder) {     super(initialCapacity, loadFactor);     this.accessOrder = accessOrder; } 2.2、LinkedHashMap的快速存取
　　在HashMap中最常用的两个操作就是： put(Key,Value)  和 get(Key)。同样地，在 LinkedHashMap 中最常用的也是这两个操作。对于put(Key,Value) 方法而言，LinkedHashMap完全继承了HashMap的 put(Key,Value)  方法，只是对putVal(hash,key, value, onlyIfAbsent,evict) 方法所调用的afterNodeAccess方法和afterNodeInsertion方法进行了重写；对于get(Key)方法，LinkedHashMap则直接对它进行了重写。
　　下面我们结合JDK源码看 LinkedHashMap 的存取实现。
　　HashMap的putVal源码，上一节中已经分析过，直接来看LinkedHashMap对afterNodeAccess和afterNodeInsertion方法的实现：  void afterNodeInsertion(boolean evict) { // possibly remove eldest     LinkedHashMap.Entry first;     if (evict && (first = head) != null && removeEldestEntry(first)) {         K key = first.key;         removeNode(hash(key), key, null, false, true);     } }   /**  * 如果map应该删除最老的节点，返回true  * 这个方法在被put和putAll方法被调用，当向map中插入一个新的entry时被执行。这个方法提供了当一个新的entry被添加到linkedHashMap中，删除最老节点的机会。  *   * 这个方法是很有用的，可以通过删除最老节点来减少内存消耗，避免溢出。  *   * 简单的例子：这个方法的重写将map的最大值设为100，到100时，每次增一个entry，就删除一次最老节点。  *   *     private static final int MAX_ENTRIES = 100;  *  *     protected boolean removeEldestEntry(Map.Entry eldest) {  *        return size() > MAX_ENTRIES;  *     }  *  * 这个方法一般不会直接修改map，而是通过返回true或者false来控制是否修改map。  *  *  * @param    eldest 最老的节点（即头节点）  * @return   如果map应该删除头节点就返回true，否则返回false  */ protected boolean removeEldestEntry(Map.Entry eldest) {     return false; }
　　以上afterNodeInsertion方法由于removeEldestEntry方法默认一直返回的false而无执行意义。也就意味着如果想要让它有意义必须重写removeEldestEntry方法。  void afterNodeAccess(Node e) { // move node to last     LinkedHashMap.Entry last;     if (accessOrder && (last = tail) != e) {         LinkedHashMap.Entry p =             (LinkedHashMap.Entry)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;     } }
　　可见仅有accessOrder为true时，且访问节点不等于尾节点时，该方法才有意义。通过before/after重定向，将新访问节点链接为链表尾节点。推荐：Java面试题宝典
　　LinkedHashMap的get操作：  public V get(Object key) {     Node e;     if ((e = getNode(hash(key), key)) == null)         return null;     //当accessOrder为true时，才会出现个性化逻辑     if (accessOrder)         afterNodeAccess(e);     return e.value; }   //以下是HashMap中的getNode方法 final Node getNode(int hash, Object key) {     Node[] tab; Node first, e; int n; K k;     if ((tab = table) != null && (n = tab.length) > 0 &&         (first = tab[(n - 1) & hash]) != null) {         if (first.hash == hash && // always check first node             ((k = first.key) == key || (key != null && key.equals(k))))             return first;         if ((e = first.next) != null) {             if (first instanceof TreeNode)                 return ((TreeNode)first).getTreeNode(hash, key);             do {                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k))))                     return e;             } while ((e = e.next) != null);         }     }     return null; }
　　在LinkedHashMap的get方法中，通过HashMap中的getNode方法获取Node对象。
　　注意这里的afterNodeAccess方法，如果链表中元素的排序规则是按照插入的先后顺序排序的话，该方法什么也不做；如果链表中元素的排序规则是按照访问的先后顺序排序的话，则将e移到链表的末尾处。  2.3、LinkedHashMap与LRU算法
　　到此为止，我们已经分析完了LinkedHashMap的存取实现，这与HashMap大体相同。LinkedHashMap区别于HashMap最大的一个不同点是，前者是有序的，而后者是无序的。为此，LinkedHashMap增加了两个属性用于保证顺序，分别是双向链表头结点header和标志位accessOrder。我们知道，header是LinkedHashMap所维护的双向链表的头结点，而accessOrder用于决定具体的迭代顺序。
　　我们知道，当accessOrder标志位为true时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序，但put和get方法均有判断accessOrder的值。
　　如果accessOrder为true，put时将新插入的元素放入到双向链表的尾部，get时将当前访问的Entry移到双向链表的尾部。当标志位accessOrder的值为false时，表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序，即每次put到LinkedHashMap中的Entry都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序。
　　测试代码  @Test public void testLinkedHashMap() {     Map map = new HashMap<>(128);     System.out.println(＂------HashMap------＂);     map.put(＂first＂, ＂a＂);     map.put(＂second＂, ＂b＂);     map.put(＂third＂, ＂c＂);     map.put(＂fourth＂, ＂d＂);     map.put(＂fifth＂, ＂e＂);     map.put(＂sixth＂, ＂f＂);     map.forEach((key,value) -> {         System.out.println(＂key=＂ + key + ＂,value=＂ + value);     });      map.clear();     System.out.println(＂------LinkedHashMap------＂);     map = new LinkedHashMap<>(128);     map.put(＂first＂, ＂a＂);     map.put(＂second＂, ＂b＂);     map.put(＂third＂, ＂c＂);     map.put(＂fourth＂, ＂d＂);     map.put(＂fifth＂, ＂e＂);     map.put(＂sixth＂, ＂f＂);      map.forEach((key,value) -> {         System.out.println(＂key=＂ + key + ＂,value=＂ + value);     }); }
　　运行结果如下，HashMap不保证有序而LinkedHashMap默认按迭代顺序和插入的顺序一致。
　　前面介绍的LinkedHashMap的五种构造方法，前四个构造方法都将accessOrder设为false，说明默认是按照插入顺序排序的；而第五个构造方法可以自定义传入的accessOrder的值。当我们要用LinkedHashMap实现LRU算法时，就需要调用该构造方法并将accessOrder置为true。
　　使用LinkedHashMap实现LRU的必要前提是将accessOrder标志位设为true以便开启按访问顺序排序的模式。我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此就把该Entry加入到了双向链表的末尾。这样，我们便把最近使用的Entry放入到了双向链表的后面。多次操作后，双向链表前面的Entry便是最近没有使用的，这样当节点个数满的时候，删除最前面的Entry即可，因为它就是最近最少使用的Entry。  public class SomeTest {     @Test     public void testLru() {         LRU lru = new LRU<>(8);         String s = ＂abcdefghijkl＂;         for (int i = 0; i < s.length(); i++) {             lru.put(s.charAt(i), i + 1);         }         System.out.println(＂LRU的大小： ＂ + lru.size());         System.out.println(lru);         System.out.println(＂LRU的中key为h的value值： ＂ + lru.get(＂h＂));         System.out.println(lru);         lru.put(＂z＂, 26);         System.out.println(lru);     }      public static class LRU extends LinkedHashMap {          private int cacheSize;          public LRU(int cacheSize) {             super(cacheSize, 0.75f, true);             this.cacheSize = cacheSize;         }          /**          * 重写LinkedHashMap中的removeEldestEntry方法，当LRU中元素多余cacheSize个时，删除最老的节点（即最不经常使用的元素）          * @param eldest          * @return          */         protected boolean removeEldestEntry(Map.Entry eldest) {             return size() > getCacheSize();         }          public int getCacheSize() {             return cacheSize;         }      } }
　　运行结果：  LRU的大小：8 {e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12} LRU的中key为h的value值：8 {e=5, f=6, g=7, i=9, j=10, k=11, l=12, h=8} {f=6, g=7, i=9, j=10, k=11, l=12, h=8, z=26}