Java——》ConcurrentHashMap

一、存储结构

JDK1.7：数组 + 链表
JDK1.8：数组 + 链表 + 红黑树

Q：为什么JDK1.8中追加了红黑树（红黑树是平衡二叉树）？
A：链表查询的时间复杂度为On，链表过长，查询速度慢
红黑树查询的时间复杂度是Ologn

1、链表长度到8，一定会转换为红黑树吗？

答案：必须达到数组长度>=64，并且某一个桶下的链表长度到8，才会转换为红黑树
原因：数组查询效率更快（数据平均的分散在数组上，才是最快的）

1）ConcurrentHashMap规定数组长度：64

2）HashMap规定数组长度：64

2、为什么链表长度为8，才会转为红黑树？

原因：泊松分布（概率学）

3、红黑树什么情况下会转换为链表？

答案：链表长度为6时，才可能会转换为链表

二、散列算法

散列算法：
HashMap、ConcurrentHashMap如何基于key进行运算，并将key-value存储到数组的某一个节点上，或者是挂载到下面的链表或者红黑树上

1、散列算法相关源码

2、散列算法介绍

参考链接：Java——》运算

// 散列算法的调用 
int hash = spread(key.hashCode()); 

// 散列算法的具体实现 
static final int spread(int h) {     
    return (h ^ (h >>> 16)) & HASH_BITS; 
} 


// 计算索引位置：基于数组长度和hash值，tab[(n - 1) & hash])
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null)

第一步：h

h = key.hashCode()，是一个int类型值

第二步：h >>> 16

h >>> 16，表示无符号右移16位

第三步：h ^ (h >>> 16)

h ^ (h >>> 16)，表示进行 ^运算（相同为0，不同为1）

第四步：(h ^ (h >>> 16)) & HASH_BITS

HASH_BITS = 0x7fffffff ，是一个16进制值
h的二进制：01010101 11111111 01010101 01010101
h >>> 16的二进制：00000000 00000000 01010101 11111111
h ^ (h >>> 16)的二进制：01010101 11111111 00000000 10101010
HASH_BITS 的二进制：01111111 11111111 11111111 11111111
(h ^ (h >>> 16)) & HASH_BITS的二进制：01010101 11111111 00000000 10101010

3、散列算法中为什么要执行一个&运算？

&运算的目的是为了保证hash值一定是正数，因为hash值为负数有特殊含义
二进制的最高位是是符号位，HASH_BITS的最高位是0，所以&运算结果的最高位一定是0

4、散列算法中hash有什么特殊含义？

// Hash值为-1，代表当前位置数据已经被迁移到新数组中（正在扩容！） 
static final int MOVED 		= -1; // hash for forwarding nodes 
// Hash值为-2，代表当前索引位置下是一颗红黑树！ 
static final int TREEBIN 	= -2; // hash for roots of trees 
// Hash值为-3，代表当前索引位置已经被占座了 
static final int RESERVED 	= -3; // hash for transient reservations

1）MOVED相关源码

2）RESERVED相关源码

三、保证安全的方式 1、Hashtable

实现方式：方法追加上 **synchronized **保证线程安全（速度巨慢）

2、JDK1.7的ConcurrentHashMap

实现方式：使用分段锁 **Segment **，原理就是ReentrantLock。

3、JDK1.8的ConcurrentHashMap：

实现方式：基于 **CAS **和 **synchronized **同步代码块实现的线程安全

四、扩容 1、sizeCtl

new ConcurrentHashMap()时，数组并不会初始化，而是只有在第一次put()操作时，才会初始化数组

表初始化和调整大小控件。
如果为负值，则表正在初始化或调整大小：-1用于初始化，否则-（1+活动调整大小线程的数量）
。否则，当table为null时，将保留创建时使用的初始表大小，默认值为0。
初始化后，保存下一个要调整表大小的元素计数值。

private transient volatile int sizeCtl;

sizeCtl = -1：代表当前ConcurrentHashMap的数组正在初始化
sizeCtl < -1：代表当前ConcurrentHashMap的数组正在扩容
sizeCtl = -2：代表有1个线程在扩容
sizeCtl = -3：代表有2个线程在扩容
sizeCtl = 0：代表当前ConcurrentHashMap的数组还没初始化呢
sizeCtl > 0：2个含义
如果数组还没初始化，代表初始数组长度
如果数组已经初始化了，代表扩容阈值

数组初始化相关源码

