ConcurrentHashMap

ConcurrentHashMap是如何保证线程安全的？

在JDK 1.7中，ConcurrentHashMap使用了分段锁技术，即将哈希表分成多个段，每个段拥有一个独立的锁。这样可以在多个线程同时访问哈希表时，只需要锁住需要操作的那个段，而不是整个哈希表，从而提高了并发性能。

虽然JDK 1.7的这种方式可以减少锁竞争，但是在高并发场景下，仍然会出现锁竞争，从而导致性能下降。

在JDK 1.8中，ConcurrentHashMap的实现方式进行了改进，使用分段锁和“CAS+Synchronized”的机制来保证线程安全。 在JDK 1.8中，ConcurrentHashMap会在添加或删除元素时，首先使用CAS操作来尝试修改元素，如果CAS操作失败，则使用Synchronized锁住当前槽，再次尝试put或者delete。这样可以避免分段锁机制下的锁粒度太大，以及在高并发场景下，由于线程数量过多导致的锁竞争问题，提高了并发性能。

ConcurrentHashMap在哪些地方做了并发控制

初始化桶阶段

如果在此阶段不做并发控制，那么极有可能出现多个线程都去初始化桶的问题，导致内存浪费。所以Map在此处采用自旋操作和CAS操作，如果此时没有线程初始化，则去初始化，否则当前线程让出CPU时间片，等待下一次唤醒。

put元素阶段

如果hash后发现桶中没有值，则会直接采用CAS插入并且返回；
如果发现桶中有值，则对流程按照当前的桶节点为维度进行加锁，将值插入链表或者红黑树中。

扩容阶段

多线程最大的好处就是可以充分利用CPU的核数，带来更高的性能，所以ConcurrentHashMap并没有一味的通过CAS或者锁去限制多线程，在扩容阶段，ConcurrentHashMap就通过多线程来加加速扩容。
在分析之前，我们需要知道两件事情：

• ConcurrentHashMap通过ForwardingNode来记录当前已经桶是否被迁移，如果oldTable[i] instanceOf ForwardingNode则说明处于i节点的桶已经被移动到newTable中了。它里面有一个变量nextTable，指向的是下一次扩容后的table。
• transferIndex记录了当前扩容的桶索引，最开始为oldTable.length，它给下一个线程指定了要扩容的节点。

得知到这两点后，我们可以梳理出如下扩容流程：

1. 通过CPU核数为每个线程计算划分任务，每个线程最少的任务是迁移16个桶
2. 将当前桶扩容的索引transferIndex赋值给当前线程，如果索引小于0，则说明扩容完毕，结束流程，否则
3. 再将当前线程扩容后的索引赋值给transferIndex，譬如，如果transferIndex原来是32，那么赋值之后transferIndex应该变为16，这样下一个线程就可以从16开始扩容了。这里有一个小问题，如果两个线程同时拿到同一段范围之后，该怎么处理？答案是ConcurrentHashMap会通过CAS对transferIndex进行设置，只可能有一个成功，所以就不会存在上面的问题。
4. 之后就可以对真正的扩容流程进行加锁操作了。

ChatGPT：

在ConcurrentHashMap的扩容过程中，多个线程可以同时进行元素的迁移操作，而不是只有一个线程能够成功进行迁移操作。

具体来说，ConcurrentHashMap在进行扩容时，会将原来的Segment数组分成多个部分，并由多个线程同时进行元素的迁移操作。每个线程负责迁移一部分的元素到新的Segment数组中。这样，多个线程可以并发地进行元素的迁移，提高了扩容的速度。

同时，ConcurrentHashMap会使用CAS（Compare and Swap）操作来确保元素的迁移的原子性和一致性。CAS操作可以避免多个线程并发修改同一个元素的问题。如果多个线程同时修改同一个元素，只有一个线程的CAS操作会成功，其他线程需要重试或者等待。

因此，多个线程可以并发地进行元素的迁移操作，提高了扩容的速度和并发能力。而CAS操作则用于保证元素迁移的原子性和一致性。

SynchronizedList和Vector的区别

Vector是java.util包中的一个类。 SynchronizedList是java.util.Collections中的一个静态内部类。

