ConcurrentHashMap 的存在意义
我们知道,Java中有了HashMap和HashTable 那为何还需要ConcurrentHashMap
对比HashMap
ConcurrentHashMap 数据存储结构是:数组+链表+红黑树
HashMap 不是线程安全的,不能在多线程场景使用。
两者相同之处:
- 数组、链表结构几乎相同,因此底层对数据结构的操作思路是相同的
- 都实现 Map 接口,多数方法也都是相同的
两者不同之处:
- 红黑树结构略有不同,HashMap的红黑树节点叫做TreeNode,TreeNode不仅有属性还维护着红黑树的结构,比如查找、新增等;ConcurrentHashMap中红黑树拆分成两块,TreeNode仅维护属性和查找功能, 新增TreeBin来维护红黑树的结构,负责根节点的加锁和解锁
- ConcurrentHashMap新增ForwardingNode转移节点,扩容会用到,该节点用来保证扩容时线程安全
对比HashTable
- Hashtable使用synchronized保证线程安全,当一个线程访问其中一个同步方法时,其他线程是不能访问其同步方法(竞争同一把锁)。会导致在put数据时,其他线程也不能get数据之类操作,导致并发效率非常低.
- ConcurrentHashMap使用分段锁(Segment)技术,将数组分成多段,每个分段锁维护着 HashEntry, 修改数据时先将这一段锁起来,其他线程此时要操作其他分段的数据互不干扰. 操作不是同一分段数据, 线程间不存在竞争关系,大大提高并发效率.
ConcurrentHashMap部分源码分析
数据初始化
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//1. 通过死循环来保证一定能初始化成功,通过对sizeCtl变量的赋值来保证只被初始化一次
while ((tab = table) == null || tab.length == 0) {
//2. sizeCtl小于0,表示有其他线程正在初始化,释放当前CPU的调度权,重新发起锁的竞争,自旋
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//3. CAS 赋值,保证当前只有一个线程正在初始化,如果第一次初始化这里会将sizeCtl的值赋值为-1,
//保证了数组的初始化安全性
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//4. 可能执行到这里的时候,table已经不为空了,双重check
if ((tab = table) == null || tab.length == 0) {
//5. 初始化数组
int n = (sc > 0) sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//>>>:无符号右移,无论是正数还是负数,高位通通补0
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
从上面源码看出使用自旋+CAS+双重check来保证数组初始化时的线程安全.
获取数据:Get
ConcurrentHashMap 读取数据比较简单,先获取数组下标,然后通过判断数组下标的 key 是否与目标 key 一致,相等直接返回。如果下标的槽点是链表或红黑树,分别调用相应的查找数据方法,整体思路和 HashMap 很像
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//计算hashcode
int h = spread(key.hashCode());
//不是空的数组 && 并且当前索引的槽点数据不是空的
//否则该key对应的值不存在,返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//槽点第一个值和key相等,直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//如果是红黑树或者转移节点,使用对应的find方法
else if (eh < 0)
return (p = e.find(h, key)) != null p.val : null;
//如果是链表,遍历查找
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
扩容机制
ConcurrentHashMap 扩容时机是和HashMap相同,都在put方法最后一步检查一下是否需要扩容.但实现上有差别:
- 需要把老数组的值全部拷贝到扩容之后的新数组上,先从数组的队尾开始拷贝;
- 拷贝数组的槽点时,先把原数组槽点锁住,保证原数组槽点不能操作,成功拷贝到新数组时,把原数组槽点赋值为转移节点;
- 若有新数据正好需要put到此槽点,发现槽点为转移节点,会一直等待,所以在扩容完成之前,该槽点对应的数据是不会发生变化;
- 从数组的尾部拷贝到头部,每拷贝成功一次,就把原数组中的节点设置为转移节点;
- 直到所有数组数据都拷贝到新数组时,直接把新数组赋值给数组容器,拷贝即完成。