数组+链表+红黑树 HashMap -- hashtable concurrenthashmap

绝地灬酷狼 2022-03-12 13:28 184阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> &nbsp; *hashmap相关问题 参考 :&nbsp;&nbsp;<a href="http://www.importnew.com/7099.html" rel="nofollow">http://www.importnew.com/7099.html</a> <a href="https://www.cnblogs.com/heyonggang/p/9112731.html" rel="nofollow">https://www.cnblogs.com/heyonggang/p/9112731.html</a>&nbsp;[待学习] *hashmap底层源码,很多时候还是要看源码,源码看一次可能记不住,在这里记录几篇参考的文章 源码参考&nbsp;<a href="https://blog.csdn.net/weixin_28774815/article/details/80640540" rel="nofollow">https://blog.csdn.net/weixin_28774815/article/details/80640540</a>（数组加链表） 图解参考2&nbsp;&nbsp;<a href="https://blog.csdn.net/carson_ho/article/details/79373134" rel="nofollow">https://blog.csdn.net/carson_ho/article/details/79373134</a>&nbsp;HashMap 在 JDK 1.8 后新增的红黑树结构 hashmap 根据value来查找 //遍历所有key 再比较value符合的值 <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//普遍使用(通过key取value)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code>&nbsp;<code>(Object&nbsp;key&nbsp;:&nbsp;map.keySet())&nbsp;{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(key&nbsp;+&nbsp;</code><code>"---"</code>&nbsp;<code>+&nbsp;map.get(key));</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//推荐，尤其是容量大时</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(Map.Entry&lt;Object,Object&gt;&nbsp;entry&nbsp;:&nbsp;map.entrySet()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(entry.getKey()&nbsp;+&nbsp;</code><code>"==="</code>&nbsp;<code>+&nbsp;entry.getValue());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>根据value反查key</code> <code>&nbsp; private static ArrayList valueGetKey(Map map,String value) { &nbsp; &nbsp; Set set = map.entrySet(); &nbsp; &nbsp; ArrayList arr = new ArrayList&lt;&gt;(); &nbsp; &nbsp; Iterator it = set.iterator(); &nbsp; &nbsp; while(it.hasNext()) { &nbsp; &nbsp; &nbsp; Map.Entry entry = (Map.Entry)it.next(); &nbsp; &nbsp; &nbsp; if(entry.getValue().equals(value)) { &nbsp; &nbsp; &nbsp; &nbsp; int s = (int)entry.getKey(); &nbsp; &nbsp; &nbsp; &nbsp; arr.add(s); &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; } &nbsp; &nbsp; return arr; &nbsp; }</code> </td> 
 </tr> 
 </tbody> 
</table>

### hashmap ###

**在jdk1.7和jdk1.8结构上的区别 : **

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 1][]

**以上是jdk1.7hashmap结构图**

存储第一个entry的位置叫‘桶（bucket）’而桶中只能存一个值也就是链表的头节点

源码发现HashMap在底层将key\_value对当成一个整体进行处理（Entry 对象）这个整体就是一个Entry对象，当系统决定存储HashMap中的key\_value对时，完全没有考虑Entry中的value，而仅仅是根据key的hash值来决定每个Entry的存储位置。**时间复杂度在最差情况下会退化到O(n)**

**JDK1.8中使用一个Node数组来存储数据**，但这个Node可能是链表结构，也可能是红黑树结构如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用**treeifyBin函数**，**将链表转换为红黑树。**那么即使hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要**O(log n)**的开销 ; **也就是说put/get的操作的时间复杂度最差只有O(log n)**。

需要注意：**key的对象**，必须**正确的实现了Compare接口 **

如果没有实现Compare接口，或者实现得不正确（比方说所有Compare方法都返回0）; 那JDK1.8的HashMap其实还是慢于JDK1.7的

> 为什么要这么操作呢？
> 
> 应该是**为了避免Hash Collision DoS攻击**
> 
> Java中String的hashcode函数的强度很弱，有心人可以很容易的构造出大量hashcode相同的String对象。
> 
> 如果向服务器一次提交数万个hashcode相同的字符串参数，那么可以很容易的卡死JDK1.7版本的服务器。
> 
> 但是**String正确的实现了Compare接口**，因此在JDK1.8版本的服务器上，**Hash Collision DoS不会造成不可承受的开销。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 2][]

**\*[关键是定位问题--定位到哈希桶数组索引的位置:][--]**

整个过程本质上就是三步：

1.  拿到**key的hashCode**值
2.  将hashCode的高位参与运算，重新计算hash值//在**JDK1.8的实现中，还优化了高位运算的算法**，将hashCode的高16位与hashCode进行异或运算，主要是为了在table的length较小的时候，让高位也参与运算，并且不会有太大的开销。
3.  将计算出来的hash值与(table.length - 1)进行&运算 查找桶的位置//取模运算 为了分布均匀 -->之前有算法题输出也是防止输出数组范围过大

**对应put方法只是在根据key和buckets数组的长度(jdk1.7,在1.8中为**table.length**)查找到位置后 , 需要添加一步 : 如果key的哈希值相同，Hash冲突（也就是指向了同一个桶）则每次新添加的作为头节点，而最先添加的在表尾。**

**hashmap的get方法**

> 1.  先对table进行校验，校验是否为空，length是否大于0
> 2.  使用table.length - 1和hash值进行位与运算，得出在table上的索引位置，将该索引位置的节点赋值给first节点，校验该索引位置是否为空（即上图的2 ,6位置的情况）
> 3.  检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点
> 4.  如果first的next节点不为空则继续遍历
> 5.  如果first节点为TreeNode，则调用getTreeNode方法（见下）查找目标节点
> 6.  如果first节点不为TreeNode，则调用普通的遍历链表方法查找目标节点
> 7.  如果查找不到目标节点则返回空

<table> 
 <tbody> 
 <tr> 
 <td> getTreeNode方法 
 <ol> 
 <li>找到调用此方法的节点的树的根节点</li> 
 <li>使用该树的根节点调用find方法</li> 
 <li>将p(根节点)节点赋值为调用此方法的节点</li> 
 <li>如果传入的hash值小于p节点的hash值，则往p节点的左边遍历，否则往p节点的右边遍历</li> 
 <li>如果传入的hash值等于p节点的hash值，并且传入的key值跟p节点的key值相等, 则该p节点即为目标节点，返回p节点</li> 
 <li>如果p的左节点为空则向右遍历，反之如果p的右节点为空则向左遍历</li> 
 <li>如果传入的key（即代码中的参数变量k）所属的类实现了Comparable接口（kc不为空，comparableClassFor方法见<a href="https://blog.csdn.net/v123411739/article/details/78996181" rel="nofollow">https://blog.csdn.net/v123411739/article/details/78996181</a>），则将传入的key跟p节点的key进行比较（kc实现了Comparable接口，因此通过kc的比较方法进行比较），并将比较结果赋值给dir，如果dir&lt;0则代表k&lt;pk，则向p节点的左边遍历（pl）；否则，向p节点的右边遍历（pr）。</li> 
 <li>代码走到此处，代表key所属类没有实现Comparable，因此直接指定向p的右边遍历，如果能找到目标节点则返回</li> 
 <li>代码走到此处代表与第7点向右遍历没有找到目标节点，因此直接向左边遍历</li> 
 <li>以上都找不到目标节点则返回空</li> 
 </ol></td> 
 </tr> 
 </tbody> 
