ConcurrentHashMap.md 13 KB
ConcurrentHashMap部分源码分析
jdk1.7和JDK1.8区别
jdk1.7
1、源码解析
无参构造
//空参构造
public ConcurrentHashMap() {
//调用本类的带参构造
//DEFAULT_INITIAL_CAPACITY = 16
//DEFAULT_LOAD_FACTOR = 0.75f
//int DEFAULT_CONCURRENCY_LEVEL = 16
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
}
三个参数的构造：一些非核心逻辑的代码已经省略
//initialCapacity 定义ConcurrentHashMap存放元素的容量
//concurrencyLevel 定义ConcurrentHashMap中Segment[]的大小
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
int sshift = 0;
int ssize = 1;
//计算Segment[]的大小，保证是2的幂次方数
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
//这两个值用于后面计算Segment[]的角标
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
//计算每个Segment中存储元素的个数
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
//最小Segment中存储元素的个数为2
int cap = MIN_SEGMENT_TABLE_CAPACITY;
////矫正每个Segment中存储元素的个数，保证是2的幂次方，最小为2
while (cap < c)
cap <<= 1;
//创建一个Segment对象，作为其他Segment对象的模板
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
//利用Unsafe类，将创建的Segment对象存入0角标位置
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
ConcurrentHashMap中保存了一个默认长度为16的Segment[],相当于同时支持16个并发put操作，每个Segment元素中保存了一个默认长度为2的HashEntry[]，我们添加的元素，是存入对应的Segment中的HashEntry[]中。所ConcurrentHashMap中默认元素的长度是32个，而不是16个
2、图解
总结：
JDK7 中的 ConcurrentHashMap由 Segment和 HashEntry组成，即 ConcurrentHashMap 把哈希桶数组切分成
小数组(Segment)，每个小数组有n个HashEntry组成。
将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现并发访问。
3、Segment是什么？
static final class Segment<K,V> extends ReentrantLock implements Serializable {
...
}
我们发现Segment是继承自ReentrantLock的，它可以实现同步操作，从而保证多线程下的安全。因为每个Segment之间的锁互不影响，所以我们也将ConcurrentHashMap中的这种锁机制称之为分段锁，这比HashTable的线程安全操作高效的多。
4、HashEntry是什么？
实际上HashEntry在segment中组成的是一个单向链表
//ConcurrentHashMap中真正存储数据的对象
static final class HashEntry<K,V> {
final int hash; //通过运算，得到的键的hash值
final K key; // 存入的键
volatile V value; //存入的值
volatile HashEntry<K,V> next; //记录下一个元素，形成单向链表
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
jdk1.8
1、源码分析
在jdk8的ConcurrentHashMap中一共有5个构造方法，这5个构造方法中都没有对内部的数组做初始化， 只是对一些变量的初始值做了处理
jdk8的ConcurrentHashMap的数组初始化是在第一次添加元素时完成
//传递进来一个初始容量，ConcurrentHashMap会基于这个值计算一个比这个值大的2的幂次方数作为初始容量
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
注意，调用这个方法，得到的初始容量和我们之前讲的HashMap以及jdk7的ConcurrentHashMap不同，即使你传递的是一个2的幂次方数，该方法计算出来的初始容量依然是比这个值大的2的幂次方数
//计算一个大于或者等于给定的容量值，该值是2的幂次方数作为初始容量
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
//基于一个Map集合，构建一个ConcurrentHashMap
//初始容量为16
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
.....
}
2、图解
总结：
JDK8 中的ConcurrentHashMap 选择了与 HashMap 相同的 Node数组+链表+红黑树结构在锁的实现上，抛弃了
原有的 Segment分段锁，采用 CAS+synchronized 实现更加细粒度的锁。将锁的级别控制在了更细粒度的哈希桶
数组元素级别，只需要锁住这个链表头节点(红黑树的根节点)，就不会影响其他的哈希桶数组元素的读写，大大提
高了并发度。
3、jdk1.8的put方法
1、源码分析
1.1、添加元素put/putVal方法
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
//如果有空值或者空键，直接抛异常
if (key == null || value == null) throw new NullPointerException();
//基于key计算hash值，并进行一定的扰动
int hash = (key.hashCode());
//记录某个桶上元素的个数，如果超过8个，会转成红黑树
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果数组还未初始化，先对数组进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//如果hash计算得到的桶位置没有元素，利用cas将元素添加
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//cas+自旋（和外侧的for构成自旋循环），保证元素添加安全
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//如果hash计算得到的桶位置元素的hash值为MOVED，证明正在扩容，那么协助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
//hash计算的桶位置元素不为空，且当前没有处于扩容操作，进行元素添加
V oldVal = null;
//对当前桶进行加锁，保证线程安全，执行元素添加操作
synchronized (f) {
if (tabAt(tab, i) == f) {
//普通链表节点
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//树节点，将元素添加到红黑树中
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//链表长度大于/等于8，将链表转成红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
//如果是重复键，直接将旧值返回
if (oldVal != null)
return oldVal;
break;
}
}
}
//添加的是新元素，维护集合长度，并判断是否要进行扩容操作
addCount(1L, binCount);
return null;
}
通过以上源码，我们可以看到，当需要添加元素时，会针对当前元素所对应的桶位进行加锁操作，这样一方面保证元素添加时，多线程的安全，同时对某个桶位加锁不会影响其他桶位的操作，进一步提升多线程的并发效率
总结put方法流程：
首先对于每一个放入的值，首先利用 spread 方法对 key 的 hashcode 进行一次 hash 计算，由此来确定这个值在 table 中的位置；
如果当前 table 数组还未初始化，先将 table 数组进行初始化操作；
如果这个位置是 null 的，那么使用 CAS 操作直接放入；
如果这个位置存在结点，说明发生了 hash 碰撞，首先判断这个节点的类型。如果该节点 fh==MOVED(代表 forwardingNode,数组正在进行扩容)的话，说明正在进行扩容；
如果是链表节点（fh>0）,则得到的结点就是 hash 值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到 key 相同的节点，则只需要覆盖该结点的 value 值即可。否则依次向后遍历，直到链表尾插入这个结点；
如果这个节点的类型是 TreeBin 的话，直接调用红黑树的插入方法进行插入新的节点；
插入完节点之后再次检查链表长度，如果长度大于 8，就把这个链表转换成红黑树；
对当前容量大小进行检查，如果超过了临界值（实际大小*加载因子）就需要扩容。
流程图
其他问题：
ConcurrentHashMap的get方法是否需要加锁？
get 方法不需要加锁。因为 Node 和 HashEntry的元素 value 和指针 next是用 volatile 修饰的，在多线程环境
下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。
ConcurrentHashMap不支持 key 或者 value 为 null 的原因是什么？
https://cloud.tencent.com/developer/article/1690271
jdk8中为什么使用Synchronized替换ReentrantLock?
synchronized性能提升,在 JDK6 中对 synchronized 锁的实现引入了大量的优化，会从无锁->偏向锁 ->轻量级
锁->重量级锁一步步转换就是锁膨胀的优化。以及有锁的粗化 锁消除 自适应自旋等优化。提升并发度和减少内存
开销，CAS+synchronized 方式时 加锁的对象是每个链条的头结点，相对Segment 再次提高了并发度。如果使用
可重入锁达到同样的效果，则需要大量继承自ReentrantLock的对象，造成巨大内存浪费。
ConcurrentHashMap的并发读是如何设计的?
并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。
在JDK7中，实际上就是ConcurrentHashMap中的分段锁个数，即Segment的数组长度，默认是16，这个值可
以在构造函数中设置。如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作
为实际并发度。如果并发度设置的过小，会带来严重的锁竞争问题;如果并发度设置的过大，原本位于同一个
Segment内的访问会扩散到不同的Segment中，从而引起程序性能下降。在JDK8中，已经摒弃了Segment的概
念，选择了Node数组+链表+红黑树结构，并发度大小依赖于数组的大小。