浅谈ConcurrentHashMap实现原理

我们都知道hashtable是线程安全的类，因为使用了synchronized来锁整张hash表来实现线程安全，让线程独占；

concurrenthashmap的锁分离技术就是用多个锁来控制对hash表的不同部分进行修改，因为我可能只需要对一小块部分进行操作，而如果锁整张表开销太大了，其内部实现就是用semgent来控制的，每个semgent都是一个小的hashtable，他们有自己的锁；

然后有些方法需要访问整个表，比如size，containsvalue肯定是要访问整个表的数据，这个时候就需要锁整张表，concurrenthashmap就会按顺序锁定每个segment，操作完毕之后再按顺序释放每个segment，按顺序是为了防止出现死锁；

引用一张图片解释concurrenthashmap的结构：

 

可以看出就是在hashmap的基础上多了一个数组(暂且这样理解)，数组的每个元素就是segment；segment<k,v> extends reentrantlock implements serializable；

concurrenthahsmap进行put操作的时候，对key需要进行3次hash运算才能确定最终的位置：hash1(key) -> x1(得到一个值)；hash2(x1) -> x2(确定segment位置，第二次hash是为了减少hash碰撞)；hash3(x2) -> x3(确定元素放入哪个hashentry)；这里只是用比较好理解的白话说，下面会说原理；

 

concurrenthashmap中主要实体类就是三个：concurrenthashmap(整个hash表),segment(桶)，hashentry(节点)；

 

 static final class hashentry<k,v> {  
     final k key;  
     final int hash;  
     volatile v value;  
     final hashentry<k,v> next;  
 } 

 

可以看出，除了value不是final，其next属性都是final，说明不能从hash链的中间或尾部添加或删除节点；对于put操作，可以一律将元素添加到hash链的头部，而对于remove操作，从中间删除一个节点，将该节点的前面所有节点复制一份并指向删除节点的下一节点；这会产生两条hash链，这也是为了保证多线程访问的同步性；将value设置成volatile，这样避免了加锁；因为一个线程在执行get，另一个线程在执行remove，remove还没有执行完的时候，get能看到remove之前的值，如下图：

 

下面说说segment的数据结构：

static final class segment<k,v> extends reentrantlock implements serializable {    
         /** 
          * count用来统计该段数据的个数，它是volatile，如增加/删除节点，都要写count值，每次读取操作开始都要读取count的值。
          */
         transient volatileint count;  
         /** 
          * modcount统计段结构改变的次数，主要是为了检测对多个段进行遍历过程中某个段是否发生改变
          */
         transient int modcount;  
         /** 
          * rehash界限值
          */
         transient int threshold;  
         /** 
          * 就是上面的hashentry
          */
         transient volatile hashentry<k,v>[] table;  
         /** 
          * 负载因子
          */
         final float loadfactor;  
 }

未完待续。。。