ConcurrentHashMap源码分析

小咪咪 2024-03-26 16:31 85阅读 0赞

![format_png][]

### 概述 ###

ConcurrentHashMap（CHM）是日常开发中使用频率非常高的一种数据结构，想对于普通的HashMap，CHM提供了线程安全的读写，CHM里面使用了许多比较精妙的优化&操作。本文主要对CHM的整体结构、初始化，查找，插入等做分析。  
CHM在1.8之前和之后有比较大的变动，1.8之前主要通过**Segment 分段锁** 来解决并发问题，1.8及之后就没有这些臃肿的数据结构了，其数据结构与普通的HashMap一样，都是Node数组+链表+红黑树

![format_png 1][]

一颗红黑树应满足如下性质：

1.  根节点是黑色的

*  外部节点均为黑色（图中的 leaf 节点，通常在表述的时候会省略）
 *  红色节点的孩子节点必为黑色（通常插入的节点为红色）
 *  从任一外部节点到根节点的沿途，黑节点的数目相等

![format_png 2][]

除了上面基本的数据结构之外，Node节点也是一个需要关心的数据结构，Node节点本质上是单向链表的节点，其中包含`key`、`value`、`Hash`、`next`属性

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;  
        final K key;
        volatile V val;
        volatile Node<K,V> next;
    }

### ForwardingNode节点 ###

ForwardingNode节点（简称fwd节点）继承自Node节点，主要用于扩容，该节点里面固定Hash值为MOVED(值为-1)，同时持有新表的引用

static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
    
        Node<K,V> find(int h, Object k) {
            ...
        }
    }

### TreeNode ###

TreeNode节点也继承自Node节点，用于表示红黑树上的节点，主要属性如下所示

static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // 父节点
        TreeNode<K,V> left;    // 左儿子
        TreeNode<K,V> right;   // 右儿子
        TreeNode<K,V> prev;    // 记录前驱节点，用于恢复链表
        boolean red;
    }

### TreeBin ###

TreeBin节点内部持有TreeNode节点的引用，内部实现了读写锁用于控制多线程并发在红黑树上的操作，主要属性如下所示

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;  // 红黑树根节点
        volatile TreeNode<K,V> first;  // 链表根节点，读写分离时会用到
        volatile Thread waiter;  // 当前线程
        volatile int lockState;  // 当前红黑树的锁状态
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // 读锁标记
    }

### SizeCtl ###

除了数据结构需要说明外，SizeCtl也是理解CHM十分重要的一个字段，他是一个整数，不同的值表示不同的状态

1.  当SizeCtl > 0时，表示下次扩展的阈值，其中阈值计算方式：数组长度 \* 扩展阈值（注意这里是固定的0.75）
2.  当SizeCtl = 0时，表示还没有开始初始化
3.  当sizeCtl = -1是，表示此时正在进行初始化
4.  当SizeCtl < -1时，表示此时正在进行扩展，其中高16位表示扩容标识戳，低16位表示参与扩容的线程数+1

## 初始化 ##

CHM的初始化是惰性初始化的，即当我们使用`ConCurrentHashMap<String,string> map = new ConcurrentHashMap(20);`创建一个CHM对象时，并不会真正的创建对象，而是只有在put时才会真正开始创建对象。

public ConcurrentHashMap(int initialCapacity) {
        // 只是检查参数是否合理，并设置好数组容量和扩容阈值
        if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
    }

### 初始化流程 ###

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        // 判空，注意这里是while，当线程苏醒后会记性检查直到初始化完毕
        while ((tab = table) == null || tab.length == 0) {
            // 如果其他线程正在初始化，则让出cpu
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 当前线程尝试获取创建数组的重任
                try {
                    // 这里需要再进行判断是否为空，防止当前线程创建完毕后又有其他线程进来重复创建
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        // 设置阈值为0.75n
                        sc = n - (n >>> 2);
                    }
                } finally {

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ffabc79e0e7d451db2192d6da45fc9bc.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/81afc8af596141409295e76fac7ff685.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c2581f42973f490992f3325aaa090e13.png