Java容器探秘之旅 ConcurrentHashMap

发表于 | 更新于 | 分类于 | 浏览 次
字数统计: 3k

ConcurrentHashMap使用CAS操作和synchronized关键字，保证了并发安全，它不允许任何记录的键或者值为null。

此外，虽然ConcurrentHashMap类名中带有HashMap字样，但它并不是HashMap的子类。

在JDK 8-11中，ConcurrentHashMap::tryPresize方法存在bug（JDK-8214427），该bug在JDK 12中已被修复。此外，JDK12对ConcurrentHashMap进行了部分调整，因此，本文将基于JDK 12来进行分析。

存储结构

ConcurrentHashMap的存储结构与HashMap基本相同，都是数组+单链表+红黑树。

数组

与HashMap相比，数组table使用了volatile关键字。

1
transient volatile Node<K,V>[] table;

单链表

与HashMap相比，val和next字段均使用了volatile关键字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static class Node<K,V> implements Map.Entry<K,V> {
    // hash >= 0
    final int hash;
    final K key;
    // val和next均被volatile修饰
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
    ...
}

红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next,
             TreeNode<K,V> parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }
    ...
}

辅助结构

  • 特殊hash值
1
2
3
static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations
  • 用于扩容
1
2
3
4
5
6
7
8
9
// 当执行扩容操作时，插在桶的头部，hash值为-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;
    }
    ...
}
  • 用于红黑树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 当桶中为红黑树时，插在桶的根部，hash值为-2
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; // increment value for setting read lock
    ...
    TreeBin(TreeNode<K,V> b) {
        super(TREEBIN, null, null, null);
        ...
    }
    ...
}
  • 占位：用于序列化和
1
2
3
4
5
6
7
// hash值为-3
static final class ReservationNode<K,V> extends Node<K,V> {
    ReservationNode() {
        super(RESERVED, null, null, null);
    }
    ...
}

构造方法

1
2
3
4
5
6
7
8
9
10
11
public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    if (initialCapacity < concurrencyLevel)   // Use at least as many bins
        initialCapacity = concurrencyLevel;   // as estimated threads
    long size = (long)(1.0 + (long)initialCapacity / loadFactor);
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?
        MAXIMUM_CAPACITY : tableSizeFor((int)size);
    this.sizeCtl = cap;
}

插入操作

put方法

1
2
3
public V put(K key, V value) {
    return putVal(key, value, false);
}