2、ConcurrentHashMap扩容触发条件

1）数组长度达到了扩容的阈值（阈值 = 数组长度 * 负载因子 = 64*0.75）
2）链表达到了8，但是数组长度没到64，触发扩容
3）在执行putAll操作时，会直接优先判断是否需要扩容tryPresize()，真正扩容执行transfer()

以上场景，ConcurrentHashMap会触发helpTransfer()，也就是多线程扩容。

3、扩容戳介绍

扩容戳是一个负数
高16位：标识当前old数组的长度，用来保证多线程扩容是从同样的长度开始扩容到2倍长度
低16位：标识当前正在扩容的线程个数-1

因为在扩容时，是基于原数组的长度来做计算的，所以在扩容时，需要保证多个线程扩容是的长度都是一样的。
线程A（32 - 64），线程B（32 - 64）是可以同时进行扩容。
线程C（64 - 128）是不可以同上面线程一起扩容。

4、扩容步骤

private static int RESIZE_STAMP_BITS = 16;
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;


// 基于原数组长度，计算扩容戳
static final int resizeStamp(int n) {     
    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); 
}

假如现在要从32扩容到64，n = 32

第一步：Integer.numberOfLeadingZeros(n)

n前面有几个0，32前面有26个0

第二步：(RESIZE_STAMP_BITS - 1)

RESIZE_STAMP_BITS - 1 = 16 - 1 = 15

第三步：1 << (RESIZE_STAMP_BITS - 1)

1往左移 15位

第四步：Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1))

32的二进制：00000000 ‭00000000 ‭00000000 ‭00100000‬
26的二进制：‭00000000 ‭00000000 ‭00000000 ‭00011010‬
1往左移15位的二进制：00000000 ‭00000000 ‭10000000 ‭00000000
| 运算结果的二进制：00000000 ‭00000000 ‭10000000 ‭00011010‬

第五步：rs << RESIZE_STAMP_SHIFT

rs左移16位

第六步：(rs << RESIZE_STAMP_SHIFT) + 2

rs<<16的二进制：‭10000000 ‭00011010‬ 00000000 ‭00000000
+2的二进制：10000000 ‭00011010‬ 00000000 ‭00000010

5、扩容流程

假如现在要从32扩容到64，n = 32
ConcurrentHashMap在扩容时，会先指定每个线程每次扩容的长度，最小值为16（根据数组长度和CPU内核去指定每次扩容长度）。
开始扩容，而开始扩容的线程只有一个，第一个扩容的线程需要把新数组new出来。
有了新数组之后，其他线程再执行transfer()（可能从helpTransfer()进来），其他线程进来后，对扩容戳进行+1操作，也就是如果1个线程低位是-2，那么2个线程低位为-3
每次迁移时，会从后往前迁移数据，也就是说两个线程并发扩容：
线程A负责索引位置：16~31
线程B负责索引位置：15~0
是一个桶一个桶的去迁移数据，每次迁移完一个桶之后，会将ForwardingNode设置到老数组中，证明当前老数组的数据已经迁移到新数组了！
在迁移链表数据时，会基于lastRun机制，提升效率

6、lastRun机制

提前将链表数据进行计算，算出链表的节点需要存放到哪个新数组位置，将不同位置算完打个标记

Node lastRun = f; 
for (Node p = f.next; p != null; p = p.next) {     
    int b = p.hash & n;     
    if (b != runBit) {         
        runBit = b;         
        lastRun = p;     
    } 
}

7、老数组数据放到新数组的哪个位置

:::info
HashMap和ConcurrentHashMap计算原理一致
案例：oldCap=16 newCap=32
oldCap的二进制：00000000 00000000 00000000 00010000

如果e.hash的二进制：01010101 01010101 01010101 01010101
e.hash & oldCap的二进制：00000000 00000000 00000000 00010000

如果e.hash的二进制：01010101 01010101 01010101 01000101
e.hash & oldCap的二进制：00000000 00000000 00000000 00000000
结果只有2种情况：要么是0，要么是老数组长度
:::

// lo就是放到新数组的原位置（老数组放到索引为1的位置，新数组也放到索引为1的位置） 
// hi就是放到新数组的原位置 + 老数组长度的位置（老数组放到索引为1的位置，新数组放到17位置） 
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

8、ConcurrentHashMap扩容处的BUG

https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427
在JDK12中，修复了一部分。

Java——》ConcurrentHashMap

Java相关栏目本月热门文章