ConcurrentHashMap

jdk7 的 ConcurrentHashMap

在 JDK1.7 中用的是 Segment 数组+链表实现的。Segment 是一种可重入锁(ReentrantLock)，链表则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment数组，一个 Segment 里包含一个链表。

JDK1.7 的 ConcurrentHashMap 给每一段数据配一把锁，当一个线程访问其中该段数据的时候，会锁住该链表头节点，那么其他段的数据也能被其他线程访问，能够实现真正的并发访问。

Segment 默认个数是 16，一旦初始化就不能改变。每个链表默认长度也是 16。 >

rehash

ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize

jdk8 的 ConcurrentHashMap

JDK1.7 的 ConcurrentHashMap 底层实现是 Segment 数组+链表的形式，在数据量大时要遍历链表，效率低。而 JDK1.8 则使用了 Node 数组+链表/红黑树的形式。

Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。

ConcurrentHashMap 的实现(和 HashMap 结构一样)

参考此文章

具体实现结构如下：

JDK1.8 ConcurrentHashMap JDK1.8 ConcurrentHashMap 主要通过 volatile+CAS 或者
synchronized 来实现的线程安全的。put 元素时先根据 key 的 hashcode 判断对应 Node 容器是否为空：

如果为空则使用 volatile+CAS 来初始化

如果容器不为空，则根据存储的元素计算该位置是否为空。

如果根据存储的元素计算结果为空 ，则利用CAS设置该节点；

如果根据存储的元素计算结果不为空 ，则使用synchronized ，然后，遍历桶中的数据，并替换或新增节点 到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

也就是访问 Node 数组时用 CAS+volatile，访问 HashEntry 时用 CAS 或synchronized。

为什么 ConcurrentHashMap 的 key 和 value 不能为 null

ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性。null 是一个特殊的值，表示没有对象或没有引用 。如果用 null 作为键，就无法通过 containsKey(key)区分这个键是否存在于 ConcurrentHashMap 中，还是根本没有这个键。同样，如果用 null 作为值，就无法区分这个值是否是真正存储在 ConcurrentHashMap 中的，还是因为找不到对应的键而返回的。

与此形成对比的是，HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。如果传入 null 作为参数，就会返回 hash 值为 0 的位置的值 。单线程环境下，不存在一个线程操作该 HashMap 时，其他的线程将该 HashMap 修改的情况，所以可以通过 contains(key)来做判断是否存在这个键值对，也就不存在二义性问题。

ConcurrentHashMap 如何保证复合操作的原子性

复合操作是指由多个基本操作(如put、get、remove、containsKey等)组成的操作，例如先判断某个键是否存在containsKey(key)，然后根据结果进行插入或更新put(key, value)。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。

ConcurrentHashMap 提供了一些原子性的复合操作，如 putIfAbsent、compute、computeIfAbsent 、computeIfPresent、merge等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。