（转）ConcurrentHashMap分段与锁的学习总结

现阶段的学习策略是理解和实践这些知识点，并没有深入分析其原理，但确实精读了许多关于这个主题基础性的资料让我很受益（见参考资料）。

哈希表基础

1.哈希表是基于数组的数据结构

2.通过对关键字的哈希运算实现元素的快速定位

3.哈希表的重点是哈希化，哈希化负责把一个大范围的数字转化成一个小范围的数字

4.哈希化过程中会产生值冲突，这种情况有多种办法可以解决（开放地址法、链地址法）

4.1.开放地址法，通过在哈希表中寻找一个空位解决冲突问题，寻找空位的方法也有多种（线性探测、二次探测、再哈希）

4.2.链地址法，通过在哈希表单元中加入链表的方式解决

5.哈希表的重要缺点

5.1.当存储数组基本被填满时性能下降很高

5.2.对存储数组进行扩容会分别对已存储的元素重新计算哈希的过程

ConcurrentHashMap分段与锁的学习

一、结构

 

二、定位分段

这块对Key的哈希值进行移位处理，首先给定的Key在哪一段，然后从具体段中定位Hash值对应具体值对象。

 

 

三、锁

ConcurrentHashMap没有将每个方法都在同一个锁上同步并使得每次只能有一个线程访问容器，而是使用一种粒度更细的加锁机制实现更大程度的共享。这种细粒度的加锁机制体现在ConcurrentHashMap划分的Segment数组，Segment数组上各Segment元素代表了粒度更细的锁，从结构图中可以看到Segment继承自ReentrantLock可重入锁。

ConcurrentHashMap这种基于分组Segment并加锁的策略可在高并发的环境下获得更高的吞吐量。

ConcurrentHashMap实现并发的基础操作都通过sun.misc.Unsafe完成。

 

四、sun.misc.Unsafe

Unsafe类相关于一个工具类，低层调用native方法，提供了基础CompareAndSet(CAS)支持，通过CAS可以在不加锁并发情况下实现数字或引用的细粒度更新。

 

参考资料

1、Wang/Jenkins Hash算法，http://wangjunle23.blog.163.com/blog/static/11783817120138863910800

2、数据结构和算法2th

3、并发容器，http://www.blogjava.NET/xylz/archive/2010/07/20/326584.html

4、UNSAFE，http://blog.csdn.Net/aesop_wubo/article/details/7537278

5、CAS，http://blog.csdn.net/aesop_wubo/article/details/7537960

6、Java非阻塞，http://www.ibm.com/developerworks/cn/java/j-jtp04186/

 

 

 

 

REFS:http://blog.csdn.net/ybygjy/article/details/38530159