java8 中ConcurrentHashMap

在 JDK 1.8 中，ConcurrentHashMap 通过 CAS（Compare-And-Swap） 和 synchronized 实现高并发和线程安全。它采用了一种更简洁的方式来提高并发性能，相较于 JDK 1.7 中的分段锁设计，JDK 1.8 的实现更优，减少了锁竞争，并使用红黑树优化了链表冲突。

1. `ConcurrentHashMap` 的核心数据结构

哈希桶数组：ConcurrentHashMap 的核心是一个数组，称为 Node[] table，每个元素是一个链表/红黑树的头节点。
链表/红黑树节点：当哈希冲突发生时，同一个桶中的多个节点以链表或红黑树的形式存储。
- 链表节点：在冲突较少时，使用链表存储。
- 红黑树节点：当链表长度超过一定阈值（8个节点）时，链表会转换为红黑树，以提高查找性能。

2. `put()` 方法的实现逻辑

2.1 基本插入逻辑

步骤 1：计算哈希值和桶位置
- 通过键的 hashCode() 计算哈希值，并通过 哈希值 % table.length 确定键值对在哈希表中的位置。
步骤 2：插入节点
- 如果目标桶（槽位）为空，使用 CAS 插入节点。javaCopy codeif (tab[i] == null) { if (CAS(tab, i, null, new Node<>(hash, key, value))) { return null; // 插入成功 } }
- 如果目标桶不为空，则会进入桶的链表/红黑树结构：
  - 链表插入：在链表中遍历所有节点，若键已存在则更新值，否则在链表尾部插入新节点。
  - 红黑树插入：若桶已经被转换为红黑树，则在红黑树中插入新节点。
- 当多个线程同时插入同一个桶时，ConcurrentHashMap 会通过 synchronized 锁定该桶，以确保插入操作的原子性。

2.2 CAS 操作

在插入节点的过程中，ConcurrentHashMap 首先尝试使用 CAS 来确保在并发环境下插入的新节点是唯一的。
若 CAS 操作失败，说明有其他线程同时操作此桶，则会退回到synchronized，对桶加锁。

2.3 扩容触发

扩容条件：当元素数量超过阈值（table.length * loadFactor）时，会触发扩容。
在扩容期间，插入操作可能会被阻塞，直到扩容完成。

3. `get()` 方法的实现逻辑

3.1 基本读取逻辑

步骤 1：计算哈希值和桶位置
- 与 put() 类似，通过键的 hashCode() 计算哈希值，并定位到具体的桶。
步骤 2：获取节点值
- 通过遍历桶的链表/红黑树结构，查找与键匹配的节点，并返回对应的值。

3.2 高并发读取

get() 方法是无锁的。由于 ConcurrentHashMap 的结构是基于无锁的设计，读取操作不会使用锁，即使在扩容期间，get() 也可以继续工作。

3.3 延迟读取

在 ConcurrentHashMap 中，get() 方法的设计是延迟读取的，即使在扩容或插入的过程中，get() 也会尽量读取到最接近最新的值，而不会阻塞等待。

4. 扩容的实现逻辑

4.1 扩容触发

当 ConcurrentHashMap 中的元素个数超过容量阈值时，扩容会被触发。扩容时，哈希表的大小会增加一倍（newCapacity = oldCapacity * 2）。

4.2 扩容的多线程支持

ConcurrentHashMap 采用了分布式扩容，允许多个线程同时帮助完成扩容过程，降低单个线程的负担和扩容时间。

4.3 扩容步骤

初始化新数组：首先，创建一个新数组，其容量是原数组的两倍。
分桶迁移：多个线程并发地迁移旧数组的桶到新数组。
- 每个线程在迁移时，使用分区锁来锁定特定的桶，避免冲突。
rehash 处理：在迁移过程中，将原链表/红黑树重新哈希到新数组的相应位置。

4.4 扩容对读取和写入的影响

在扩容过程中，put() 操作会首先完成当前线程负责的部分扩容工作，然后继续插入。
get() 方法在扩容过程中仍然可以正常工作，因为新旧数组都在访问范围内，JVM 保证了对数据的一致性。

5. CAS 和 synchronized 的协同工作

CAS 操作：
- CAS 操作是乐观锁的一种实现，它通过不断重试来确保操作的原子性。CAS 适用于插入和修改操作，它允许多个线程在无锁的情况下更新不同的槽位，从而提高并发性能。
synchronized 操作：
- 当 CAS 失败时（如发生哈希冲突），ConcurrentHashMap 会使用 synchronized 来对单个桶加锁，以确保操作的线程安全。
- 通过对桶的局部加锁，ConcurrentHashMap 能够有效地减少锁的粒度，从而提高并发性能。

6. 总结

ConcurrentHashMap 中的高并发和线程安全性依赖于 CAS 和 synchronized 的结合，通过无锁和局部加锁的策略，实现了高效的插入、读取和扩容操作。
在读操作中，ConcurrentHashMap 采用无锁设计，实现了高效的并发读取。
在写操作和扩容时，通过局部加锁和多线程分布式扩容，提高了并发效率，避免了全局锁带来的性能瓶颈。

这种设计使得 ConcurrentHashMap 能够在高并发环境下，保证读写的高效性和一致性，同时也适用于分布式缓存、并发计数器等场景。

在 JDK 1.8 中，ConcurrentHashMap 采用了一种特殊的机制来确保读取操作不会受到扩容的影响。在扩容过程中，get() 方法依旧能够正常地读取数据，且可以读取到新数组和旧数组上的值，这就是 ConcurrentHashMap 在高并发和扩容时能够保持一致性的关键之一。

1. 扩容对 `get()` 方法的影响

在扩容时，ConcurrentHashMap 能够做到边扩容边读取，即 get() 操作在扩容期间依然能够正确地读取到元素值。这是通过一种叫做“逐步迁移”的扩容策略来实现的。

1.1 扩容触发

当 ConcurrentHashMap 的负载超过了阈值（table.length * loadFactor）时，会触发扩容。这种扩容是渐进式的，每个线程在执行插入操作时，都会帮助进行部分扩容。

1.2 逐步迁移的设计

新数组（nextTable）：扩容时，ConcurrentHashMap 会创建一个新数组 nextTable，其容量是原数组的两倍。
转移槽位：在扩容过程中，每个线程负责将一个或多个旧桶（bucket）的元素转移到新桶中。
转移标志：为每个槽位设置一个特殊的节点标记（ForwardingNode），标识该槽位已被迁移或正在迁移。

2. `get()` 方法在扩容期间的逻辑

get() 方法的实现确保了在扩容期间，能够从新数组和旧数组上读取到正确的值。

2.1 `get()` 的读取过程

计算哈希值和初始桶位置：
- 通过键的 hashCode() 计算哈希值，并根据旧数组的长度，定位到该键在旧数组中的位置。
检查槽位的类型：
- 如果槽位为空，直接返回 null，表示没有找到对应的键。
- 如果槽位是 ForwardingNode，说明该槽位已被迁移到新数组上，此时需要重新定位到新数组中的位置进行查找。
在旧数组和新数组中查找：
- 旧数组中查找：如果槽位不是 ForwardingNode，则在旧数组中正常进行链表/红黑树的查找。
- 新数组中查找：如果槽位是 ForwardingNode，则意味着数据已经迁移到新数组，此时需要在新数组中重新计算位置，并在新数组上进行查找。

2.2 为什么读取不受扩容影响？

逐步迁移：在扩容过程中，ConcurrentHashMap 采用了分布式的逐步迁移机制，即多个线程可以同时进行部分槽位的迁移，而不需要在整个迁移完成前阻塞读取操作。
双数组结构：在扩容期间，ConcurrentHashMap 同时维护了旧数组和新数组，确保了在迁移过程中可以从两个数组中读取到数据。
- 如果当前槽位的数据已经迁移到新数组，那么 get() 方法会通过 ForwardingNode 指引到新数组进行查找。
- 如果数据尚未迁移，get() 方法可以从旧数组中直接读取到正确的值。

3. `ForwardingNode` 的作用

ForwardingNode 是一个特殊的节点类型，用于标识槽位是否已经迁移。它在扩容过程中起到了重要作用：

重定向读取操作：当 get() 方法遇到 ForwardingNode 时，会知道当前槽位的数据已经迁移至新数组，因此会切换到新数组进行查找。
避免数据丢失：通过 ForwardingNode 的指引，读取操作能够保证在扩容期间仍能读取到最接近的一致性数据。

4. 扩容中的一致性保障

ConcurrentHashMap 的设计使得扩容时的数据一致性可以得到较好的保障。通过使用分布式扩容和ForwardingNode，读取操作不会因为扩容而被阻塞。
由于新旧数组是并行存在的，get() 操作能够在扩容时遍历新旧数组，确保读取到最新的数据。

5. 代码示例：`get()` 方法的逻辑

以下是 ConcurrentHashMap 中的简化版 get() 方法的逻辑（简化为理解原理，实际实现更为复杂）：

javaCopy codepublic V get(Object key) {
    Node<K, V>[] tab; // 哈希表
    Node<K, V> e, p; // 节点指针
    int n, i; // 数组长度和索引
    int h = spread(key.hashCode()); // 计算哈希值
    tab = table; // 获取当前哈希表

    // 确定哈希槽位位置
    if (tab != null && (n = tab.length) > 0 && (e = tabAt(tab, (i = (n - 1) & h))) != null) {
        // 槽位中的节点为 ForwardingNode，切换到新数组
        if (e instanceof ForwardingNode) {
            tab = ((ForwardingNode<K, V>) e).nextTable;
            e = tabAt(tab, (i = (tab.length - 1) & h));
        }

        // 查找链表或红黑树中的节点
        while (e != null) {
            if (e.hash == h && (key.equals(e.key))) {
                return e.val; // 找到对应的值
            }
            e = e.next;
        }
    }

    return null; // 未找到对应的值
}

6. 总结

扩容期间的读取行为：ConcurrentHashMap 的 get() 方法在扩容期间会遍历新旧数组，确保能够读取到正确的值。即使在扩容过程中，读取也不会被阻塞。
逐步迁移和双数组结构：ConcurrentHashMap 的扩容是逐步进行的，通过双数组结构和 ForwardingNode 实现数据的一致性保障。
读取优先，写入让步：在高并发和扩容期间，ConcurrentHashMap 的设计优先考虑读取操作的性能和一致性，确保不因扩容而导致读取操作被阻塞。

这种设计使得 ConcurrentHashMap 能在高并发和扩容过程中保持良好的性能和一致性，是其在多线程环境下表现优异的关键之一。

为什么 `computeIfAbsent()` 是原子的？

ConcurrentHashMap 中的 computeIfAbsent() 方法之所以是原子的，是因为它通过内部的同步机制或CAS（Compare-And-Swap）操作，确保对特定键的计算和插入是不可分割的操作。

1. `computeIfAbsent()` 的基本概念

computeIfAbsent() 是 ConcurrentHashMap 中的一种方法，用于在键不存在时，进行计算并插入键值对。其常用形式是：

javaCopy codemap.computeIfAbsent(key, k -> computeValue(k));

如果键 key 已存在，则返回对应的值。
如果键 key 不存在，则会调用传入的计算函数来生成对应的值，并将该值插入到 ConcurrentHashMap 中。

2. `computeIfAbsent()` 方法的原子性

computeIfAbsent() 的原子性体现在以下几个方面：

2.1 原子性保障

单个线程的计算和插入是同步的：
- 在调用 computeIfAbsent() 时，方法内部使用了 synchronized 锁定对应的桶（bucket），以确保计算和插入操作是不可分割的。
- 这意味着在计算过程中，其他线程无法访问或修改该键对应的桶，从而保证了操作的原子性。

2.2 使用 CAS 进行无锁插入

当 ConcurrentHashMap 确定某个桶的头节点为空时，会尝试使用 CAS 进行无锁插入。CAS 是一种乐观锁操作，它会在插入失败时重试，从而保证了在多线程竞争下的线程安全性。
如果 CAS 失败，则表示其他线程已插入了值，当前线程的插入将会被中止，这样可以防止重复计算。

2.3 避免竞争条件

computeIfAbsent() 保证了整个计算和插入操作是原子的，避免了传统的 “先检查，再插入” 的竞争问题。
传统的 “先检查，再插入” 通常会引发竞争条件，如：javaCopy codeif (map.get(key) == null) { map.put(key, value); } 在高并发场景下，多个线程可能同时通过 map.get(key) == null 条件，从而导致重复插入或其他不一致的结果。

2.4 内部实现逻辑

computeIfAbsent() 方法内部使用了分段锁（在 JDK 1.7 之前）和 CAS + Synchronized（在 JDK 1.8 之后）来实现高并发和线程安全。
当一个线程正在计算某个键对应的值时，其他线程会被阻塞在该键对应的桶上，直到计算完成，避免了并发计算导致的多次插入问题。

3. 使用场景和优点

避免重复计算：computeIfAbsent() 可以确保值的计算和插入在并发环境中是安全的，避免多个线程对同一键重复计算值的问题。
简化代码逻辑：相比于传统的 “先检查，再插入” 方式，computeIfAbsent() 更加简洁，减少了加锁的复杂性。
提高性能：通过 CAS 和局部同步，computeIfAbsent() 提供了较高的并发性能，同时又保证了数据的一致性。

4. 示例代码

javaCopy codeimport java.util.concurrent.ConcurrentHashMap;

public class ComputeIfAbsentExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        map.computeIfAbsent("key", k -> {
            System.out.println("Computing value...");
            return 42; // 假设的计算结果
        });
        System.out.println(map.get("key")); // 输出: 42
    }
}

在上述代码中，当多个线程同时调用 computeIfAbsent() 时，只有一个线程会执行计算并插入新值，其他线程会获取已插入的值。

总结

computeIfAbsent() 的原子性是由 ConcurrentHashMap 内部的CAS 操作和同步锁机制保障的。
它可以确保在并发环境中对指定键的计算和插入是不可分割的，避免了多线程环境下的竞争条件和不一致问题。
通过这种机制，computeIfAbsent() 提供了简单、高效且线程安全的方式来插入或获取缺失的键值对。