</table>

> 面试中关于HashMap的时间复杂度O(1)的思考               [https://blog.csdn.net/donggua3694857/article/details/64127131/][https_blog.csdn.net_donggua3694857_article_details_64127131]
> 
> get方法(搜索)-4步
> 
> 1.判断key，根据**key算出索引**。   
> 2.根据索引**获得索引位置所对应的键值对链表**。   
> 3.**遍历键值对链表**，根据key找到对应的Entry键值对。   
> 4.拿到value。   
> 分析： 以上四步要保证HashMap的时间复杂度O(1)，需要保证每一步都是O(1)，现在看起来就第三步对链表的循环的时间复杂度影响最大，链表查找的时间复杂度为O(n)，与链表长度有关。我们要保证那个链表长度为1，才可以说时间复杂度能满足O(1)。但这么说来只有那个hash算法尽量减少冲突，才能使链表长度尽可能短，理想状态为1。因此可以得出结论：HashMap的查找时间复杂度只有在最理想的情况下才会为O(1)，而要保证这个理想状态不是我们开发者控制的。  
>

**hashmap的put方法**

> 1.  校验table是否为空或者length等于0，如果是则调用resize方法进行初始化
> 2.  通过hash值计算索引位置，将该索引位置的头节点赋值给p节点，如果该索引位置节点为空则使用传入的参数新增一个节点并放在该索引位置
> 3.  判断p节点的key和hash值是否跟目标相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点
> 4.  如果p节点不是目标节点，则判断p节点是否为TreeNode，如果是则调用红黑树的putTreeVal方法([https://blog.csdn.net/v123411739/article/details/78996181][https_blog.csdn.net_v123411739_article_details_78996181])查找目标节点
> 5.  走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，并定义变量binCount来统计该链表的节点数
> 6.  如果p的next节点为空时，则代表找不到目标节点，则新增一个节点并插入链表尾部，并校验节点数是否超过8个，如果超过则调用treeifyBin方法链表节点转为红黑树节点
> 7.  如果遍历的e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环
> 8.  如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue
> 9.  如果插入节点后节点数超过阈值，则调用resize方法进行扩容

> put 方法 : 计算hash值 根据hash值与table.length 得到在table中的位置index (bucketindex) ; 接着在Entry<>e不为空时,遍历对应位置从头开始遍历链表 找到key改value并返回Oldvalue 否则add Entry<>,还要判断是否超量resize

**hashmap的resize方法**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 3][]

> 1. 如果老表的容量大于0，判断老表的容量是否超过最大容量值：如果超过则将阈值设置为Integer.MAX\_VALUE，并直接返回老表（此时oldCap \* 2比Integer.MAX\_VALUE大，因此无法进行重新分布，只是单纯的将阈值扩容到最大）；如果容量 \* 2小于最大容量并且不小于16，则将阈值设置为原来的两倍<常见情况>。
> 2. 如果老表的容量为0，老表的阈值大于0，这种情况是传了容量的new方法创建的空表，将新表的容量设置为老表的阈值（这种情况发生在新创建的HashMap第一次put时，该HashMap初始化的时候传了初始容量，由于HashMap并没有capacity变量来存放容量值，因此传进来的初始容量是存放在threshold变量上（查看HashMap(int initialCapacity, float loadFactor)方法），因此此时老表的threshold的值就是我们要新创建的HashMap的capacity，所以将新表的容量设置为老表的阈值。
> 3. 如果老表的容量为0，老表的阈值为0，这种情况是没有传容量的new方法创建的空表，将阈值和容量设置为默认值。
> 4. 如果新表的阈值为空，则通过新的容量 \* 负载因子获得阈值（这种情况是初始化的时候传了初始容量，跟第2点相同情况，也只有走到第2点才会走到该情况）。
> 5. 将当前阈值设置为刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将当前的表设置为新定义的表。---------\-------以上主要关注计算阈值和容量-------
> 6. 如果老表不为空，则需遍历所有节点，将节点赋值给新表。
> 7. 将老表上索引为j的头结点赋值给e节点，并将老表上索引为j的节点设置为空。
> 8. 如果e的next节点为空，则代表老表的该位置只有1个节点，通过hash值计算新表的索引位置，直接将该节点放在新表的该位置上。
> 9. 如果e的next节点不为空，并且e为TreeNode，则调用split方法（[https://blog.csdn.net/v123411739/article/details/78996181][https_blog.csdn.net_v123411739_article_details_78996181]）进行hash分布。
> 10. 如果e的next节点不为空，并且e为普通的链表节点，则进行普通的hash分布。
> 11. 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）**进行位与运算为0**，则说明e节点扩容后的索引位置**跟老表的索引位置一样**，进行链表拼接操作：如果loTail为空，代表该节点为第一个节点，则将loHead赋值为该节点；否则将节点添加在loTail后面，并将loTail赋值为新增的节点。
> 12. 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）进行位与运算为1，则说明e节点扩容后的索引位置为：老表的索引位置＋oldCap，进行链表拼接操作：如果hiTail为空，代表该节点为第一个节点，则将hiHead赋值为该节点；否则将节点添加在hiTail后面，并将hiTail赋值为新增的节点。
> 13. 老表节点重新hash分布在新表结束后，如果loTail不为空（说明老表的数据有分布到新表上原索引位置的节点），则将最后一个节点的next设为空，并将新表上原索引位置的节点设置为对应的头结点；如果hiTail不为空（说明老表的数据有分布到新表上原索引+oldCap位置的节点），则将最后一个节点的next设为空，并将新表上索引位置为原索引+oldCap的节点设置为对应的头结点。
> 14. 返回新表。

final Node<K,V>[] resize() {
 Node<K,V>[] oldTab = table;
 int oldCap = (oldTab == null) ? 0 : oldTab.length;
 int oldThr = threshold;
 int newCap, newThr = 0;
 if (oldCap > 0) { // 老table不为空
 if (oldCap >= MAXIMUM_CAPACITY) { // 老table的容量超过最大容量值
 threshold = Integer.MAX_VALUE; // 设置阈值为Integer.MAX_VALUE
 return oldTab;
 }
 // 如果容量*2<最大容量并且>=16, 则将阈值设置为原来的两倍
 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 oldCap >= DEFAULT_INITIAL_CAPACITY) 
 newThr = oldThr << 1; // double threshold
 }
 else if (oldThr > 0) // 老表的容量为0, 老表的阈值大于0, 是因为初始容量被放入阈值
 newCap = oldThr;	// 则将新表的容量设置为老表的阈值 
 else {	// 老表的容量为0, 老表的阈值为0, 则为空表，设置默认容量和阈值
 newCap = DEFAULT_INITIAL_CAPACITY; 
 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab; // 将当前的表赋值为新定义的表
 if (oldTab != null) { // 如果老表不为空, 则需遍历将节点赋值给新表
 for (int j = 0; j < oldCap; ++j) {
 Node<K,V> e;
 if ((e = oldTab[j]) != null) { // 将索引值为j的老表头节点赋值给e
 oldTab[j] = null; // 将老表的节点设置为空, 以便垃圾收集器回收空间
 // 如果e.next为空, 则代表老表的该位置只有1个节点, 
 // 通过hash值计算新表的索引位置, 直接将该节点放在该位置
 if (e.next == null) 
 newTab[e.hash & (newCap - 1)] = e;
 else if (e instanceof TreeNode)
 	 // 调用treeNode的hash分布(跟下面最后一个else的内容几乎相同)
 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
 else { // preserve order
 Node<K,V> loHead = null, loTail = null; // 存储跟原索引位置相同的节点
 Node<K,V> hiHead = null, hiTail = null; // 存储索引位置为:原索引+oldCap的节点
 Node<K,V> next;
 do {
 next = e.next;
 //如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样
 if ((e.hash & oldCap) == 0) { 
 if (loTail == null) // 如果loTail为空, 代表该节点为第一个节点
 loHead = e; // 则将loHead赋值为第一个节点
 else 
 loTail.next = e; // 否则将节点添加在loTail后面
 loTail = e; // 并将loTail赋值为新增的节点
 }
 //如果e的hash值与老表的容量进行与运算为1,则扩容后的索引位置为:老表的索引位置＋oldCap
 else { 
 if (hiTail == null) // 如果hiTail为空, 代表该节点为第一个节点
 hiHead = e; // 则将hiHead赋值为第一个节点
 else
 hiTail.next = e; // 否则将节点添加在hiTail后面
 hiTail = e; // 并将hiTail赋值为新增的节点
 }
 } while ((e = next) != null);
 if (loTail != null) {
 loTail.next = null; // 最后一个节点的next设为空
 newTab[j] = loHead; // 将原索引位置的节点设置为对应的头结点
 }
 if (hiTail != null) {
 hiTail.next = null; // 最后一个节点的next设为空
 newTab[j + oldCap] = hiHead; // 将索引位置为原索引+oldCap的节点设置为对应的头结点
 }
 }
 }
 }
 }
 return newTab;
 }

**以上源码分析的原文(棒 学习)：[https://blog.csdn.net/v123411739/article/details/78996181][https_blog.csdn.net_v123411739_article_details_78996181]\--->深入 (再学习)**

### TreeMap ###

**红黑树是一种近似平衡的二叉查找树**，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。具体来说，红黑树是满足如下条件的二叉查找树（binary search tree）：

1.  每个节点要么是红色，要么是黑色。
2.  根节点必须是黑色
3.  红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4.  对于每个节点，从该点至null（树尾端）的任何路径，都含有**相同个数的黑色节点**。

在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的条件。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 4][]

TreeMap的底层使用了红黑树来实现，**像TreeMap对象中放入一个key-value 键值对时，就会生成一个Entry对象，这个对象就是红黑树的一个节点，**其实这个和HashMap是一样的，一个Entry对象作为一个节点，只是这些节点存放的方式不同。

存放每一个Entry对象时都会按照key键的大小按照二叉树的规范进行存放，所以**TreeMap中的数据是按照key从小到大排序**的。

TreeMap总结：

程序添加新节点时，**总是从树的根节点开始比较，即将根节点当成当前节点。**如果新增节点大于当前节点并且当前节点的右节点存在，则以右节点作为当前节点，如果新增节点小于当前节点并且当前节点的左子节点存在，则以左子节点作为当前节点；如果新增节点等于当前节点，则用新增节点覆盖当前节点，并结束循环 直到某个节点的左右子节点不存在，将新节点添加为该节点的子节点。如果新节点比该节点大，则添加其为右子节点。如果新节点比该节点小，则添加其为左子节点；

### JDK1.8版本的hashmap ###

### **jdk1.8之后hashmap底层更新 结构为数组+链表+红黑树** ###

什么情况下使用红黑树---->链表长度大于8转为红黑树

具体分析

参考源码分析帖 [https://blog.csdn.net/carson\_ho/article/details/79373134][https_blog.csdn.net_carson_ho_article_details_79373134]

以及 [https://blog.csdn.net/v123411739/article/details/78996181][https_blog.csdn.net_v123411739_article_details_78996181] 以及 [https://blog.csdn.net/wushiwude/article/details/75331926][https_blog.csdn.net_wushiwude_article_details_75331926]

<table> 
 <tbody> 
 <tr> 
 <td> <h3>*使用红黑树的原因</h3> JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。 针对这种情况，JDK 1.8 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题。 &nbsp; 红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的，以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，而这虽然会导致红黑树的查询会比AVL稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。 在HashMap中的应用：HashMap在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion方法）或删除平衡调整（balanceDeletion ）方法，调整的方式主要有以下手段：左旋转（rotateLeft方法）、右旋转（rotateRight方法）、改变节点颜色（x.red =&nbsp;false、x.red = true），进行调整的原因是为了维持红黑树的数据结构。 &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

JDK 1.8 中 HashMap 中除了链表节点：Node, 属性有hash key value Node<>next

还有另外一种节点：TreeNode，属性有 TreeNode<>parent, left, right, prev  boolean red

另外由于它继承自 LinkedHashMap.Entry ，而 LinkedHashMap.Entry 继承自 HashMap.Node ，因此还有额外的 6 个属性：

hash key value Node<>next  Entry<>before,after

>HashMap 在 JDK 1.8 中新增的操作：桶的树形化 treeifyBin()

如果一个桶中的元素个数超过 TREEIFY\_THRESHOLD(默认是 8 )，就使用红黑树来替换链表，从而提高速度。

<table> 
 <tbody> 
 <tr> 
 <td> &nbsp; <img alt="" height="264" src="https://img-blog.csdnimg.cn/20190411101809448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70" width="347"><img alt="" height="272" src="https://img-blog.csdnimg.cn/20190411101839538.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70" width="691"> HashMap 中有三个关于红黑树的关键参数: 
 <ol> 
 <li> //一个桶的树化阈值 </li> 
 <li> //当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点 </li> 
 <li> //这个值必须为 8，要不然频繁转换效率也不高 </li> 
 <li> static final int TREEIFY_THRESHOLD = 8; </li> 
 <li>&nbsp;</li> 
 <li> //一个树的链表还原阈值 </li> 
 <li> //当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构 </li> 
 <li> //这个值应该比上面那个小，至少为 6，避免频繁转换 </li> 
 <li> static final int UNTREEIFY_THRESHOLD = 6; </li> 
 <li>&nbsp;</li> 
 <li> //哈希表的最小树形化容量 = = 转红黑树时, table的最小长度 </li> 
 <li> //当哈希表中的容量大于这个值时，表中的桶才能进行树形化 </li> 
 <li> //否则桶内元素太多时会扩容，而不是树形化 </li> 
 <li> //为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD </li> 
 <li> static final int MIN_TREEIFY_CAPACITY = 64; </li> 
 </ol>JDK1.8 如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 )，就使用红黑树来替换链表，从而提高速度。 <a href="https://blog.csdn.net/wushiwude/article/details/75331926" rel="nofollow">这个替换的方法叫 treeifyBin() 即(桶的)树形化。</a> 
 <ul> 
 <li>根据哈希表中元素个数确定是扩容还是树形化</li> 
 <li>如果是树形化&nbsp; 
 <ul> 
 <li>遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系</li> 
 <li>然后让桶第一个元素指向新建的树头结点，替换桶的链表内容为树形内容</li> 
 </ul></li> 
 <li>在 最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树</li> 
 </ul>红黑树的添加元素方法 putTreeVal() ,红黑树节点的 getTreeNode() 方法 ,当扩容时，如果当前桶中元素结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD （默认为 6），就会把桶中的树形结构缩小或者直接还原（切分）为链表结构，调用的就是 split()(树的修剪方法) [HashMap 扩容时对红黑树节点的修剪主要分两部分，先分类、再根据元素个数(是否大于6)决定是还原成链表还是精简一下元素仍保留红黑树结构]&nbsp; 这里红黑树在hashmap中的方法学习参考&nbsp;<a href="https://blog.csdn.net/wushiwude/article/details/75331926" rel="nofollow">https://blog.csdn.net/wushiwude/article/details/75331926</a> </td> 
 </tr> 
 </tbody> 
</table>

> \***HashMap的table为什么是transient的** (转自 [https://blog.csdn.net/lixiaoxiong55/article/details/73308882][https_blog.csdn.net_lixiaoxiong55_article_details_73308882])
> 
> 一个非常细节的地方：`transient Entry[] table;`看到table用了transient修饰，也就是说table里面的内容全都不会被序列化，不知道大家有没有想过这么写的原因？
> 
> 这么写是非常必要的,因为HashMap是基于HashCode的，HashCode作为Object的方法，是native的：`public native int hashCode();`这意味着的是：HashCode和底层实现相关，不同的虚拟机可能有不同的HashCode算法。
> 
> 这就有问题了，Java自诞生以来，就以[跨平台][Link 1]性作为最大卖点，好了，如果table不被transient修饰，在虚拟机A上可以用的程序到虚拟机B上可以用的程序就不能用了，失去了跨平台性，
> 
> \***HashMap和Hashtable的区别**
> 
> 1、Hashtable是线程安全的，Hashtable所有对外提供的方法都使用了synchronized，也就是同步，而HashMap则是线程非安全的
> 
> 2、Hashtable不允许空的value，空的value将导致空指针异常，而HashMap则无所谓，没有这方面的限制
> 
> 3、上面两个缺点是最主要的区别，另外一个区别[无关紧要][Link 2]，就是两个的rehash算法不同
> 
> <table> 
> <tbody> 
> <tr> 
> <td> 4.另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。 5.HashMap不能保证随着时间的推移Map中的元素次序是不变的。 要注意的一些重要术语： 1) sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁，其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。 2) Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator，然后其它的线程试图“结构上”更改集合对象，将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的，因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改，再调用set()方法，将会抛出IllegalArgumentException异常。 &gt;HashMap可以通过下面的语句进行同步： Map m = Collections.synchronizeMap(hashMap); 转自&nbsp;<a href="http://www.importnew.com/7010.html" rel="nofollow">http://www.importnew.com/7010.html</a> &nbsp; “HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，或者错误的认为仅仅只在bucket中存储值的话，你将不会回答如何从HashMap中获取对象的逻辑。 </td> 
> </tr> 
> </tbody> 
> </table>
> 
> 1. HashMap的默认初始容量为16，Hashtable为11。
> 2. HashMap的扩容为原来的2倍，Hashtable的扩容为原来的2倍加1。(扩容因子都是一样0.75)
> 3. HashMap的hash值重新计算过，Hashtable直接使用hashCode。
> 4. HashMap去掉了Hashtable中的contains方法。
> 5. **HashMap继承自AbstractMap类(都实现map cloneable serializable接口)，Hashtable继承自Dictionary类。**
> 6. HashMap在触发扩容后，阈值会变为原来的2倍，并且会进行重hash，重hash后索引位置index的节点的新分布位置最多只有两个：原索引位置或原索引+oldCap位置。例如capacity为16，索引位置5的节点扩容后，只可能分布在新报索引位置5和索引位置21（5+16）。  ------>  导致HashMap扩容后，同一个索引位置的节点重hash最多分布在两个位置的根本原因是：1）table的长度始终为2的n次方；2）索引位置的计算方法为“(table.length - 1) & hash”。HashMap扩容是一个比较耗时的操作，定义HashMap时尽量给个接近的初始容量值。
> 7. HashMap有threshold属性和loadFactor属性，但是没有capacity属性。初始化时，如果传了初始化容量值，该值是存在threshold变量，并且Node数组是在第一次put时才会进行初始化，初始化时会将此时的threshold值作为新表的capacity值，然后用capacity和loadFactor计算新表的真正threshold值。
> 8. 当同一个索引位置的节点在增加后达到**9个**时，会触发链表节点（Node）转红黑树节点（TreeNode，间接继承Node），转成红黑树节点后，其实链表的结构还存在，通过next属性维持。链表节点转红黑树节点的具体方法为源码中的treeifyBin(Node<K,V>\[\] tab, int hash)方法。
> 9. 当同一个索引位置的节点在移除后达到**6个**时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的untreeify(HashMap<K,V> map)方法。
> 10. **HashMap在JDK1.8之后不再有死循环的问题，JDK1.8之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。**
> 11. HashMap是非线程安全的，在并发场景下使用ConcurrentHashMap来代替。

以上参考 : [https://blog.csdn.net/v123411739/article/details/78996181][https_blog.csdn.net_v123411739_article_details_78996181]

\***一个hashmap的题 ** ([https://www.cnblogs.com/BBchao/p/7878699.html][https_www.cnblogs.com_BBchao_p_7878699.html])

面试题：初始构造器设置大小为25，hashmap实际大小是多少？

实际是64，首先，找到比25大的2^n，是32，负载因子为0.75，则能装24个，25>24，触发扩容，为64

\* HashMap 中 String、Integer 这样的包装类适合作为 key 键

包装类都是final类型保证了key/hash的不可更改性

### \*\***hashmap扩容机制、线程安全问题 (主要是线程安全问题)** ###

> **HashMap的resize（rehash）：**最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
> 
> 当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)\*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16\*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
> 
> <table> 
> <tbody> 
> <tr> 
> <td> //HashMap数组扩容&nbsp; ---&gt;1.7版本? void resize(int newCapacity) { &nbsp;&nbsp;&nbsp;&nbsp;Entry[] oldTable = table; &nbsp;&nbsp;&nbsp;&nbsp;int oldCapacity = oldTable.length; &nbsp;&nbsp;&nbsp;&nbsp;//如果当前的数组长度已经达到最大值，则不在进行调整 &nbsp;&nbsp;&nbsp;&nbsp;if (oldCapacity == MAXIMUM_CAPACITY) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;threshold = Integer.MAX_VALUE; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;//根据传入参数的长度定义新的数组 &nbsp;&nbsp;&nbsp;&nbsp;Entry[] newTable = new Entry[newCapacity]; &nbsp;&nbsp;&nbsp;&nbsp;//按照新的规则，将旧数组中的元素转移到新数组中 &nbsp;&nbsp;&nbsp;&nbsp;transfer(newTable); &nbsp;&nbsp;&nbsp;&nbsp;table = newTable; &nbsp;&nbsp;&nbsp;&nbsp;//更新临界值 &nbsp;&nbsp;&nbsp;&nbsp;threshold = (int)(newCapacity * loadFactor); } //旧数组中元素往新数组中迁移 void transfer(Entry[] newTable) { &nbsp;&nbsp;&nbsp;&nbsp;//旧数组 &nbsp;&nbsp;&nbsp;&nbsp;Entry[] src = table; &nbsp;&nbsp;&nbsp;&nbsp;//新数组长度 &nbsp;&nbsp;&nbsp;&nbsp;int newCapacity = newTable.length; &nbsp;&nbsp;&nbsp;&nbsp;//遍历旧数组 &nbsp;&nbsp;&nbsp;&nbsp;for (int j = 0; j &lt; src.length; j++) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Entry&lt;K,V&gt; e = src[j]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (e != null) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;src[j] = null; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Entry&lt;K,V&gt; next = e.next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int i = indexFor(e.hash, newCapacity);//放在新数组中的index位置 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e.next = newTable[i];//实现链表结构，新加入的放在链头，之前的的数据放在链尾 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;newTable[i] = e; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e = next; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} while (e != null); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} } 线程不安全 在hashmap做put操作。现在假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。 &nbsp; <img alt="" height="351" src="https://img-blog.csdnimg.cn/20190411151722187.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70" width="661"> </td> 
> </tr> 
> </tbody> 
> </table>
> 
> **jdk1.8版本中多线程put不会在出现死循环问题**了，只有可能出现数据丢失的情况，因为1.8版本中，会将原来的链表结构保存在节点e中，将原来数组中的位置置为null，然后依次遍历e,根据hash&n是否等于0,分成两条支链，保存在新数组中。**如果有新的线程继续添加元素，则扩容操作中可能就会取到null值造成数据丢失，后来线程返回的扩容以后的数组将替换掉前面有可能正确进行扩容的数组。jdk1.7版本中，扩容过程中会新数组会和原来的数组有指针引用关系，所以将引起死循环问题\[带图的例子**[https://coolshell.cn/articles/9606.html][https_coolshell.cn_articles_9606.html]**\]。---->并发进行put操作 而非get工作--->** 在于`HashMap` 线程不安全的其中一个重要原因：多线程下容易出现`resize（）`死循环 本质 = 并发 执行 `put（）`操作导致触发 扩容行为，从而导致 环形链表，使得在获取数据遍历链表时形成死循环，即`Infinite Loop`
> 
> \*JDK1.8版本put尾插法
> 
> `1\链表遍历查找元素是比较慢的，在HashMap中put元素发现数组桶位上已有元素，接着遍历桶位上的链表查找是否有相同key的过程称为hash碰撞，这是比较耗性能的。`而为了避免链表过长遍历时间过大的问题，在JDK1.8采用了数据+链表+红黑树的结构。在往链表上新增元素时发现链表长度超过8时，会进入链表转红黑树的方法，然后再判断数组长度是否不小于64，若满足条件则将链表转化为红黑树。
> 
> `2、至于JDK1.8的链表插入元素为什么改为了尾插法，则是为了避免出现逆序且链表死循环的问题（JDK1.7的HashMap扩容导致死循环了解哈）。` 
>  
> 
> <table> 
> <tbody> 
> <tr> 
> <td> final Node&lt;K,V&gt;[] resize() { //--&gt;1.8版本? &nbsp; &nbsp; &nbsp; &nbsp; //oldTab保存原来的table &nbsp; &nbsp; &nbsp; &nbsp; Node&lt;K,V&gt;[] oldTab = table; &nbsp; &nbsp; &nbsp; &nbsp; //原来数组的长度 &nbsp; &nbsp; &nbsp; &nbsp; int oldCap = (oldTab == null) ? 0 : oldTab.length; &nbsp; &nbsp; &nbsp; &nbsp; //原来数组的阈值&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int oldThr = threshold; &nbsp; &nbsp; &nbsp; &nbsp; //新数组的阈值 &nbsp; &nbsp; &nbsp; &nbsp; int newCap, newThr = 0; &nbsp; &nbsp; &nbsp; &nbsp; if (oldCap &gt; 0) { &nbsp;//这种情况下应该是数组已经被初始化了不为null &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (oldCap &gt;= MAXIMUM_CAPACITY) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //已经达到最大的初始容量了，则不扩容了，返回原来的数组 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; threshold = Integer.MAX_VALUE; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return oldTab; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //old&lt;&lt;2，数组扩大为原来的两倍，阈值也扩大为原来的两倍 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;oldCap &gt;= DEFAULT_INITIAL_CAPACITY) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newThr = oldThr &lt;&lt; 1; // double threshold &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp;//省略了部分初始化数组的代码，下面的一段代码是扩容以后进 &nbsp; &nbsp; &nbsp;//行扩容操作的代码 &nbsp; &nbsp; &nbsp; &nbsp; if (oldTab != null) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;//依次遍历数组中的元素 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j &lt; oldCap; ++j) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node&lt;K,V&gt; e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //首先将桶中的值保存在e节点中---&gt;JDK1.8 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;//依次将桶中的元素置为null， &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((e = oldTab[j]) != null) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; oldTab[j] = null; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //如果只有一个元素 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (e.next == null) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //如果桶的位置只有一个节点 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //重新找桶的位置，找桶的位置算法不变 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newTab[e.hash &amp; (newCap - 1)] = e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //如果是树节点 &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (e instanceof TreeNode) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ((TreeNode&lt;K,V&gt;)e).split(this, newTab, j, oldCap); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else { // preserve order &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //如果不是树节点并且有多个节点的情况下 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // 将同一桶中的元素根据(e.hash &amp; oldCap)是否为0进 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;//行分割，分成两个不同的链表，完成rehash &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node&lt;K,V&gt; loHead = null, loTail = null; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node&lt;K,V&gt; hiHead = null, hiTail = null; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Node&lt;K,V&gt; next; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; do { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; next = e.next; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((e.hash &amp; oldCap) == 0) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (loTail == null) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; loHead = e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; loTail.next = e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; loTail = e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hiTail == null) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hiHead = e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hiTail.next = e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hiTail = e; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } while ((e = next) != null); &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (loTail != null) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; loTail.next = null; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //将新的链添加到指定位置&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newTab[j] = loHead; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hiTail != null) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hiTail.next = null; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //将新的链添加到指定位置 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; newTab[j + oldCap] = hiHead; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; return newTab; &nbsp;//返回新数组 &nbsp; &nbsp; } </td> 
> </tr> 
> </tbody> 
> </table>
> 
> **\*扩容是多个线程一起扩容**
> 
> Jdk 1.8以前，导致**死循环**的主要原因是**扩容后，节点的顺序会反掉**, 在Jdk 1.8的时候，这个问题解决了吗？
> 
> <table> 
> <tbody> 
> <tr> 
> <td> <img alt="" height="347" src="https://img-blog.csdnimg.cn/20190411154633204.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70" width="575"> <img alt="" height="485" src="https://img-blog.csdnimg.cn/20190411154722252.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70" width="631"> &nbsp; 由图中可见, 扩容后，节点A和节点C的先后顺序跟扩容前是一样的。因此，即使此时有多个线程并发扩容，也不会出现死循环的情况。当然，这仍然改变不了HashMap仍是非并发安全，在并发下，还是要使用ConcurrentHashMap来代替。 </td> 
> </tr> 
> </tbody> 
> </table>

### \*\*concurrenthashmap ###

Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。

与HashMap不同的是，ConcurrentHashMap并不允许key或者value为null \[原因是在ConcurrentHashMap中，一旦value出现null，则代表HashEntry的key/value没有映射完成就被其他线程所见，需要特殊处理。\]

ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响

\*\***JDK1.7和1.8版本的区别** 参考 : [https://my.oschina.net/hosee/blog/675884][https_my.oschina.net_hosee_blog_675884] \[博主很棒,一篇即可\]

jdk7中ConcurrentHashmap中，**当长度过长碰撞会很频繁**，链表的增改删查操作都会消耗很长的时间，影响性能,所以jdk8 中完全重写了concurrentHashmap,代码量从原来的1000多行变成了 6000多 行，实现上也和原来的分段式存储有很大的区别。

主要设计上的变化有以下几点:

1.  **不采用segment而采用node，锁住node来实现减小锁粒度。**
2.  设计了MOVED状态 当resize的中过程中 线程2还在put数据，线程2会帮助resize。
3.  **使用3个CAS操作来确保node的一些操作的原子性，这种方式代替了锁。**
4.  sizeCtl的不同值来代表不同含义，起到了控制的作用。

**JDK8**中使用**synchronized而不是ReentrantLock**

### **JDK1.7** ###

ConcurrentHashMap采用了分段锁的设计，只有在同一个分段内才存在竞态关系，不同的分段锁之间没有锁竞争。

**JDK1.7 **ConcurrentHashMap中的**分段锁称为Segment，**它即类似于HashMap（[JDK7与JDK8中HashMap的实现][JDK7_JDK8_HashMap]）的结构，即**内部拥有一个Entry数组，数组中的每个元素又是一个链表**；同时又是一个ReentrantLock**（Segment继承了ReentrantLock）**。ConcurrentHashMap中的HashEntry相对于HashMap中的Entry有一定的差异性：**HashEntry中的value以及next都被volatile修饰**，这样在多线程读写过程中能够保持它们的可见性.

**概念名词: 并发度**

并发度可以理解为程序运行时能够**同时更新ConccurentHashMap且不产生锁竞争的最大线程数**，实际上就是ConcurrentHashMap中的**分段锁个数，即Segment\[\]的数组长度。**ConcurrentHashMap默认的并发度为16，但用户也可以在构造函数中设置并发度。当用户设置并发度时，ConcurrentHashMap会使用大于等于该值的最小2幂指数作为实际并发度（假如用户设置并发度为17，实际并发度则为32）。运行时通过将key的高n位（n = 32 – segmentShift）和并发度减1（segmentMask）做位与运算定位到所在的Segment。segmentShift与segmentMask都是在构造过程中根据concurrency level被相应的计算出来。

如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。（文档的说法是根据你并发的线程数量决定，太多会导性能降低）

**JDK7**中除了第一个Segment之外，剩余的Segments采用的是**延迟初始化的机制**：每次put之前都需要检查key对应的Segment是否为null，如果是则调用ensureSegment()以确保对应的Segment被创建。

ensureSegment可能在并发环境下被调用，但与想象中不同，ensureSegment**并未使用锁来控制竞争**，而是使用了Unsafe对象的getObjectVolatile()提供的**原子读语义结合CAS来确保Segment创建的原子性**。

**JDK1.7** put/putIfAbsent/putAll方法: ConcurrentHashMap的put方法被**代理到了对应的Segment,**由于在并发环境下，其他线程的put，rehash或者remove操作可能会导致链表头结点的变化，即使该变化因为是非原子写操作，因此在过程中需要进行检查，如果头结点发生变化则重新**对表进行遍历**。之所以在获取锁的过程中对整个链表进行遍历，主要目的是希望遍历的链表被**CPU cache所缓存**，为后续实际put过程中的链表遍历操作提升性能。和put类似，remove在真正获得锁之前，也会对链表进行遍历以提高缓存命中率。

**JDK1.7 **rehash方法和hashmap相似 ,扩容后该HashEntry对应到新数组中的index只可能为i或者i+capacity，由此让大多数HashEntry节点在扩容前后index可以保持不变。

**JDK1.7 **get和containsKey ,由于遍历过程中其他线程可能对链表结构做了调整，因此get和containsKey返回的可能是过时的数据，这一点是ConcurrentHashMap在**弱一致性**上的体现。如果**要求强一致性，那么必须使用Collections.synchronizedMap()**方法。

**JDK1.7 **size和containsValue, **首先不加锁循环**执行以下操作：循环所有的Segment（通过Unsafe的getObjectVolatile()以保证原子读语义），获得对应的值以及所有Segment的modcount之和。如果连续两次所有Segment的modcount和相等，则**过程中没有发生其他线程修改ConcurrentHashMap的情况，返回获得的值**。

**当循环次数超过预定义的值时**，这时需要**对所有的Segment依次进行加锁，获取返回值后再依次解锁。**值得注意的是，加锁过程中要强制创建所有的Segment，否则容易出现其他线程创建Segment并进行put，remove等操作。

### **JDK1.8** ###

摒弃了Segment（锁段）的概念，而是启用了一种全新的方式实现,利用CAS算法。它沿用了与它同时期的HashMap版本的思想，底层依然由“数组”+链表+红黑树的方式思想([JDK7与JDK8中HashMap的实现][JDK7_JDK8_HashMap])，但是为了做到并发，又增加了很多辅助的类，例如TreeBin，Traverser等对象内部类。

**JDK1.8**的重要属性**sizeCtl,** 是concurrenthashmap出镜率很高的一个属性,它是一个控制标识符，在不同的地方有不同用途，而且它的取值不同，也代表不同的含义。

*  负数代表正在进行初始化或扩容操作

*  \-1代表正在初始化

*  \-N 表示有N-1个线程正在进行扩容操作

*  正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。还后面可以看到，它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor是对应的。

**JDK1.8**重要的类

**1 Node**

Node是最核心的内部类，它包装了key-value键值对，所有插入ConcurrentHashMap的数据都包装在这里面。它与HashMap中的定义很相似，但是但是有一些差别它对value和next属性设置了volatile同步锁(与JDK7的Segment相同)，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。

**2 TreeNode**

树节点类，另外一个核心的数据结构。当链表长度过长的时候，会转换为TreeNode。但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap集成自Node类，而并非**HashMap中的集成自LinkedHashMap.Entry<K,V>类**，也就是说TreeNode带有next指针，这样做的目的是方便基于TreeBin的访问。

**3 TreeBin**

这个类并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。

**4 ForwardingNode**

一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。

**JDK1.8 Unsafe与CAS**

在ConcurrentHashMap中，随处可以看到U, 大量使用了**U.compareAndSwapXXX**的方法，这个方法是利用一个CAS算法实现**无锁化的修改值**的操作，他可以大大降低锁代理的性能消耗。这个算法的基本思想就是不断地去比较当前内存中的变量值与你指定的一个变量值是否相等，如果相等，则接受你指定的修改的值，否则拒绝你的操作。因为当前线程中的值已经不是最新的值，你的修改很可能会覆盖掉其他线程修改的结果。这一点与乐观锁，SVN的思想是比较类似的。

<table> 
 <tbody> 
 <tr> 
 <td> CAS:Compare and Swap, 比较并交换;存在于J.U.C包中。真实的CAS操作是由CPU完成的，CPU会确保这个操作的原子性，CAS远非JAVA代码能实现的功能（下面我们会看到CAS的汇编代码）。 参考&nbsp;<a href="https://blog.csdn.net/cringkong/article/details/80533917" rel="nofollow">https://blog.csdn.net/cringkong/article/details/80533917</a> public void compareAndSwap(int v,int a,int b) { &nbsp; &nbsp; &nbsp; &nbsp; if (v == a) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; v = b; &nbsp; &nbsp; &nbsp; &nbsp; }else {&nbsp;// 什么也不做 &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; } CAS操作可以防止内存中共享变量出现脏读脏写问题，多核的CPU在多线程的情况下经常出现的问题，通常我们采用锁来避免这个问题，但是CAS操作避免了多线程的竞争锁，上下文切换和进程调度。 CAS通过调用JNI的代码实现的。JNI:Java Native Interface为JAVA本地调用，允许java调用其他语言。 以<code>compareAndSwapInt()</code>为例来说，<code>compareAndSwapInt</code>就是借助C来调用CPU底层指令实现的。 下面是sun.misc.Unsafe类的compareAndSwapInt()方法的源代码： public final native boolean compareAndSwapInt(Object o, long offset, &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int expected, &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int x); 其大意是使用CPU的锁机制，确保了整个CAS操作的原子性。关于CPU中的锁机制和CPU的原子操作——<a href="https://blog.csdn.net/cringkong/article/details/79966161" rel="nofollow">CPU中的原子操作</a>。 
 <table> 
 <tbody> 
 <tr> 
 <td> [多核CPU的原子操作:在执行原子操作时，CPU保证只有一个核心能对内存进行操作，这样以来就不会出现多个核心同时运算并回写内存的情况了] 如何实现x++的原子性？ 在单处理器上，如果执行x++时，禁止多线程调度，就可以实现原子。因为单处理的多线程并发是伪并发。&nbsp; 在多处理器上，需要借助cpu提供的Lock功能。锁总线。读取内存值，修改，写回内存三步期间禁止别的CPU访问总线。同时我估计使用Lock指令锁总线的时候，OS也不会把当前线程调度走了。要是调走了，那就麻烦了。 </td> 
 </tr> 
 </tbody> 
 </table>上述参考博客的博主总结: 对于CAS操作，编译器会自动汇编成CPU可以实现原子操作的汇编代码（不同CPU下实现可能不同，但是一定会借助某些锁实现汇编代码块的原子性）。 使用CAS实现无锁同步的优点：减少操作系统阻塞线程的负担，直接使用硬件级别的锁必然要比在其之上的系统调用（比如OS实现的mutex互斥锁）更节省资源。 &nbsp; Java的CAS操作可以实现现代CPU上硬件级别的原子指令（不是依靠JVM或者操作系统的锁机制），而同时<code>volatile</code>关键字又保证了线程间共享变量的可见性和指令的顺序性，因此凭借这两种手段，就可以实现不依靠操作系统实现的锁机制来保证并发时共享变量的一致性。 如果我们仔细分析concurrent包的源代码实现，会发现一个通用化的实现模式： 首先，声明共享变量为volatile； 然后，使用CAS的原子条件更新来实现线程之间的同步； 同时，配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。 <img alt="" height="286" src="https://img-blog.csdnimg.cn/20190416165008880.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70" width="416"> </td> 
 </tr> 
 </tbody> 
</table>

### 三个核心方法 ###

ConcurrentHashMap定义了三个原子操作，用于对指定位置的节点进行操作。正是这些原子操作保证了ConcurrentHashMap的线程安全。

//获得在i位置上的Node节点
 static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
 return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
 }
 		//利用CAS算法设置i位置上的Node节点。之所以能实现并发是因为他指定了原来这个节点的值是多少
 		//在CAS算法中，会比较内存中的值与你指定的这个值是否相等，如果相等才接受你的修改，否则拒绝你的修改
 		//因此当前线程中的值并不是最新的值，这种修改可能会覆盖掉其他线程的修改结果 有点类似于SVN
 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
 Node<K,V> c, Node<K,V> v) {
 return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
 }
 		//利用volatile方法设置节点位置的值
 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
 U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
 }

### **初始化方法initTable** ###

初始化方法主要应用了关键属性sizeCtl 如果这个值〈0，表示其他线程正在进行初始化，就放弃这个操作。在这也可以看出ConcurrentHashMap的初始化只能由一个线程完成。如果获得了初始化权限，就用CAS方法将sizeCtl置为-1，防止其他线程进入。初始化数组后，将sizeCtl的值改为0.75\*n。

### 扩容方法 transfer ###

ConcurrentHashMap容量不足的时候，需要对table进行扩容。这个方法的基本思想跟HashMap是很像的，但是由于它是支持并发扩容的，所以要复杂的多。原因是它支持多线程进行扩容操作，而并没有加锁。

整个扩容操作分为两个部分

*   第一部分是构建一个nextTable,它的容量是原来的两倍，这个操作是单线程完成的。这个单线程的保证是通过RESIZE\_STAMP\_SHIFT这个常量经过一次运算来保证的，这个地方在后面会有提到；
 *  第二个部分就是将原来table中的元素复制到nextTable中，这里允许多线程进行操作。

先来看一下单线程是如何完成的：

它的大体思想就是遍历、复制的过程。首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素：

*  如果这个位置为空，就在原table中的i位置放入forwardNode节点，这个也是触发并发扩容的关键点；

*  如果这个位置是Node节点（fh>=0），如果它是一个链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上

* 如果这个位置是TreeBin节点（fh<0），也做一个反序处理，并且判断是否需要untreefi，把处理的结果分别放在nextTable的i和i+n的位置上
 * 遍历过所有的节点以后就完成了复制工作，这时让nextTable作为新的table，并且更新sizeCtl为新容量的0.75倍 ，完成扩容。

再看一下多线程是如何完成的：

在代码的69行有一个判断，如果遍历到的节点是forward节点，就向后继续遍历，再加上给节点上锁的机制，就完成了多线程的控制。多线程遍历节点，处理了一个节点，就把对应点的值set为forward，另一个线程看到forward，就向后遍历。这样交叉就完成了复制工作。而且还很好的解决了线程安全的问题。(??)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 5][]

**JDK1.8**put ,在多线程中可能有以下两个情况

1.  如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。这个扩容的操作之所以能被检测到，是因为transfer方法中在空结点上插入forward节点，如果检测到需要插入的位置被forward节点占有，就帮助进行扩容；
2.  如果检测到要插入的节点是非空且不是forward节点，就对这个节点加锁，这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比hashTable的synchronized要好得多。

整体流程就是首先定义不允许key或value为null的情况放入  对于每一个放入的值，首先利用spread方法对key的hashcode进行一次hash计算，由此来确定这个值在table中的位置。

如果这个位置是空的，那么直接放入，而且不需要加锁操作。

如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。如果是链表节点（fh>0）,则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个结点。如果加入这个节点以后链表长度大于8，就把这个链表转换成红黑树。如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。

我们可以发现JDK8中的实现也是锁分离的思想，只是锁住的是一个Node，而不是JDK7中的Segment，而锁住Node之前的操作是无锁的并且也是线程安全的，建立在之前提到的3个原子操作上。

**helpTransfer方法,**这是一个协助扩容的方法。这个方法被调用的时候，当前ConcurrentHashMap一定已经有了nextTable对象，首先拿到这个nextTable对象，调用transfer方法。回看上面的transfer方法可以看到，当本线程进入扩容方法的时候会直接进入复制阶段。** **

**treeifyBin方法,  get方法,**

**Size相关的方法, **对于ConcurrentHashMap来说，这个table里到底装了多少东西其实是个不确定的数量，因为不可能在调用size()方法的时候像GC的“stop the world”一样让其他线程都停下来让你去统计，因此只能说这个数量是个估计值。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190603110750109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 1]: /images/20220312/dd6cd848214e49a792b421da8e2502d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 2]: /images/20220312/4833982f35564cf88c23ce85c7318d70.png
[--]: https://blog.csdn.net/v123411739/article/details/78996181%C2%A0
[https_blog.csdn.net_donggua3694857_article_details_64127131]: https://blog.csdn.net/donggua3694857/article/details/64127131/
[https_blog.csdn.net_v123411739_article_details_78996181]: https://blog.csdn.net/v123411739/article/details/78996181
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 3]: /images/20220312/b4afcf591bbb42c394528e7ec89841a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 4]: /images/20220312/5df3ff68543444f58f49fdc5eb8fedbe.png
[https_blog.csdn.net_carson_ho_article_details_79373134]: https://blog.csdn.net/carson_ho/article/details/79373134
[https_blog.csdn.net_wushiwude_article_details_75331926]: https://blog.csdn.net/wushiwude/article/details/75331926
[https_blog.csdn.net_lixiaoxiong55_article_details_73308882]: https://blog.csdn.net/lixiaoxiong55/article/details/73308882
[Link 1]: https://www.baidu.com/s?wd=%E8%B7%A8%E5%B9%B3%E5%8F%B0&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[Link 2]: https://www.baidu.com/s?wd=%E6%97%A0%E5%85%B3%E7%B4%A7%E8%A6%81&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[https_www.cnblogs.com_BBchao_p_7878699.html]: https://www.cnblogs.com/BBchao/p/7878699.html
[https_coolshell.cn_articles_9606.html]: https://coolshell.cn/articles/9606.html
[https_my.oschina.net_hosee_blog_675884]: https://my.oschina.net/hosee/blog/675884
[JDK7_JDK8_HashMap]: http://my.oschina.net/hosee/blog/618953
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70 5]: /images/20220312/0413ab3dc835411daee1e7ee67142246.png