中时讯通信建设有限公司网站,咋样做班级主页网站,免费工程项目分包平台,影响网站pr的因素有哪些转载自 玻璃猫 程序员小灰————————————————————————前两期我们讲解了HashMap的基本原理#xff0c;以及高并发场景下存在的问题。没看过的小伙伴可以点击下面链接#xff1a;漫画#xff1a;什么是HashMap#xff1f;
漫画#xff1a;高并发下的H…转载自 玻璃猫 程序员小灰————————————————————————前两期我们讲解了HashMap的基本原理以及高并发场景下存在的问题。没看过的小伙伴可以点击下面链接漫画什么是HashMap
漫画高并发下的HashMap如果实在懒得看也没有关系我们来简单回顾一下HashMap的结构简单来说HashMap是一个Entry对象的数组。数组中的每一个Entry元素又是一个链表的头节点。Hashmap不是线程安全的。在高并发环境下做插入操作有可能出现下面的环形链表Segment是什么呢Segment本身就相当于一个HashMap对象。同HashMap一样Segment包含一个HashEntry数组数组中的每一个HashEntry既是一个键值对也是一个链表的头节点。单一的Segment结构如下像这样的Segment对象在ConcurrentHashMap集合中有多少个呢有2的N次方个共同保存在一个名为segments的数组当中。因此整个ConcurrentHashMap的结构如下可以说ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面有若干个子哈希表。这样的二级结构和数据库的水平拆分有些相似。Case1不同Segment的并发写入不同Segment的写入是可以并发执行的。Case2同一Segment的一写一读同一Segment的写和读是可以并发执行的。Case3同一Segment的并发写入Segment的写入是需要上锁的因此对同一Segment的并发写入会被阻塞。由此可见ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度让并发操作效率更高。Get方法1.为输入的Key做Hash运算得到hash值。2.通过hash值定位到对应的Segment对象3.再次通过hash值定位到Segment当中数组的具体位置。Put方法1.为输入的Key做Hash运算得到hash值。2.通过hash值定位到对应的Segment对象3.获取可重入锁4.再次通过hash值定位到Segment当中数组的具体位置。5.插入或覆盖HashEntry对象。6.释放锁。Size方法的目的是统计ConcurrentHashMap的总元素数量 自然需要把各个Segment内部的元素数量汇总起来。但是如果在统计Segment元素数量的过程中已统计过的Segment瞬间插入新的元素这时候该怎么办呢ConcurrentHashMap的Size方法是一个嵌套循环大体逻辑如下1.遍历所有的Segment。2.把Segment的元素数量累加起来。3.把Segment的修改次数累加起来。4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于说明统计过程中有修改重新统计尝试次数1如果不是。说明没有修改统计结束。5.如果尝试次数超过阈值则对每一个Segment加锁再重新统计。6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁次数一定和上次相等。7.释放锁统计结束。官方源代码如下public int size() {// Try a few times to get accurate count. On failure due to// continuous async changes in table, resort to locking.final SegmentK,V[] segments this.segments;int size;boolean overflow; // true if size overflows 32 bitslong sum; // sum of modCountslong last 0L; // previous sumint retries -1; // first iteration isnt retrytry {for (;;) {if (retries RETRIES_BEFORE_LOCK) {for (int j 0; j segments.length; j)ensureSegment(j).lock(); // force creation}sum 0L;size 0;overflow false;for (int j 0; j segments.length; j) {SegmentK,V seg segmentAt(segments, j);if (seg ! null) {sum seg.modCount;int c seg.count;if (c 0 || (size c) 0)overflow true;}}if (sum last)break;last sum;}} finally {if (retries RETRIES_BEFORE_LOCK) {for (int j 0; j segments.length; j)segmentAt(segments, j).unlock();}}return overflow ? Integer.MAX_VALUE : size;
}为什么这样设计呢这种思想和乐观锁悲观锁的思想如出一辙。为了尽量不锁住所有Segment首先乐观地假设Size过程中不会有修改。当尝试一定次数才无奈转为悲观锁锁住所有Segment保证强一致性。几点说明1. 这里介绍的ConcurrentHashMap原理和代码都是基于Java1.7的。在Java8中会有些许差别。2.ConcurrentHashMap在对Key求Hash值的时候为了实现Segment均匀分布进行了两次Hash。有兴趣的朋友可以研究一下源代码。—————END—————
