开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java——》ConcurrentHashMap -> 正文阅读

[数据结构与算法]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<K,V> lastRun = f; 
for (Node<K,V> 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);