阿里网站如何做接入,企业网站建设中有哪几个重要点,一个公司可以做多少个网站,网站首页翻转效果什么模块系列文章目录
第一章 ArrayList-Java八股面试(一)
第二章 HashMap-Java八股面试(二)
第三章 单例模式-Java八股面试(三)
第四章 线程池和Volatile关键字-Java八股面试(四) 提示#xff1a;动态每日更新算法题#xff0c;想要学习的可以关注一下 文章目录系列文章目录一、…系列文章目录
第一章 ArrayList-Java八股面试(一)
第二章 HashMap-Java八股面试(二)
第三章 单例模式-Java八股面试(三)
第四章 线程池和Volatile关键字-Java八股面试(四) 提示动态每日更新算法题想要学习的可以关注一下 文章目录系列文章目录一、ConcurrentHashMap是什么1 jdk1.71. put方法2. HashEntry扩容3 Segment的数量和下标的计算4.HashEntry的初始化5.HashEntry的下标计算2. jdk1.81. 扩容机制2. 初始化机制(capacity和factor)3. put方法4. 扩容机制5. 扩容时的put和get操作总结和细节1.JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别2.ConcurrentHashMap 的并发度是什么3. ConcurrentHashMap 迭代器是强一致性还是弱一致性4.ConcurrentHashMap 和 Hashtable 的效率哪个更高为什么一、ConcurrentHashMap是什么
1 jdk1.7
JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成即 ConcurrentHashMap 把哈希桶数组切分成小数组Segment 每个小数组有 n 个 HashEntry 组成。 和普通的HashMap相比ConcurrentHashMap其实就解决了多线程下安全的问题其构造和HashMap相差不大也是需要计算二次哈希值唯一需要说明的是segment下标和小数组的问题。
Segment的数量决定了ConcurrentHashMap的并发度因为在同一时刻只有一把锁可以访问一旦Segment初始化之后就无法扩容能扩容的是Segment下面的小数组。 而每个小数组则是HashEntry。
1. put方法
每一个元素先进行二次哈希值的计算然后计算得到Segment下标而后再进算桶下标最后会以头插法的方式加入到链表中。
2. HashEntry扩容
一旦HashEntry下的节点个数大于HashEntry数量的3/4时就会发生扩容 3 Segment的数量和下标的计算
segment的数量是初始化时给的参数(clevel). 而segment的下标计算时根据如下图所示是二次哈希值的二进制编码的高4位得出12。 4.HashEntry的初始化
一旦初始化ConcurrentHashMap后第一个HashEntry也会随之初始化HashEntry的数量计算时capacity/Segment(clevel),当然最小为2.第一次创建之后这个也就会作为模板后面任意一个Segment对HashEntry初始化时都会以这个长度而不是第一个HashEntry扩容后的长度此时的长度。注意这里的capacity只在这一步计算中用到我们看到的数组长度其实是segment的长度。 5.HashEntry的下标计算
二次哈希值的二进制编码的最低位如下图为0则在索引为0的地方。
2. jdk1.8
与jdk1.7不同的是没有了Segment也没有了HashEntry和原始的HashMap在结构上有一些类似。初始化方式为懒汉式只有在调用时才会初始化整个ConcurrentHashMap.在数据结构上 JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组链表红黑树结构在锁的实现上抛弃了原有的 Segment 分段锁采用CAS synchronized实现更加细粒度的锁。
将锁的级别控制在了更细粒度的哈希桶数组元素级别也就是说只需要锁住这个链表头节点红黑树的根节点就不会影响其他的哈希桶数组元素的读写大大提高了并发度。 1. 扩容机制
与1.7不同的是当容量到达3/4时就会发生扩容而不是超过3/4。
2. 初始化机制(capacity和factor) capacity的意思并不再指初始化数组的容量而是指一开始会往ConcurrentHashMap中放几个元素。 如上图所示放16个元素扩容因子为3/4假如map长度为16那么长度在12就会扩容因此还需要在16的基础上继续扩容成32.尽管capacity设置为16但并不意味着必须要放16个元素并且capacity和factor只会在第一次初始化时有效。后续就算factor设置为0.5或者其他值都是按默认的0.75计算。 值得说明的是ConcurrentHashMap的容量只能是2的n次方。如上所示放7个元素那么先考虑8是否能行因为factor为0.5所以必须要扩容成16.
3. put方法 根据二次哈希值先定位到数组索引处然后占锁再进行put。数组的大小决定了 ConcurrentHashMap的并发度也就是说不同索引的Node互不干扰d的put和ab的put互不影响。但是a和b的put需要占锁释放锁的步骤。
4. 扩容机制 假设n为临界节点也就是put了n之后就会扩容与数组方式相同新建一个容量为2倍的新数组然后进行数据迁移。
迁移顺序是从后往前进行迁移每次迁移一个索引的链表或者红黑树。一旦该索引处完成迁移就会变成Forwarding Node 认为是已完成的Node。 在迁移过程中需要重新计算二次哈希值一般情况下会重新创建新的节点并将该节点插入新的数组中。 在这里为什么需要重新创建新的节点需要说明一下如上图1这个节点的next指针为2一旦哈希值重新计算之后在新的数组中它的next不一定是2. 当然也有一种情况可以直接引用不需要再创建节点的情况就是比如说456三个节点在新的数组中仍然是该顺序情况那么就不需要新创建节点。
5. 扩容时的put和get操作
get的索引在forwarding node之前 那么正常get并不会影响。
2.get的索引已经变成forwarding 那么直接去新数组中取得get
3.get的索引正在迁移 由上所述因为扩容之后的节点的next指针可能会变化所以该线程会等待该索引完成迁移查询新的节点。 put的索引在forwarding node之前 同样正常的并发执行。 2.put的索引已经变成forwarding node 线程会阻塞并帮助前面的node一起进行迁移因为新的节点只有在所有旧的节点都完成迁移之后才能进行put这时线程就会帮助前面未完成的索引一起进行迁移。 3.put的索引正在迁移 只能阻塞。
总结和细节
1.JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别
数据结构取消了 Segment 分段锁的数据结构取而代之的是数组链表红黑树的结构。 保证线程安全机制JDK1.7 采用 Segment 的分段锁机制实现线程安全其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CASsynchronized保证线程安全。 锁的粒度JDK1.7 是对需要进行数据操作的 Segment 加锁JDK1.8 调整为对每个数组元素加锁Node。 链表转化为红黑树定位节点的 hash 算法简化会带来弊端hash 冲突加剧因此在链表节点数量大于 8且数据总量大于等于 64时会将链表转化为红黑树进行存储。 查询时间复杂度从 JDK1.7的遍历链表O(n) JDK1.8 变成遍历红黑树O(logN)。
2.ConcurrentHashMap 的并发度是什么
并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。在JDK1.7中实际上就是ConcurrentHashMap中的分段锁个数即Segment[]的数组长度默认是16这个值可以在构造函数中设置。
在JDK1.8中已经摒弃了Segment的概念选择了Node数组链表红黑树结构并发度大小依赖于数组的大小。
3. ConcurrentHashMap 迭代器是强一致性还是弱一致性
与 HashMap 迭代器是强一致性不同ConcurrentHashMap 迭代器是弱一致性。
ConcurrentHashMap 的迭代器创建后就会按照哈希表结构遍历每个元素但在遍历过程中内部元素可能会发生变化如果变化发生在已遍历过的部分迭代器就不会反映出来而如果变化发生在未遍历过的部分迭代器就会发现并反映出来这就是弱一致性。
4.ConcurrentHashMap 和 Hashtable 的效率哪个更高为什么
ConcurrentHashMap 的效率要高于 Hashtable因为 Hashtable 给整个哈希表加了一把大锁从而实现线程安全。而ConcurrentHashMap 的锁粒度更低在 JDK1.7 中采用分段锁实现线程安全在 JDK1.8 中采用CASsynchronized实现线程安全。
