ConcurrentHashMap的原理

发表于 | 更新于 | 分类于
字数统计 | 阅读时长

👌ConcurrentHashMap的原理？

题目详细答案

ConcurrentHashMap 是 Java 中一种高效的线程安全哈希表，主要用于在多线程环境下进行高并发的读写操作。它的设计和实现使得在大多数情况下能够提供比其他同步哈希表（如 HashMap）更高的并发性能。以下是 ConcurrentHashMap 的主要原理和机制

分段锁机制

在早期版本（Java 7及之前），ConcurrentHashMap 使用了分段锁机制（Segmented Locking）来实现高并发性。

分段锁：ConcurrentHashMap 将整个哈希表分成多个段（Segment），每个段维护一个独立的哈希表和锁。这样，在不同段上的操作可以并发进行，从而提高并发度。

1
2
3
4
5
6
7
8
9
10
// 伪代码示例
class ConcurrentHashMap<K, V> {
    Segment<K, V>[] segments;
    
    static class Segment<K, V> {
        final ReentrantLock lock = new ReentrantLock();
        HashEntry<K, V>[] table;
        // 其他字段和方法
    }
}

锁粒度：由于每个段都有自己的锁，只有在操作同一个段时才需要竞争锁，这大大降低了锁竞争的几率，提高了并发性能。

CAS 操作和无锁机制

在 Java 8 及之后，ConcurrentHashMap 进行了重构，摒弃了分段锁机制，转而采用了更加细粒度的锁和无锁机制（CAS 操作）。

CAS 操作：CAS（Compare-And-Swap）是一种无锁的原子操作，用于在不加锁的情况下实现线程安全。ConcurrentHashMap使用Unsafe类中的 CAS 方法来更新某些字段，从而避免了锁的开销。

1
2
3
4
// 伪代码示例
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);
}

细粒度锁：在 Java 8 中，ConcurrentHashMap使用了更加细粒度的锁（synchronized和ReentrantLock），只在必要时锁定特定的桶（bin）或节点，从而进一步提高并发性能。

红黑树

为了应对哈希冲突，ConcurrentHashMap 在链表长度超过一定阈值（默认是8）时，将链表转换为红黑树，以提高查找效率。

链表：在哈希冲突较少时，使用链表存储冲突的键值对。

红黑树：当链表长度超过阈值时，转换为红黑树，以便在大量冲突时仍能保持较高的查找效率。

1
2
3
4
// 伪代码示例
if (binCount >= TREEIFY_THRESHOLD) {
    treeifyBin(tab, hash);
}

扩容机制（Rehashing）

ConcurrentHashMap 采用了渐进式扩容机制来避免扩容过程中长时间的全表锁定。

渐进式扩容：在扩容过程中，ConcurrentHashMap并不会一次性将所有数据迁移到新的哈希表中，而是采用渐进式扩容的方式，在每次插入或删除操作时，逐步迁移部分数据。

1
2
3
4
// 伪代码示例
void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
    // 渐进式迁移数据
}

读写操作

读取操作：读取操作大部分情况下是无锁的，因为ConcurrentHashMap使用了volatile变量和 CAS 操作来保证读取的可见性和一致性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 伪代码示例
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) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // 其他读取逻辑
    }
    return null;
}

写入操作：写入操作则需要在必要时使用锁或 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
// 伪代码示例
V put(K key, V value) {
    return putVal(key, value, false);
}

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;
        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, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        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, null);
                                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;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

/gr29od28mo8ulrk5>

wechat
天生我才必有用