注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

java HashMap 和ConcurrentHashMap 代码实现分析(原)  

2013-02-10 21:54:48|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

hashmap
1.数据结构
核心是一个Entry[] table数组,一个哈希表
Entry<K,V> table[n] n为2的幂次方长度,使用2的幂次方能通过异或的位运算获取某哈希值和数字下标的对应关系

Entry包含 key value hash next
其中 key 和hash是final的

2.
增,改:根据hash找到table格子,比较所有的对象是否为目标对象,如果不存在,则在链表头插入
删:根据hash找到table格子,遍历比较删除
查:根据hash找到table格子,遍历比较查找

遍历:的时候走全部单元格一次,没有跳链表。每次获取一个键值对的时候,已经把next获取了用户next检测。

3.并发自检
在遍历的时候记录一次总修改数,每次读取的时候都检查是否更新了
否则抛出ConcurrentModificationException

4.rehash
loadFactor为满载因子,默认为0.75。
threshold是临界值,为table长度*loadFactor
当元素个数大于threshold进行rehash
每次按照2的幂次方来增长,每次rehash的时候,所有的Entry不会重建只会修改所有的next指针来重新构造关系。

其中table长度和loadfactor是构造函数的两个参数

ConcurrentHashMap是线程安全的hashmap
java开发团队在整个流程的设计上做了很多改进力求保持并发下的高效
1.数据结构
ConcurrentHashMap 比起普通的hashmap 多了一层segment的概念
大致可以理解为 一个segment才是一个真正的hashtable。
大部分的操作经过hash选定segment后,会直接调用segment的操作函数。

构造函数中新增加了一个参数,concurrency level (同步级别)也就是预估的线程并发数,真正构造的时候。
会创建比concurrency level大的 2次幂个segment。
每一个线程进行的hash操作实际上会派送到一个segment。这样即使有多个线程同时修改ConcurrentHashMap,
只要不是刚好有两个线程同时修改这个segment,是不会有同步竞争的。

假设每个线程映射到的segment是随机的,则不出现同步的概率为A(c,s)/s^c(就是标准的概率论的计算啦)
有空可以把平均等待时间加入再计算平均等待时间

而每一个segment的对象 包含一个table(哈希表) 每个table上挂着一个enter的链表

2.各种操作
增删查改的操作先找到这次操作的segment然后再对应地进行操作
每一个对象的hashcode就是一个int值,高位部分将作为segment的下标,其余部分将作为这个segment中的hash代码使用。

跟普通的hashmap不一样的是 由于要保证并发之间的准确性。
entry中的 next 是final的 不能修改。
因为加入一个线程在进行遍历循环或者定位元素的时候,要通过next查找下个entry,
假如这个时候另一个线程将修改了这个entry的next
(hashmap中的删除就是直接修改这个entry的next到下个对象来进行删除)
将会导致不可预料的状况发生。

value部分是volatile的,保证其它线程的修改对其它线程可见。

这里用到的锁不是常见的sync 而是使用了ReentrantLock。关于sync和ReentrantLock的比较,请戳这里TODO。

以下过程都是在定位到segment之后进行的伪算法
增,改:
1.计算hashcode,取高位,定位到segment
2.加segment级别的锁
3.添加1容量,测试是否需要rehash
4.定位table,遍历entry链表,查找是否存在对应的key,有到5,无到6
5.修改对应的value,到7
6.将新的映射关系插入在头部
7.修改modcount
8.解锁

删:
1.计算hashcode,取高位,定位到segment
2.加segment级别的锁
3.用hash低位在table中定位,遍历对应的entry链表,查找是否存在对应的key,有到4,无到8
4.  (由于entry的next指针不能修改,所以情况比普通的复杂很多)
  分析:假如现在的状况为  table[n]->l1->o->l2
  o为要删除的entry
  l1为o之前的链表
  l2为o之后的链表
   复制l1链表为h1
5.将h1指向l2
6.再将table[n]指向h1
  最后状况为 table[n]->h1->l2 
                     l1->o->l2

   分析:由于链表是不能修改的,之前的那个链表还会存在。
   假如,我们在删除的过程中有其它线程正在查找定位元素,当它定位到l1的时候,
   我们开始了加锁并完成这一连串复杂的操作。
   那其它线程执行的时候 还是会按照旧链表,最终回到l2上的,防止,访问到一个不存在的对象。
   然后,当没有任务线程的引用在l1或者o上的时候,java的GC 判断l1和o都是不可到达的,会成为回后的对象

7.修改modcount
8.解锁

查:查找跟普通的hashmap类似,仅仅在最后要返回value值的时候加锁,防止查找对象被删除
在遍历定位的时候,并不会加锁。

遍历:代码写得好难懂
其实就是三层循环,先看看,下个entry是否存在,不存在就寻找下个table元素,再不存在就寻找下个segment。

其中为了保证遍历时候的正确性,在rehash过程也做了特殊的处理。

新增加的特殊操作:
替换:除了传入KEY,VALUE,还可以传入一个oldvalue,最终更新之前会先对比当前值和oldvalue是否一致,如果不一致将不会更新key的值为value值,返回false
具体场景可以考虑计数,两个线程分别针对某个key进行累加操作
假如当前为 key的value值为5
A线程和B线程都要加1,A和B都要先读取key的value值,然后赋新值。
如果单纯使用put操作
最终实际执行可能如下,过程如下:

i.A读取key值的value为5
ii.B读取key值的value为5
iii.A调用put(key,6)
iiiii.B调用put(key,6)
最终key的值肯定为6,而实际上正确的值应该为7。

(这就是即使使用线程安全的类,都会可能导致的陷阱。具体可看线程安全5个等级TODO。)

使用replace就可以很方便地解决这个问题:
过程如下:
i.A读取key值的value为5
ii.B读取key值的value为5
iii.A调用replace(key,6,5),返回值为true
iiii.B调用replace(key,6,5),返回值为false(因为旧值为6)
iiiii.B由于更新失败,再次提交调用replace(key,7,6)

通过replace的返回值进行再次更新可以保证线程的安全。

JAVA中高效的AotmicInteger的实现方式就是使用类似的循环更新的方式
不过,它不用加锁,是基于CPU中的高级原子指令testANDset来完成的,具体戳这里TODO

3.rehash过程
不同于hashmap的rehash,在这里,由于next指针不能改,所有转移都是复制的。
不过有个优化,
由于table是2倍增加的,对应的hash值的地位也是相同的。
那就是说旧表中的table[n]下挂再的entry 最终会映射到n或者n+旧表长度的table桶里面
所以在复制之前首先把链表末尾一整段连续相同下标的entry串找出来
然后,复制这个串之前的entry,复用整个连续串。

伪算法:
1.遍历table,对每个entry链表做如下处理:{
1.遍历整个链表,根据每个entry的hashcode,求出映射的table下标
2.在遍历过程中,记录最后的相同下标连续串的开头entry
        3.再次遍历整个链表到连续串开头entry,每个entry复制插入到新的table里面
        4.将新的table的链表尾连接到连续串开头
}


  评论这张
 
阅读(623)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017