ConcurrentHashMap源码阅读

发表于 更新于 分类于

ConcurrentHashMap是一个支持检索操作完全并发、更新操作高并发的哈希表。该类遵循与 java.util.Hashtable 相同的功能规范，并包含与Hashtable 每个方法对应的版本。不过，尽管所有操作都是线程安全的，检索操作不需要加锁，也不支持锁定整个表以阻止所有访问。此类可与依赖其线程安全但不依赖其同步细节的程序中的Hashtable完全互操作。

get

这次先从get方法开始看起，get是读操作，读操作是无锁的。

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
/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code key.equals(k)},
 * then this method returns {@code v}; otherwise it returns
 * {@code null}.  (There can be at most one such mapping.)
 *
 * <p>A return value of {@code null} does not necessarily
 * indicate that the map contains no mapping for the key;
 * it's also possible that the map explicitly maps the key to
 * {@code null}.  The {@link #containsKey containsKey} method
 * may be used to distinguish these two cases.
 *
 * @see #put(Object, Object)
 */
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    // 1. 计算hash值，并定位到桶数组中的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 2. 遍历链表，查找key对应的节点
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

接下来看一看它和HashMap在内部实现上的一些区别。

spread

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
/**
 * Spreads (XORs) higher bits of hash to lower and also forces top
 * bit to 0. Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 *
 * 将哈希值的高位通过异或运算（XOR）传播到低位，并强制最高位为0。
 * 由于哈希表的容量总是2的幂次方，只有低位参与桶索引的计算，
 * 如果哈希值只在高位不同，则会发生碰撞。通过这种方式将高位信息混合到低位，
 * 可以减少碰撞，提高哈希分布的均匀性。
 * 这种做法在速度、实用性和位扩散质量之间做了权衡。
 * 由于很多哈希集合本身分布较好，且对于大量碰撞会用红黑树处理，
 * 所以这里只做了简单的异或操作，既能降低碰撞，也能让高位信息参与索引计算。
 */
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

前面运算这里不解释，跟hashMap一样，主要看后面的& HASH_BITS。HASH_BITS是0x7fffffff，换算下来是2147483649，int的最大值
作用是消除负数。
为什么要消除负数呢？因为Java中的不存在无符号整数，int是有符号的，最高位是符号位，1是负数，0是正数。
正数的原码、反码、补码都是一样的。
负数的原码：是对应的正数的二进制，但是符号位是1。
符号位是区分正负数用的，1是负数，0是整数(符号位就是最高位的意思，左边第一位)
负数的反码：是除符号位，其余的取反
负数的补码：是反码+1
并且，在计算机系统中，数值一律用补码来存储。这是因为补码在处理加减运算和表示零时具有显著的优势。
举个例子：
-5的原码是：10000000000000000000000000000101
反码是：11111111111111111111111111111010
补码是：11111111111111111111111111111011
HASH_BITS换算下来的二进制是：011111111111111111111111111111111
而与运算的运算规则就是对两个二进制数的每一位进行比较。只有当两个对应位都为1时，结果才为1，否则为0。
因此hash & HASH_BITS，不管hash是正还是负，结果都会转成正数，因为HASH_BITS的符号位是0，& 下来的最高位肯定是0，也就是正数。
spread(int h) 的作用其实就是避免hash值是负数，大概是因为ConcurrentHashMap内置了MOVED、TREEBIN、RESERVED
这3个hash是负数，为了避免冲突吧。

tabAt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * Atomic access methods are used for table elements as well as
 * elements of in-progress next table while resizing.  All uses of
 * the tab arguments must be null checked by callers.  All callers
 * also paranoically precheck that tab's length is not zero (or an
 * equivalent check), thus ensuring that any index argument taking
 * the form of a hash value anded with (length - 1) is a valid
 * index.  Note that, to be correct wrt arbitrary concurrency
 * errors by users, these checks must operate on local variables,
 * which accounts for some odd-looking inline assignments below.
 * Note that calls to setTabAt always occur within locked regions,
 * and so require only release ordering.
 *
 * 原子访问方法用于table元素以及扩容时的next table元素。
 * 所有tab参数的使用都需要调用方进行null检查。
 * 调用方还会偏执地预先检查tab的长度不为0，确保(hash & (length-1))形式的索引是有效的。
 * 这些检查必须基于局部变量，以防止并发错误。
 * setTabAt方法的调用总是在加锁区域内，因此只需要release语义。
 */
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    // 通过Unsafe的getReferenceAcquire方法原子性地获取tab数组指定位置的元素
    return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE);
}

这段代码的作用是原子性地读取哈希表（table）指定槽位（bin）上的节点，用于并发场景下安全地获取 ConcurrentHashMap 的桶元素。
tabAt 方法通过 Unsafe.getReferenceAcquire，以原子方式读取数组 tab 下标 i 处的元素，保证可见性和并发安全。
主要用于高并发下的哈希表读操作，比如 get、put、resize 等，避免数据竞争。
((long)i << ASHIFT) + ABASE 计算出数组元素的真实内存偏移量。

find

在 public V get(Object key) 方法中，eh < 0 表示当前桶的第一个节点（e）的 hash 字段是负数。这种情况有三种特殊节点：

  1. MOVED（-1）：表示该桶是一个转发节点（ForwardingNode），说明哈希表正在扩容，当前桶的数据已经迁移到新的表，需要在新表中继续查找。
  2. TREEBIN（-2）：表示该桶是树形结构的根节点（TreeBin），需要在红黑树中查找目标 key。
  3. RESERVED（-3）：表示该节点是占位节点（ReservationNode），用于并发计算时的占位。
    因此，eh < 0 时，get 方法会通过 e.find(h, key) 进入特殊的查找逻辑（如树查找或迁移查找），而不是普通链表查找。

put

put内部依然是putVal,这是高并发下安全插入/更新元素的主流程，兼顾性能和线程安全。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent // check first node without acquiring lock
                 && fh == hash
                 && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                 && (fv = f.val) != null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

主要作用和流程如下：

  1. 参数校验：key 或 value 为 null 时抛出异常。
  2. 计算 hash：对 key 的 hashCode 做扰动处理并去除负数，减少哈希冲突。
  3. 定位桶：通过 (n - 1) & hash 计算桶下标。
  4. 初始化表：如果 table 未初始化或长度为 0，则初始化。
  5. 无锁插入：如果目标桶为空，CAS 方式直接插入新节点，无需加锁。
  6. 扩容迁移：如果桶头节点 hash 为 MOVED，说明正在扩容，协助迁移。
  7. 只插入不存在的 key：如果 onlyIfAbsent 且 key 已存在，直接返回旧值。
  8. 加锁插入/更新：否则对桶头节点加锁，链表或树结构中查找/插入/更新节点。
    • 链表：遍历查找，存在则更新，不存在则尾插新节点。
    • 树：委托 TreeBin 处理。
    • ReservationNode：递归更新异常。
  9. 链表转树：如果桶内节点数超过阈值，链表转红黑树。
  10. 计数：插入成功后更新元素计数。
  11. 返回：返回旧值或 null。