深入理解 JDK 1.8 ConcurrentHashMap 的线程安全机制

• ConcurrentHashMap 的用途和重要性

1. 用途

• 多线程环境下的并发访问： ConcurrentHashMap 是 Java 并发编程中的一个重要工具，用于在多线程环境下安全地进行并发访问。它提供了一种线程安全的哈希表实现，可以用于存储键值对数据，并且能够支持多个线程同时对数据进行读写操作。

2. 重要性

• 线程安全性： 在多线程编程中，线程安全性是一个非常重要的考虑因素。ConcurrentHashMap 提供了一种线程安全的哈希表实现，能够保证在并发环境下的数据一致性和可靠性。它采用了一些特殊的技术来避免线程间的竞争条件，从而确保了数据的正确性和完整性。
• 性能优化： 与传统的同步机制相比，ConcurrentHashMap 在高并发环境下表现更优秀。它采用了一种分段锁的机制，使得多个线程可以同时访问不同的段，从而提高了并发性能。此外，在 JDK 1.8 中，ConcurrentHashMap 还引入了一种基于 CAS（Compare and Swap）操作的锁-Free机制，进一步提高了并发性能。
• 可扩展性： ConcurrentHashMap 的设计考虑了扩展性和性能的问题。它将哈希表分成多个段，每个段都有自己的锁，这样可以减少锁的竞争，提高了并发性能。同时，它还支持动态扩容和自动缩容，能够自动调整容量以适应不同的负载和并发需求。

综上所述，ConcurrentHashMap 在多线程编程中具有重要的作用和优势。它不仅保证了线程安全性，还提高了并发性能和可扩展性，是开发高性能并发应用程序的重要工具之一。

JDK 1.8 中 ConcurrentHashMap 的线程安全机制

为什么说HashMap线程不安全，而ConcurrentHashMap就线程安全

HashMap在多线程put的时候，当产生hash碰撞的时候，会导致丢失数据，因为要put的两个值hash相同，如果这个对于hash桶的位置个数小于8，那么应该是以链表的形式存储，由于没有做通过，后面put的元素可能会直接覆盖之前那个线程put的数据，这样就导致了数据丢失。

1. CAS机制

首先需要了解两个规则：

• volatile的happens-before原则：对于一个volatile变量的写一定可见于随后的读（happens-before）
• CAS 同时具有volatile的读和写的内存语义

put方法：

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 获取 ReentrantLock 独占锁，获取不到，scanAndLockForPut 获取。
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        // 计算要put的数据位置
        int index = (tab.length - 1) & hash;
        // CAS 获取 index 坐标的值
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                // 检查是否 key 已经存在，如果存在，则遍历链表寻找位置，找到后替换 value
                K k;
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                // first 有值没说明 index 位置已经有值了，有冲突，链表头插法。
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                // 容量大于扩容阀值，小于最大容量，进行扩容
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    // index 位置赋值 node，node 可能是一个元素，也可能是一个链表的表头
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

可以看出，使用CAS是在两个地方，一个地方是使用在initTable(),一个是尝试进行插入的时候 if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))

在initTable方法里也使用到了CAS来保障线程的安全：

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        //　如果 sizeCtl < 0 ,说明另外的线程执行CAS 成功，正在进行初始化。
        if ((sc = sizeCtl) < 0)
            // 让出 CPU 使用权
            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;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

可以看到ConcurrentHashMap在初始化的时候也使用到了这种while循环+CAS的机制来保证线程安全， 从源码中可以发现 ConcurrentHashMap 的初始化是通过自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl （sizeControl 的缩写），它的值决定着当前的初始化状态。

1. -1 说明正在初始化，其他线程需要自旋等待
2. -N 说明 table 正在进行扩容，高 16 位表示扩容的标识戳，低 16 位减 1 为正在进行扩容的线程数
3. 0 表示 table 初始化大小，如果 table 没有初始化
4. 大于0表示 table 扩容的阈值，如果 table 已经初始化

2.Put的流程

由于hashmap不会在对象第一次初始化的时候就完成数组的初始化，而是在put进第一个元素的时候开始初始化，所有我们可以总结一下的流程：

• 根据 key 计算出 hashcode 。
• 判断是否需要进行初始化。
• 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
• 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
• 如果都不满足，则利用 synchronized 锁写入数据。
• 如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥64 时才会将链表转换为红黑树

3. Get的流程

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // key 所在的 hash 位置
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果指定位置元素存在，头结点hash值相同
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                // key hash 值相等，key值相同，直接返回元素 value
                return e.val;
        }
        else if (eh < 0)
            // 头结点hash值小于0，说明正在扩容或者是红黑树，find查找
            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;
}

总结来说，Get流程是比较简单的，并没有对读的操作加锁。 总结一下 get 过程：

1. 根据 hash 值计算位置。
2. 查找到指定位置，如果头节点就是要找的，直接返回它的 value.
3. 如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。
4. 如果是链表，遍历查找之。

结论

Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。

参考资料

• javaguide.cn/java/collec…