实际执行插入操作的是putVal方法。该方法内部使用了CAS操作和同步代码块。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// onlyIfAbsent: 若为true，则只有当key不存在时，才会执行插入。
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 1.key和value都不允许为空
    if (key == null || value == null) throw new NullPointerException();
    // 2.计算键的hash值
    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;
        // 3.若表尚未初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 4.若所在的桶为空，则使用CAS操作设置头结点
            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)
            // 5.若在执行迁移操作，则帮助迁移
            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)
            // 6.若给定的key为桶中的第一个节点，并且不允许执行更新操作
            return fv;
        else {
            V oldVal = null;
            // 7.否则，先锁住桶中的第一个结点
            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.若哈希表尚未初始化，则先进行初始化操作；否则，执行2。

2.计算当前项所在的桶下标。若桶为空，则使用CAS操作，将当前项设置为桶中的第一个元素；否则，执行3。

3.若哈希表正在执行迁移操作，则让当前线程帮助执行该过程；否则，执行4。

4.若当前项为桶中的第一个结点，并且不允许执行更新操作，则循环结束；否则，执行5。

5.锁住桶中的第一个结点，然后根据桶中第一个结点的hash值判断桶中的数据结构类型。若为单链表（hash >= 0），则从前往后寻找当前项的插入（或者所在）位置，执行7；否则，执行6。

6.若桶中为红黑树，则根据二叉查找树的性质，寻找当前项的插入（或者所在）位置，执行7。

7.若桶中的元素>=树化阈值（8），则尝试将单链表转变为红黑树。

二、更新哈希表中的元素个数。

重散列

1
2
3
4
5
// 返回的值为非负
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
static final int HASH_BITS = 0x7fffffff;

初始化操作

若表为空（延迟初始化）

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
// 当sizeCtl为负数时，表示哈希表正在被初始化或者正在扩容：-1表示初始化；否则，为-(1+正在扩容的线程数量)；
// 表初始化以后，表示表的阈值（容量×负载因子）
private transient volatile int sizeCtl;
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        // 若哈希表正在被其他线程初始化，则让出处理器的使用权
        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 {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

CAS操作

  • 什么是CAS操作

CAS（Compare And Swap，比较并交换）是一种无锁算法。CAS操作包含有3个操作数：内存位置V，预期原值E，新值N。当且仅当内存位置V符合预期值E时，才会用N更新V；否则，说明已经有其他线程做了更新，则当前线程什么都不做。

  • 当桶为空时，putVal方法使用CAS操作设置桶中的第一个结点，该操作由sun.misc.Unsafe类实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static final sun.misc.Unsafe U;
// 获取第i个桶的头结点
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
// 使用CAS操作，设置第i个桶的头结点（当第i个桶为空时，才被使用）
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
// 设置第i个桶的头结点（用于删除头结点或者扩容操作中）
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

单链表与红黑树的相互转化

单链表=>红黑树

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
private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        // 1.若桶中的结点个数>=树化阈值(8)，但是表的长度<最小树化容量（64），则尝试扩容
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            tryPresize(n << 1);
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            // 2. b.hash>=0 确保桶中依然是单链表
            synchronized (b) {
                // 3.再次检查，确保头结点未发生变化
                if (tabAt(tab, index) == b) {
                    TreeNode<K,V> hd = null, tl = null;
                    // 4.将单链表（普通结点）转变为双链表（树结点）
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p =
                            new TreeNode<K,V>(e.hash, e.key, e.val,
                                              null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    // 5.红黑树的构建由TreeBin的构造方法完成
                    // 6.将桶的首结点设置为TreeBin（hash=-2），表示桶中为红黑树
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

红黑树=>单链表

1
2
3
4
5
6
7
8
9
10
11
12
static <K,V> Node<K,V> untreeify(Node<K,V> b) {
    Node<K,V> hd = null, tl = null;
    for (Node<K,V> q = b; q != null; q = q.next) {
        Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

按键取值

由于Node的val和next属性均使用了volatile关键字修饰，因此，get方法没有加锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 1.若为桶中的第一个结点
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            // 2.若正在扩容（hash = -1），或者桶中为红黑树（hash = -2）
            return (p = e.find(h, key)) != null ? p.val : null;
        // 3.若桶中为单链表
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

删除操作

1
2
3
public V remove(Object key) {
    return replaceNode(key, null, null);
}

实际执行删除操作的是replaceNode方法。

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
70
71
72
73
74
75
76
77
78
79
// value表示待设置的新值，若为null，表示删除该记录；cv表示key原来的值
final V replaceNode(Object key, V value, Object cv) {
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 1.如果表尚未初始化，或者桶为空
        if (tab == null || (n = tab.length) == 0 ||
            (f = tabAt(tab, i = (n - 1) & hash)) == null)
            break;
        else if ((fh = f.hash) == MOVED)
            // 2.如果正在扩容，则先帮助扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            boolean validated = false;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 3.1若桶中为单链表
                    if (fh >= 0) {
                        validated = true;
                        for (Node<K,V> e = f, pred = null;;) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                V ev = e.val;
                                if (cv == null || cv == ev ||
                                    (ev != null && cv.equals(ev))) {
                                    oldVal = ev;
                                    // 若新的值value不为null，则更新key对应的值
                                    if (value != null)
                                        e.val = value;
                                    else if (pred != null)
                                        // 若新的值value为null，但不是第一个结点，则删除该结点
                                        pred.next = e.next;
                                    else
                                        // 删除第一个结点
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            // 如果key不在表中
                            if ((e = e.next) == null)
                                break;
                        }
                    }
                    // 3.2若桶中为红黑树
                    else if (f instanceof TreeBin) {
                        validated = true;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        if ((r = t.root) != null &&
                            (p = r.findTreeNode(hash, key, null)) != null) {
                            V pv = p.val;
                            if (cv == null || cv == pv ||
                                (pv != null && cv.equals(pv))) {
                                oldVal = pv;
                                if (value != null)
                                    p.val = value;
                                else if (t.removeTreeNode(p))
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            if (validated) {
                if (oldVal != null) {
                    if (value == null)
                        addCount(-1L, -1);
                    return oldVal;
                }
                break;
            }
        }
    }
    return null;
}

----------本文结束感谢您的阅读----------
坚持原创技术分享，您的支持将鼓励我继续创作！