gment是什么意思

Java⾼并发之ConcurrentHashMap（锁分段技术、结构、初始化、如何定位、

常。。。

1.为什么要使⽤ConcurrentHashMap？

①HashMap线程不安全

HashMap是⾮线程安全的，并发执⾏put操作时会引起Entry链表形成死循环。

由于Entry链表中的next结点永远不为null，就会在执⾏get操作时触发死循环，导致CPU使⽤率到达100%。

形成死循环的原因：并发执⾏put操作会导致HashMap的扩容。当调⽤resize()⽅法进⾏扩容时，需要将旧的HashMap中的Entry移动

到新的HashMap中，该操作由transfer()⽅法负责完成。

transfer()⽅法在移动的过程中，如果出现以下情况，将会导致Entry链表形成死循环。

具体的图解见博客：

②HashTable效率低下

HashTable使⽤synchronized关键字实现线程安全，⼀个线程占⽤锁访问HashTable的同步⽅法，其他线程也想要访问同步⽅法，必

须进⼊阻塞状态，等待锁的释放。

例如，线程1使⽤put操作进⾏元素添加；线程2不但不能执⾏put操作添加元素，也不能执⾏get操作获取元素。

因此，在线程竞争激烈的情况下，HashTable的效率⾮常低下。

③ConcurrentHashMap的锁分段技术

ConcurrentHashMap使⽤锁分段技术，现将数据分成⼀段⼀段的存储，然后给每⼀段数据加⼀把锁。

当线程占⽤锁访问某段数据时，其他线程可以并发访问其他段的数据。只要不是并发访问同⼀段数据，就不会出现锁竞争的情况。

因此，ConcurrentHashMap的锁分段技术有效地提⾼了并发访问率。

rentHashMap详解

①结构：Segment数组+HashEntry数组（桶）

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。

t是⼀种可重⼊锁ReentrantLock，在ConcurrentHashMap⾥扮演锁的⾓⾊；HashEntry则⽤于存储键值对数据，就是

HashMap中的Node。

2.⼀个ConcurrentHashMap⾥包含⼀个Segment数组，每个Segment包含⼀个HashEntry数组，其实就是⼀个HashMap，为桶+链

表的结构。

3.每个Segment守护者⼀个HashEntry数组⾥的元素,当对HashEntry数组的数据进⾏修改时，必须⾸先获得它对应的Segment

锁。

②ConcurrentHashMap的初始化

ConcurrentHashMap的初始化主要包括：gments数组的初始化、每个gment的初始化。

通过initialCapacity、loadFactor、concurrencyLevel⼏个参数来初始化gments数组的长度ssize、段偏移量gmentShift、段掩

码gmentMask，每个gment⾥的HashEntry数组的长度cap，每个gment的容量阈值threshold。

gments数组的初始化

concurrencyLevel是允许访问的最⼤并发数，ssize是gments数组的长度，即整个ConcurrentHashMap中锁的个数。

if(concurrencyLevel>MAX_SEGMENTS)

concurrencyLevel=MAX_SEGMENTS;

intsshift=0;

intssize=1;

//ssize是⼤于等于concurrencyLevel的最⼩2^N，sshift是1左移的次数，也就是前⾯的N

//⽐如我输⼊的concurrencyLevel=12，那么sshift=4，ssize=16

while(ssize

++sshift;

ssize<<=1;//ssize=ssize<<1,ssize=ssize*2

}

gmentShift=32-sshift;

gmentMask=ssize-1;//gmentMask的⼆进制是⼀个全是1的数

ts=ay(ssize);//gment个数是ssize，默认为16

ssize的计算：

ts数组的长度是ssize是由concurrencyLevel计算得出的：先将ssize初始化为1，只要ssize

左移⼀位，即将ssize扩⼤两倍。直到ssize是⼤于或等于concurrencyLevel的最⼩的

2.为什么ssize是⼤于或等于concurrencyLevel的最⼩的？答：为了能通过按位与的hash算法定位gments数组的索引，要求ssize

=2^N。

3.例如，concurrencyLevel=14，则计算出来的ssize=16。

rencyLevel的最⼤值为65535（），所以ssize的最⼤值为65536)（）。

要想通过按位与的hash算法定义gments数组的索引，还需要使⽤gmentShift和gmentMask这两个全局变量。前者定位参与

hash运算的位数，后者表⽰hash运算的掩码。

gmentShift的计算：

1.在计算ssize时，ssize的初始值是1，通过对1进⾏向左移位，可以得到满⾜条件的ssize。同时，有个sshift的变量，记录了1发⽣左

