并发List、Map的一些问题

绝地灬酷狼 2022-12-02 00:50 168阅读 0赞

## 1. CopyOnWriteArrayList相关 ##

### 1.1 和ArrayList相比有哪些相同点和不同点？ ###

*  相同点：底层的数据结构相同，都是数组
 *  不同点：后者是线程安全的，在多线程环境下使用，无需加锁，可以直接使用

### 1.2 CopyOnWriteArrayList通过哪些手段实现了线程安全？ ###

1.  数组容器被volatile关键字修饰，保证了数组内存地址被任意线程修改后，都会通知到其他线程，保证了可见性；
2.  对数组的所有修改操作，都进行了加锁，保证了同一时刻只有一个线程对数组进行修改，比如在add时，无法remove；
3.  修改过程中对原数组进行了赋值，在新数组上进行修改，修改过程中，不会对原数组产生任何影响；

### 1.3 在add方法中，对数组进行加锁后，不是已经线程安全了么，为什么还需要对老数组进行拷贝？ ###

加锁后确实能保证同一时刻只有一个线程操作当前数组，但是在多线程环境下，如果不对数组进行拷贝，add操作只是改变了数组内部元素值的改变，就无法改变原数组容器的内存地址，进而无法触发volatile可见性效果，其他线程就无法感知到数组已经被修改了。所以就会存在可见性问题，会有线程安全问题。

### 1.4 对老数组拷贝，会有性能损耗，平时使用需要注意什么？ ###

*  不要在for循环里面使用add、remove方法，这两个方法每次都要进行一次拷贝；
 *  尽量使用addAll和removeAll方法，整个操作只会进行一次数组拷贝

### 1.5 为什么 CopyOnWriteArrayList 迭代过程中，数组结构变动，不会抛出ConcurrentModificationException 了？ ###

因为每次对CopyOnWriteArrayList 进行修改的时候，都会产生新的数组，而在迭代时，持有的仍然是老数组的引用，当每次add或remove后，会用新数组来替换老数组，老数组的结构实际上一直没发生变化，所以就没有异常了。

### 1.6 插入的数据正好在 List 的中间，请问两种 List 分别拷贝数组几次？为什么？ ###

*  ArrayList只需要拷贝一次，假设插入的位置是2，只需把位置2后面的数据往后移动一位即可，所以拷贝一次；
 *  CopyOnWriteArrayList 需要拷贝两次，因为CopyOnWriteArrayList 多了把老数组的数据拷贝到新数组上这一步，先把老数组0到2的数据拷贝到新数组上，预留出新数组2的位置，再把老数组3到最后的数组拷贝到新数组上，这种拷贝方式减少了需要拷贝的数据。

## 2. ConcurrentHashMap 相关 ##

### 2.1 ConcurrentHashMap和 HashMap 的相同点和不同点 ###

*  相同点：都是数组+链表+红黑树的数据结构，所以基本操作的思想相同；都实现了Map接口，继承了AbstractMap抽象类，所以两者的方法大多都是相似的，可以互相切换。
 *  不同点：ConcurrentHashMap是线程安全的，在多线程环境下不需要加锁；在数据结构上，ConcurrentHashMap多了转移节点，用于保证扩容时的线程安全；

### 2.2 ConcurrentHashMap 通过哪些手段保证了线程安全？ ###

*  储存Map数据的数组被volatile关键字修饰，一旦被修改，立刻就能通知其他线程，因为是数组，所以需要改变内存地址，才能触发volatile的可见性；
 *  put时，如果计算出来的数组下标没有值的话，采用自旋（无限for循环）+CAS来保证一定可以新增成功，又不会覆盖其他线程put进去的值；
 *  如果put的节点正好扩容，会等扩容完成之后，再进行put，保证了在扩容时，老数组的值不会发生变化；
 *  对数组的节点进行操作时，会先锁住节点，保证只有当前线程才能对节点上的链表或红黑树进行操作；
 *  红黑树旋转时，会锁住根节点，保证旋转时的线程安全；

### 2.3 描述一下 CAS 算法在 ConcurrentHashMap 中的应用？ ###

CAS是一种乐观锁，意思是比较并交换，在执行的时候会先判断内存中的值是否和原值相等，相等的话把新值不值给对象，否则赋值失败，整个过程都是原子性操作，没有线程安全问题。  
ConcurrentHashMap 的put方法中，有使用到CAS，是结合自旋（无限for循环）一起使用的，步骤如下：

*  计算出数组索引，拿出索引对应的原值；
 *  CAS覆盖当前索引对应的值，赋值时，如果发现内存值和原值相等，执行赋值，退出循环，否则不赋值，进入下一次for循环；  
    通过自旋和CAS可以保证不会盲目的覆盖原值，而且一定是可以赋值成功，因为CAS是调用系统底层API，是原子性操作。

### 2.4 ConcurrentHashMap 是如何发现当前槽点正在扩容的？ ###

ConcurrentHashMap新增一个节点类型，叫做转移节点，当我们发现当前节点是转移节点时（转移节点的hash值是-1），表示Map正在扩容。

### 2.5 发现槽点正在扩容时，put 操作会怎么办？ ###

无限for循环或走到扩容方法中，帮助扩容，等待扩容完成之后再执行put操作

### 2.6 两种 Map 扩容时，有啥区别？ ###

HashMap是在老数据上面进行扩容，多线程环境下，会有线程安全问题，而ConcurrentHashMap的扩容过程是这样的：

1.  从数组的队尾开始拷贝
2.  拷贝数组的槽点时，先把原数组槽点锁住，拷贝成功到新数组时，把原数组槽点赋值为转移节点
3.  从数组的尾部拷贝到头部，每拷贝成功一次，就把原数组的槽点设置成转移节点
4.  直到所有数组数据都拷贝到新数组时，直接把新数组整个赋值给数组容器，拷贝完成

简单来说，通过扩容时给槽点加锁，和发现槽点正在扩容就等待的策略，保证了ConcurrentHashMap可以慢慢一个一个槽点的转移，保证了扩容时的线程安全。