在多线程的场景中可以直接使用Vector类，也可以使用Collections.synchronizedList(List list)方法来返回一个线程安全的List。

1. 如果使用add方法，那么他们的扩容机制不一样。
2. SynchronizedList可以指定锁定的对象。即锁粒度是同步代码块。而Vector的锁粒度是同步方法
3. SynchronizedList有很好的扩展和兼容功能。他可以将所有的List的子类转成线程安全的类。
4. 使用SynchronizedList的时候，进行遍历时要手动进行同步处理。
5. SynchronizedList可以指定锁定的对象。

ConcurrentHashMap是如何保证fail-safe的？

在 JDK 1.8 中，ConcurrentHashMap作为一个并发容器，他是解决了fail-fast的问题的，也就是说，他是一个fail-safe的容器。 通过以下两种机制来实现 fail-safe 特性：

首先，在 ConcurrentHashMap 中，遍历操作返回的是弱一致性迭代器，这种迭代器的特点是，可以获取到在迭代器创建后被添加到 ConcurrentHashMap 中的元素，但不保证一定能获取到在迭代器创建后被删除的元素。

也就是说，在迭代器遍历时，如果发现当前元素的 hash 值为 MOVED，即该元素所在的哈希桶正在进行扩容操作，那么就会帮助扩容操作，然后重新遍历当前哈希桶。

另外。在 JDK 1.8 中，ConcurrentHashMap 中的 Segment 被移除了，取而代之的是使用类似于cas+synchronized的机制来实现并发访问。在遍历 ConcurrentHashMap 时，只需要获取每个桶的头结点即可，因为每个桶的头结点是原子更新的，不会被其他线程修改，因此不需要加锁。

也就是说，ConcurrentHashMap 通过弱一致性迭代器和 Segment 分离机制来实现 fail-safe 特性，可以保证在遍历时不会受到其他线程修改的影响。

弱一致性保障

ConcurrentHashMap 提供的是弱一致性保障，这是因为在多线程并发修改 ConcurrentHashMap 时，可能会出现一些短暂的不一致状态，即一个线程进行了修改操作，但是另一个线程还没有看到这个修改。因此，在并发修改 ConcurrentHashMap 时，不能保证在所有时刻 ConcurrentHashMap 的状态都是一致的。

首先就是因为前面提到的弱一致性迭代器，在 ConcurrentHashMap 中，使用迭代器遍历时，不能保证在迭代器创建后所有的元素都被迭代器遍历到。这是因为在迭代器遍历过程中，其他线程可能会对 ConcurrentHashMap 进行修改，导致迭代器遍历的元素发生变化。为了解决这个问题，ConcurrentHashMap 提供了一种弱一致性迭代器，可以获取在迭代器创建后被添加到 ConcurrentHashMap 中的元素，但是可能会获取到迭代器创建后被删除的元素。

为什么ConcurrentHashMap不允许null值？

ConcurrentHashMap在使用时，和HashMap有一个比较大的区别，那就是HashMap中，null可以作为键或者值都可以。而在ConcurrentHashMap中，key和value都不允许为null。

ConcurrentMap（如ConcurrentHashMap、ConcurrentSkipListMap）不允许使用null值的主要原因是，在非并发的Map中（如HashMap)，是可以容忍模糊性（二义性）的，而在并发Map中是无法容忍的。

假如说，所有的Map都支持null的话，那么map.get(key)就可以返回null，但是，这时候就会存在一个不确定性，当你拿到null的时候，你是不知道他是因为本来就存了一个null进去还是说就是因为没找到而返回了null。

在HashMap中，因为它的设计就是给单线程用的，所以当我们map.get(key)返回null的时候，我们是可以通过map.contains(key)检查来进行检测的，如果它返回true，则认为是存了一个null，否则就是因为没找到而返回了null。

但是，像ConcurrentHashMap，它是为并发而生的，它是要用在并发场景中的，当我们map.get(key)返回null的时候，是没办法通过map.contains(key)检查来准确的检测，因为在检测过程中可能会被其他线程锁修改，而导致检测结果并不可靠。

所以，为了让ConcurrentHashMap的语义更加准确，不存在二义性的问题，他就不支持null。