本文首发于 vivo互联网技术 微信公众号
链接：
作者：vivo 游戏技术团队
一、概述
ConcurrentHashMap (以下简称C13Map) 是并发编程出场率最高的数据结构之一，大量的并发CASE背后都有C13Map的支持，同时也是JUC包中代码量最大的组件(6000多行)，自JDK8开始Oracle对其进行了大量优化工作。
本文从 HashMap 的基础知识开始，尝试逐一分析C13Map中各个组件的实现和安全性保证。
二、HashMap基础知识
分析C13MAP前，需要了解以下的HashMap知识或者约定：
- 哈希表的长度永远都是2的幂次方，原因是hashcode%tableSize==hashcode&(tableSize-1)，也就是哈希槽位的确定可以用一次与运算来替代取余运算。
- 会对hashcode调用若干次扰动函数，将高16位与低16位做异或运算，因为高16位的随机性更强。
- 当表中的元素总数超过tableSize * 0.75时，哈希表会发生扩容操作，每次扩容的tableSize是原先的两倍。
- 下文提到的槽位(bucket)、哈希分桶、BIN均表示同一个概念，即哈希table上的某一列。
- 旧表在做搬运时i槽位的node可以根据其哈希值的第tableSize位的bit决定在新表上的槽位是i还是i+tableSize。
- 每个槽位上有可能会出现哈希冲突，在未达到某个阈值时它是一个链表结构，达到阈值后会升级到红黑树结构。
- HashMap本身并非为多线程环境设计，永远不要尝试在并发环境下直接使用HashMap，C13Map不存在这个安全问题。
三、C13Map的字段定义
C13Map的字段定义
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|