- 引言
- java7的ConcurrentHashMap
- 存储结构
- 存储流程(put)
- 扩容机制(rehash)
- java8的ConcurrentHashMap
- 存储结构
- 存储流程(put)
- 总结
- 附:参考资料
java7的ConcurrentHashMap 存储结构我们都知道,对于hashmap来说,无论是1.7或是1.8,线程都是不安全的,所以我们很少在多线程的项目中使用hashmap。因此,在多线程环境下,我们通常使用ConcurrentHashMap来保证线程安全。
本质上采用数组+链表的形式存储键值对的。但是,为了提高并发,将整个数组划分为 n 个 Segment(段) 。同时,每个 Segment 里边由若干个HashEntry 组成,每个 HashEntry之间又可以形成链表。
存储流程(put)我们可以把每个 Segment 看成是一个小的 HashMap,其内部结构和 HashMap 一模一样。
源码如下:
ConcurrentHashMap层面:
public V put(K key, V value) {
Segment s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
// hash 值无符号右移 28位(初始化时获得),然后与 segmentMask=15 做与运算
// 其实也就是把高4位与segmentMask(1111)做与运算
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
// 如果查找到的 Segment 为空,初始化
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
@SuppressWarnings("unchecked")
private Segment ensureSegment(int k) {
final Segment[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment seg;
// 判断 u 位置的 Segment 是否为null
if ((seg = (Segment)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment proto = ss[0]; // use segment 0 as prototype
// 获取0号 segment 里的 HashEntry 初始化长度
int cap = proto.table.length;
// 获取0号 segment 里的 hash 表里的扩容负载因子,所有的 segment 的 loadFactor 是相同的
float lf = proto.loadFactor;
// 计算扩容阀值
int threshold = (int)(cap * lf);
// 创建一个 cap 容量的 HashEntry 数组
HashEntry[] tab = (HashEntry[])new HashEntry[cap];
if ((seg = (Segment)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck
// 再次检查 u 位置的 Segment 是否为null,因为这时可能有其他线程进行了操作
Segment s = new Segment(lf, threshold, tab);
// 自旋检查 u 位置的 Segment 是否为null
while ((seg = (Segment)UNSAFE.getObjectVolatile(ss, u))
== null) {
// 使用CAS 赋值,只会成功一次
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
上面的源码分析了 ConcurrentHashMap 在 put 一个数据时的处理流程,大致流程如下:
- 计算要 put 的 key 的位置,获取指定位置的 Segment。
- 如果指定位置的 Segment 为空,则初始化这个 Segment:
- 检查计算得到的位置的 Segment 是否为null.
- 为 null 继续初始化,使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组
- 再次检查计算得到的指定位置的 Segment 是否为null.
- 使用创建的 HashEntry 数组初始化这个 Segment.
- 自旋判断计算得到的指定位置的 Segment 是否为null,使用 CAS 在这个位置赋值为 Segment.
- Segment.put 插入 key,value 值。
Segment层面:
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 获取 ReentrantLock 独占锁,获取不到,scanAndLockForPut 获取。
HashEntry node = tryLock() ? null : scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry[] tab = table;
// 计算要put的数据位置
int index = (tab.length - 1) & hash;
// CAS 获取 index 坐标的值
HashEntry first = entryAt(tab, index);
for (HashEntry e = first;;) {
if (e != null) {
// 检查是否 key 已经存在,如果存在,则遍历链表寻找位置,找到后替换 value
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
// first 有值没说明 index 位置已经有值了,有冲突,链表头插法。
if (node != null)
node.setNext(first);
else
node = new HashEntry(hash, key, value, first);
int c = count + 1;
// 容量大于扩容阀值,小于最大容量,进行扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
// index 位置赋值 node,node 可能是一个元素,也可能是一个链表的表头
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
- tryLock() 获取锁,获取不到使用 scanAndLockForPut 方法继续获取。
- 计算 put 的数据要放入的 index 位置,然后获取这个位置上的 HashEntry 。
- 遍历 put 新元素。【因为这里获取的 HashEntry 可能是一个空元素,也可能是链表已存在】:
- 如果这个位置上的 HashEntry 不存在:
- 如果当前容量大于扩容阀值,小于最大容量,进行扩容。
- 直接头插法插入。
- 如果这个位置上的 HashEntry 存在:
- 判断链表当前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值
- 不一致,获取链表下一个节点,直到发现相同进行值替换,或者链表表里完毕没有相同的。
- 如果当前容量大于扩容阀值,小于最大容量,进行扩容
- 直接链表头插法插入。
- 如果要插入的位置之前已经存在,替换后返回旧值,否则返回 null.
扩容机制(rehash)注:scanAndLockForPut 就是不断的自旋 tryLock() 获取锁。当自旋次数大于指定次数时,使用 lock() 阻塞获取锁。在自旋时顺表获取下 hash 位置的 HashEntry
private void rehash(HashEntrynode) { HashEntry [] oldTable = table; // 老容量 int oldCapacity = oldTable.length; // 新容量,扩大两倍 int newCapacity = oldCapacity << 1; // 新的扩容阀值 threshold = (int)(newCapacity * loadFactor); // 创建新的数组 HashEntry [] newTable = (HashEntry []) new HashEntry[newCapacity]; // 新的掩码,默认2扩容后是4,-1是3,二进制就是11。 int sizeMask = newCapacity - 1; for (int i = 0; i < oldCapacity ; i++) { // 遍历老数组 HashEntry e = oldTable[i]; if (e != null) { HashEntry next = e.next; // 计算新的位置,新的位置只可能是不便或者是老的位置+老的容量。 int idx = e.hash & sizeMask; if (next == null) // Single node on list // 如果当前位置还不是链表,只是一个元素,直接赋值 newTable[idx] = e; else { // Reuse consecutive sequence at same slot // 如果是链表了 HashEntry lastRun = e; int lastIdx = idx; // 新的位置只可能是不便或者是老的位置+老的容量。 // 遍历结束后,lastRun 后面的元素位置都是相同的 for (HashEntry last = next; last != null; last = last.next) { int k = last.hash & sizeMask; if (k != lastIdx) { lastIdx = k; lastRun = last; } } // ,lastRun 后面的元素位置都是相同的,直接作为链表赋值到新位置。 newTable[lastIdx] = lastRun; // Clone remaining nodes for (HashEntry p = e; p != lastRun; p = p.next) { // 遍历剩余元素,头插法到指定 k 位置。 V v = p.value; int h = p.hash; int k = h & sizeMask; HashEntry n = newTable[k]; newTable[k] = new HashEntry (h, p.key, v, n); } } } } // 头插法插入新的节点 int nodeIndex = node.hash & sizeMask; // add the new node node.setNext(newTable[nodeIndex]); newTable[nodeIndex] = node; table = newTable; }
java8的ConcurrentHashMap 存储结构ConcurrentHashMap 的扩容只会扩容到原来的两倍。
老数组里的数据移动到新的数组时,位置要么不变,要么变为 index+ oldSize。
参数里的 node 会在扩容之后使用链表头插法插入到指定位置
存储流程(put)可以发现 1.8 的 ConcurrentHashMap 变化比较大,不再是之前的 Segment 数组 + HashEntry 数组 + 链表,而是 Node 数组 + 链表 / 红黑树。当冲突链表达到一定长度时,链表会转换成红黑树
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 不能为空
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node[] tab = table;;) {
// f = 目标位置元素
Node f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值
if (tab == null || (n = tab.length) == 0)
// 数组桶为空,初始化数组桶(自旋+CAS)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 桶内为空,CAS 放入,不加锁,成功了就直接 break 跳出
if (casTabAt(tab, i, null,new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 使用 synchronized 加锁加入节点
synchronized (f) {
if (tabAt(tab, i) == f) {
// 说明是链表
if (fh >= 0) {
binCount = 1;
// 循环加入新的或者覆盖节点
for (Node 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 pred = e;
if ((e = e.next) == null) {
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
// 红黑树
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
总结
根据 key 计算出 hashcode 。
判断是否需要进行初始化。
即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功。
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
如果都不满足,则利用 synchronized 锁写入数据。
如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
1、Java7 中 ConcruuentHashMap 使用的分段锁,也就是每一个 Segment 上同时只有一个线程可以操作。
2、每一个 Segment 都是一个类似 HashMap 数组的结构,它可以扩容,它的冲突会转化为链表。
3、Segment 的个数一但初始化就不能改变。
附:参考资料1、Java8 中的 ConcruuentHashMap 使用的 Synchronized 锁加 CAS 的机制。
2、结构也由 Java7 中的Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树。
3、Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树,在冲突小于一定数量时又退回链表。
3W字详细解析 ConcurrentHashMap 1.7和1.8源码,再也不用担心被面试官吊打了。



