Java ConcurrentHashMap 高并发安全实现原理解析

本文首发于 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