移的次数。

2.完成ssize的计算后，sshift的值也就确定了。然后开始计算gmentShift，gmentShift=32-sshift。

3.使⽤32减去sshift，是因为ConcurrentHashMap⾥的hash()⽅法输出的最⼤数是32位。

4.因为ssize的最⼤值为，所以sshift的最⼤值为16，所以gmentShift的最⼩值为16。

gmentMask的计算：

tMask的计算⾮常简单，gmentMask=ssize-1。

2.作为掩码，要求其⼆进制数为全为1。通过减⼀，刚好可以让gmentMask的⼆进制数全为1。

3.因为ssize的最⼤值为65536（），所以gmentMask的最⼤值为65535，⼆进制数16位，每位都为1。

gment的初始化

2N

2N

2−161216

216

216

initialCapacity是ConcurrentHashMap的初始化容量，即gments数组中HashEntry数组的总长度。

每个gment中HashEntry数组的长度cap，是⼤于等于c的最⼩。

loadFactor是每个gment的负载因⼦，在构造⽅法中初始化gment，需要使⽤cap和loadFactor这两个参数

if(initialCapacity>MAXIMUM_CAPACITY)

initialCapacity=MAXIMUM_CAPACITY;

intc=initialCapacity/ssize;

if(c*ssize

++c;

intcap=1;

while(cap

cap<<=1;

for(inti=0;i<;++i)

//cap=2^N，默认是1，也就是每个gment下都构造了cap⼤⼩的table数组

ts[i]=newSegment(cap,loadFactor);

cap的计算：

1.计算initialCapacity/ssize，可以得到initialCapacity是ssize的倍数c。

2.考虑到整数除法的特性，如果c是向下取整了，需要将c加⼀。即如果c*ssize

3.将每个gment中HashEntry数组的长度cap初始化为1，如果cap

c的最⼩。

gment的初始化

1.传⼊cap和loadFactor初始化每个gment，其中每个gment的阈值threshold=cap*loadFactor。

③ConcurrentHashMap的实例化

ConcurrentHashMap使⽤默认构造函实例化，三个参数都使⽤默认初始值，concurrencyLevel=16，initialCapocity=16，loadFactor=

0.75f。

ConcurrentMapwordCounts=newConcurrentHashMap<>()

也可以指定initialCapocity、loadFactor、concurrencyLevel的值：

newConcurrentHashMap<>(initialCapocity)

newConcurrentHashMap<>(initialCapocity,loadFactor)

newConcurrentHashMap<>(initialCapocity,loadFactor,concurrencyLevel)

④gment的定位和table中的定位

键值对要想存⼊ConcurrentHashMap中，必须先确定它所在的gment，然后确定它所在的HashEntry。

ConcurrentHashMap使⽤Wang/Jenkinshash的变种算法对元素的hashCode进⾏⼀次再散列，确定键值对所在的gment。

再散列的⽬的：通过让数字的每⼀位都参与到散列运算中，减少散列冲突，使元素能够均匀的分布在不同的gment中。

对散列后的hash值，计算gment的index：

finalSegmentgmentFor(inthash){

returngments[(hash>>>gmentShift)&gmentMask];

}

1.先对再散列的hash值进⾏⽆符号右移（>>>)，右移gmentShift那么多位，意思是让该值的⾼32-gmentShift参与散列运算。

2.然后将⽆符号右移后的值与gmentMask进⾏按位与，计算出键值对在gment中的位置。

3.按照默认初始值，gmentShift=32-4=28，gmentMask=16-1=15。

2N

2n

键值对存放在HashEntry数组中的哪个位置，也是通过再散列的后值进⾏定位的。与gment的定位相⽐，是直接将再散列的hash值

与数组长度减⼀相与。

HashEntrygetFirst(inthash){

HashEntry[]tab=table;

returntab[hash&(-1)];

}

rentHashMap的操作

①get操作

get操作⾮常⾼效：整个get操作的过程不需要加锁，除⾮读到的value为null才加锁。（readValueUnderLock(e)）

get操作⾮常⾼效的原因：

1.将get操作中的共享变量count和value定义成volatile，使得它能够在线程之间保持可见性，能够多线程同时读，并且保证不会读到过

期的值，但是只能单线程写。

操作只需要读不需要写共享变量count和value，因此不需要加锁。

3.定义成volatitle的变量既然能多线程同时读，单线程写，如果保证不会读到过期值？根据java内存模型的happensbefore原则，对

volatile字段的写⼊操作先于读操作，即使两个线程同时修改和获取volatile字段，get操作也能拿到最新的值。

get操作是volatile替换锁的经典场景。

注意：volatile变量要先赋值给局部变量，然后操作局部变量后，最后再写回volatile变量。因为，读写volatitle变量的开销很⼤。

publicVget(Objectkey){

//对key的hashCode进⾏再散列，使元素均匀分布

inthash=hash(de());

//先定位gment，再获取元素

returngmentFor(hash).get(key,hash);

}

//真正的get操作

Vget(Objectkey,inthash){

//count是⼀个volatile变量，每次put和remove之后的最后⼀步都要更新count

if(count!=0){

HashEntrye=getFirst(hash);//定位桶下标

while(e!=null){

//判断键相等：要求hash值相同且key相等

if(==hash&&()){

Vv=;

if(v!=null)

returnv;

returnreadValueUnderLock(e);//加锁读

}

e=;

}

}

returnnull;

}

HashEntrygetFirst(inthash){

HashEntry[]tab=table;

returntab[hash&(-1)];

}

②put操作

put操作需要对共享变量进⾏写⼊操作，为了保证线程安全，需要在操作共享变量时加锁。

先定gment，然后将键值对插⼊到gment中。

插⼊操作需要经历两个步骤：

1.先判断gment中的HashEntry数组是否需要扩容。即判断gment中的HashEntry数组是否超过容量阈值（threshold）。

2.再定位键值对在HashEntry数组中的位置，然后插⼊到HashEntry数组中。

gment的扩容与HashEntryMap相⽐：

1.扩容的时间不同：HashMap是先将键值对插⼊后，再判断是否需要进⾏扩容；⽽ConcurrentHashMap的gment是先判断是否需

要扩容，再插⼊键值对。HashMap很可能在扩容之后没有键值对再插⼊，这时就进⾏了⼀次⽆效的扩容。

2.扩容倍数相同：gment的扩容也是将HashEntry数组容量扩⼤两倍。

3.扩容的范围不同：为了⾼效，ConcurrentHashMap不会对整个容器进⾏扩容，⽽只对某个gment进⾏扩容。

publicVput(Kkey,Vvalue){

if(value==null)

thrownewNullPointerException();//明确指定value不能为null

inthash=hash(de());

returngmentFor(hash).put(key,hash,value,fal);

}

//真正的put操作

Vput(Kkey,inthash,Vvalue,booleanonlyIfAbnt){

lock();//对gment加锁，在finally中释放锁

try{

intc=count;//volatile变量，先赋值给局部变量，再读写。

if(c++>threshold)//ensurecapacity

rehash();//判断容量，如果不够了就扩容

//table是volatile变量，读写volatile变量的开销很⼤

HashEntry[]tab=table;

intindex=hash&(-1);//寻找table的下标

HashEntryfirst=tab[index];

HashEntrye=first;

//遍历单链表，找到key相同的为⽌，或者直到链表结尾为⽌

while(e!=null&&(!=hash||!()))

e=;

VoldValue;

if(e!=null){//如果有相同的key，那么直接替换

oldValue=;

if(!onlyIfAbnt)

=value;

}

el{//否则在链表表头插⼊新的结点

oldValue=null;

++modCount;

tab[index]=newHashEntry(key,hash,first,value);

count=c;//write-volatile

}

returnoldValue;

}finally{

unlock();

}

}

put⽅法的具体过程：

1.对整个gment加锁，lock()。

2.先通过c>threshold判断是否需要进⾏扩容，如果需要，调⽤rehash()⽅法进⾏扩容。

3.定位键值对在HashEntry数组中的位置，找到所在链表的表头：

HashEntry[]tab=table;

intindex=hash&(-1);//寻找table的下标

HashEntryfirst=tab[index];

HashEntrye=first;

4.遍历链表，直到找到相同的key，或者遍历到链表末尾。

5.如果存在相同的key，则更新value；否则，将键值对通过头插法插⼊到链表中。

6.在finally语句块中，对整个gment进⾏解锁，unlock()。

③size操作

每个gment维护了⼀个count变量，⽤于统计该gment中的键值对个数。

如果我们要统计整个ConcurrentHashMap⾥元素的⼤⼩，最直观的想法：将所有gment中的count值进⾏求和。

实际上，直接把所有gment的count相加得到的ConcurrentHashMap⼤⼩并不准确。

ConcurrentHashMap的解决办法：

1.先通过两次不加锁的⽅式，对gment中的count变量进⾏累加。

2.如果两次操作的结果不⼀致，则使⽤加锁的⽅式，对gment中的count变量进⾏累加。

两次操作结果不⼀致，是通过modCount变量进⾏判断的：如果gment的modCount在第⼆次统计时和第⼀次统计时不⼀样，则

直接退出统计，使⽤加锁的⽅式重新统计。

modCount会在gment的put,remove和clean⽅法中加⼀，直接判断统计前后的modCount值是否发⽣变化，就可以知道容器

⼤⼩是否发⽣变化。

publicintsize(){

finalSegment[]gments=ts;

longsum=0;

longcheck=0;

int[]mc=newint[];

//uredueto

//continuousasyncchangesintable,resorttolocking.

for(intk=0;k

check=0;

sum=0;

intmcsum=0;

for(inti=0;i<;++i){//第⼀次统计

sum+=gments[i].count;

mcsum+=mc[i]=gments[i].modCount;

}

if(mcsum!=0){

for(inti=0;i<;++i){//第⼆次统计

check+=gments[i].count;

if(mc[i]!=gments[i].modCount){//modCount发⽣该变则结束当次尝试

check=-1;//forceretry

break;

}

}

}

if(check==sum)

break;

}

if(check!=sum){//Resorttolockingallgments

sum=0;

for(inti=0;i<;++i)

gments[i].lock();

for(inti=0;i<;++i)

sum+=gments[i].count;

for(inti=0;i<;++i)

gments[i].unlock();

}

if(sum>_VALUE)

_VALUE;

el

return(int)sum;

}

④与Hashtable的⽐较

并发访问的实现不同、锁住的范围不同：HashTable中get、put、remove、clear操作都是⽤synchronized关键字进⾏修饰，是对整个

HashTable加锁。⽽ConcurrentHashMap在put、remove、clear操作中使⽤锁，只是对某个gment单独加锁。

get操作是否⽀持同时读：HashTable的get操作使⽤synchronized字修饰，因此不⽀持同时读。⽽ConcurrentHashMap的get操作在整

个过程中不加锁，除⾮读到的value为null才加锁重读，⽀持同时读，⽽且保证不会读到过期值。（使⽤volatitle关键字代替锁的经典场

景）

并发访问率：某个线程占⽤锁访问HashTable的同步⽅法，其他线程也访问HashTable的同步⽅法，必须进⼊阻塞状态，等待锁的释

放。⽽某个线程占⽤锁访问ConcurrentHashMap中的某个gment，其他线程可以访问ConcurrentHashMap的其他gment。

rentHashMap在JDK1.8中的变化

锁机制的变化：

1.7使⽤锁分段技术实现并发更新操作，核⼼类为Segment，它继承⾃可重⼊锁ReentrantLock，并发度与Segment数量相

等。

1.8使⽤了CAS操作来⽀持更⾼的并发度，在CAS操作失败时使⽤内置锁synchronized。

结构的变化：

1.7中，HashEntry数组与JDK1.7中的HashMap⼀样，采⽤数组+链表的⽅式。

1.8中，没有使⽤gment，⽽且HashEntry数组与JDK1.8中⼀致，采⽤数组+链表+红⿊树的⽅式。

3.链表长度⼤于等于8，链表转为红⿊树；结点数⼩于等于6，红⿊树转回链表。

5.常见的问题

p，HashTable，三者的区别，底层源码

从为什么要使⽤ConcurrentHashMap⼊⼿：HashMap线程不安全，HashTable效率低下，ConcurrentHashMap锁分段技术提⾼并发访

问率。

底层源码：讲解ConcurrentHashMap的结构、HashTable的put、get、remove、clear操作使⽤synchronized关键字修饰。

1.7中ConcurrentHashMap的size()操作

两次不加锁的⽅式进⾏统计，如果统计结果不⼀致，使⽤加锁的⽅式重新统计。

p与ConcurrentHashMap的区别

HashMap⾮线程安全，并发执⾏put操作容易形成链表死循环；ConcurrentHashMap⽀持多线程的并发访问：ConcurrentHashMap的锁

分段技术

HashMap先插⼊元素再扩容，ConcurrentHashMap先扩容再插⼊。

HashMap如何转化为线程安全的：①使⽤onized(hashMap)；②直接使⽤ConcurrentHashMap。

rentHashMap源码实现

ConcurrentHashMap锁分段技术、初始化过程、get操作、put操作、size操作

rentHashMap与HashTable在性能上的差异？形成差异的原因？

HashTable使⽤synchronized关键字实现并发访问时的线程安全，效率低下。

ConcurrentHashMap使⽤锁分段机制实现并发访问，提⾼了并发访问率。

1.7和JDK1.8中，ConcurrentHashMap的区别

锁机制的变化、结构的变化