Java 并发编程面试题——并发 List 与并发 Set

柔光的暖阳◎ 2023-10-14 20:23 77阅读 0赞

#### 目录 ####

*  并发 List
 *   *  多线程操作 ArrayList 可能会出现什么问题？如何解决？
     *  多线程操作 LinkedList 可能会出现什么问题？如何解决？
     *  CopyOnWriteArrayList 的底层实现原理是什么？
     *  Collections.synchronizedList() 方法有什么作用？
 *  并发 Set
 *   *  多线程操作 HashSet 可能会出现什么问题？如何解决？
     *  Collections.synchronizedSet() 方法有什么作用？
     *  CopyOnWriteArraySet 的底层实现原理是什么？

## 并发 List ##

### 多线程操作 ArrayList 可能会出现什么问题？如何解决？ ###

（1）在多线程环境下，对 ArrayList 进行操作可能会出现以下问题：

*  **线程安全性问题**：ArrayList 不是线程安全的数据结构，它在进行操作时并没有提供内部的同步机制。多个线程同时对 ArrayList 进行写操作（如添加或删除元素）可能导致数据不一致的问题，例如：
    
     *  **数组越界**：当多个线程同时对 ArrayList 进行添加或删除元素的操作时，由于操作的执行顺序不确定，可能会导致数组越界的情况。例如，一个线程正在删除元素，而另一个线程可能在同一时间正在访问或修改同一个位置的元素，从而导致数组下标越界。
     *  **数值覆盖**：当多个线程同时对 ArrayList 进行修改操作时，由于操作的执行顺序不确定，可能导致数据覆盖的问题。例如，一个线程在修改某个元素的值时，另一个线程可能在修改操作之前读取了这个元素，从而导致数据的不一致性。
 *  **迭代器异常**：当一个线程正在使用迭代器遍历 ArrayList 的元素时，另一个线程对 ArrayList 进行结构性的修改（如添加、删除元素）可能导致迭代器抛出 `ConcurrentModificationException` 异常，因为迭代器在遍历过程中会检查 ArrayList 的 modCount 是否发生变化，如果发生变化，则认为集合的结构已被修改，从而抛出异常。

（2）为了解决这些问题，可以采取以下措施：

*  **使用线程安全的容器**：可以使用线程安全的容器类，例如 `Vector`、`Collections.synchronizedList()`、`CopyOnWriteArrayList` 来替代 ArrayList，这些容器提供了内部的同步机制，保证了在多线程环境下的线程安全性。
 *  **显式同步控制**：在多线程访问 ArrayList 时，使用同步控制手段（如 synchronized 关键字或 Lock）来保护对 ArrayList 的访问，确保同一时间只有一个线程可以进行修改操作。

public class ThreadList {
        
        public static void main(String[] args) {
        
            //创建 ArrayList 集合
            //List<String> list = new ArrayList<>();
            
            //解决方案
            //1.Vector
            //List<String> list = new Vector<>();
        
            //2.Collections
            //List<String> list = Collections.synchronizedList(new ArrayList<>());
            
            //3.CopyOnWriteArrayList，推荐使用
            List<String> list = new CopyOnWriteArrayList<>();
        
            for (int i = 0; i < 10; i++) {
        
                new Thread(()->{
        
                    //向集合中添加内容
                    list.add(UUID.randomUUID().toString().substring(0,8));
                    //从集合中获取内容
                    System.out.println(list);
                },String.valueOf(i)).start();
            }
        }
    }

### 多线程操作 LinkedList 可能会出现什么问题？如何解决？ ###

（1）在多线程环境下，对 LinkedList 进行操作可能会出现以下问题：

*  **线程安全性问题**：LinkedList 不是线程安全的数据结构，它在进行操作时没有提供内部的同步机制。多个线程同时对 LinkedList 进行写操作（如添加或删除元素）可能导致数据不一致的问题，例如：
    
     *  **数值覆盖**：当多个线程同时对 LinkedList 进行修改操作（如添加、删除元素）时，由于操作的执行顺序不确定，可能会导致数据覆盖的问题。例如，一个线程在添加元素时，另一个线程可能会在这个元素还未完全添加到链表之前进行删除操作，从而导致数据的不一致性。
     *  **出现环**：当多个线程同时对 LinkedList 进行修改操作时，由于操作的执行顺序不确定，可能会导致链表出现环的问题。例如，一个线程在删除元素时，另一个线程可能在删除操作之前又添加了这个元素，从而形成了一个环形链表。
 *  **迭代器异常**：当一个线程正在使用迭代器遍历 LinkedList 的元素时，若其他线程对 LinkedList 进行结构性的修改（如添加、删除元素）可能导致迭代器抛出 ConcurrentModificationException 异常，原因同样是迭代器在遍历过程中会检查 modCount 是否发生变化，一旦发生变化就会抛出异常。

（2）为了解决这些问题，可以采取以下措施：

*  **使用线程安全的容器**：可以使用线程安全的容器类，例如 `ConcurrentLinkedQueue` 来替代 LinkedList，这些容器提供了内部的同步机制，保证了在多线程环境下的线程安全性。
 *  **显式同步控制**：在多线程访问 LinkedList 时，使用同步控制手段（如 synchronized 关键字或 Lock）来保护对 LinkedList 的访问，确保同一时间只有一个线程可以进行修改操作。

### CopyOnWriteArrayList 的底层实现原理是什么？ ###

（1）`CopyOnWriteArrayList` 是 Java 并发包提供的一个线程安全的容器类，它的底层实现原理是**写时复制 (Copy-on-Write)**。其底层原理可以简要概括为以下几个步骤：

*  **初始状态**：CopyOnWriteArrayList 内部使用一个 volatile 修饰的数组来存储元素。
 *  **写操作**：当有线程想要进行修改操作（如添加、删除元素）时，首先会进行一次数组的复制（复制出一个新的数组，其长度为原数组的长度 + 1），然后在新数组上进行修改操作。
 *  **修改完成**：当修改完成后，将新数组设置为内部数组的引用，并更新 volatile 的引用，使得其他线程可以访问到最新的修改后的数组。这样可以确保在修改操作过程中，其他线程仍然可以读取到原来的数组，而不会受到修改的影响。

例如，CopyOnWriteArrayList 的 `add` 方法的源码如下：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        
    	
    	//...
    
    	public boolean add(E e) {
        
    		//通过使用 ReentrantLock 来保证线程安全。
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
        
                Object[] elements = getArray();
                int len = elements.length;
                //复制一个新的数组，其长度为原数组的长度 + 1
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                //在新数组的末尾进行插入操作
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally {
        
                lock.unlock();
            }
        }
    }

（2）由于 CopyOnWriteArrayList 的写操作会涉及创建新的数组并复制数据，因此它**适用于读多写少的场景**。读操作不需要加锁，并且可以提供较好的读性能，而写操作的性能可能相对较低，特别是**当集合容量较大时，因为写操作需要复制整个数组，会占用较多的内存**，并且不能保证实时一致性。

（3）总结来说，CopyOnWriteArrayList 的底层原理是在写操作时进行数组的复制，从而确保读操作不受写操作的影响，从而提供线程安全的读写访问。

### Collections.synchronizedList() 方法有什么作用？ ###

（1）`Collections.synchronizedList` 是 Java 中提供的一个工具方法，用于**创建线程安全的 List 集合**。它实际上是一个包装器 (Wrapper) 方法，接受一个 List 对象作为参数，并返回一个线程安全的 List 对象。使用 `Collections.synchronizedList` 方法可以将普通的 List 对象包装成一个线程安全的 List 对象，该线程安全的 List 对象可以被多个线程同时访问而不会导致数据不一致的问题。

（2）下面是使用 `Collections.synchronizedList` 的示例代码：

// 创建一个普通的 List 对象
    List<String> list = new ArrayList<>(); 
    
    // 使用 Collections.synchronizedList 方法创建一个线程安全的 List 对象
    List<String> synchronizedList = Collections.synchronizedList(list); 
    
    // 线程安全的 List 对象可以被多个线程同时访问

（3）需要注意的是，通过 `Collections.synchronizedList` 方法创建的线程安全的 List 对象，在并发场景下可以保证读写操作的线程安全性。但是，如果需要保证复合操作的原子性，仍然需要使用额外的同步机制，比如使用 `synchronized` 关键字或者 `Lock`。此外，虽然 `Collections.synchronizedList` 方法可以确保对于该集合的任意单个调用都是线程安全的，但在多线程环境下进行批量的操作时，仍然需要手动进行外部同步以保证一致性。

## 并发 Set ##

### 多线程操作 HashSet 可能会出现什么问题？如何解决？ ###

（1）在多线程环境下，对 HashSet 进行操作可能会出现以下问题：

*  线程安全问题：HashSet 是非线程安全的，当多个线程同时对 HashSet 进行修改操作（如添加、删除元素）时，可能会导致数据的不一致性和结构的破坏。例如，一个线程在添加元素时，另一个线程可能在同一时间进行删除操作，从而导致**数据丢失**。
 *  `ConcurrentModificationException 异常`：如果一个线程正在遍历 HashSet 并同时有其他线程修改了 HashSet 的结构，就可能会导致 ConcurrentModificationException 异常抛出。

（2）为了解决这些问题，可以采取以下措施：

*  **使用线程安全的集合类**：可以使用线程安全的集合类，如 `synchronizedSet` 或 `CopyOnWriteArraySet`，来替代 HashSet。这些集合类在内部提供了线程安全的操作机制，避免了数据不一致性和结构破坏的问题。
 *  **显式同步控制**：在多线程访问 HashSet 时，可以使用同步控制手段（如 `synchronized` 关键字或 `Lock`）来保护对 HashSet 的访问。通过加锁，确保同一时间只有一个线程能够修改 HashSet，防止多个线程之间的竞争和操作干扰。

### Collections.synchronizedSet() 方法有什么作用？ ###

（1）`Collections.synchronizedSet()` 方法的作用**是将普通的 Set 转换为线程安全的 Set**。当多个线程同时访问一个普通的 Set 对象时，可能会发生并发访问的问题，导致数据不一致或产生异常。`Collections.synchronizedSet()` 方法通过对普通的 Set 进行包装，返回一个线程安全的 Set 对象，从而解决了并发访问的问题。

（2）具体来说，该方法会返回一个线程安全的代理 Set（实现了 `Set` 接口），它对所有对 Set 的修改操作（如添加、删除元素）都进行了同步控制。这就意味着在多线程环境中，每个修改操作都会在进入和退出时使用同步锁来保证线程安全。

（3）使用 `Collections.synchronizedSet()` 方法可以提供一定程度上的线程安全性，但需要注意的是，该方法只通过对修改操作进行同步控制来实现线程安全，并不能保证对 Set 进行迭代/遍历时的线程安全。需要特别注意的是，如果已经使用了其他并发集合类，如 `ConcurrentHashSet` 或 `CopyOnWriteArraySet`，就不需要再使用 `Collections.synchronizedSet()` 方法进行包装，因为这些并发集合类已经具备了线程安全性。

### CopyOnWriteArraySet 的底层实现原理是什么？ ###

（1）`CopyOnWriteArraySet` 的底层实现原理与 `CopyOnWriteArrayList` 类似，即写时复制 (Copy-on-Write)，只不过前者实现了去重功能。

（2）例如，CopyOnWriteArraySet 的 `add` 方法的源码如下，仔细观察可以发现，`add` 实际上是调用了 `CopyOnWriteArrayList.addIfAbsent(E e)` 方法。即 CopyOnWriteArrayList 类为 CopyOnWriteArraySet 提供了大部分功能实现。

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
            implements java.io.Serializable {
        
    	//...
    	
    	private final CopyOnWriteArrayList<E> al;	
    
    	public boolean add(E e) {
        
            return al.addIfAbsent(e);
        }
    }
    
    public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        
    	
    	//...
    
    	public boolean addIfAbsent(E e) {
        
            Object[] snapshot = getArray();
            return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
                addIfAbsent(e, snapshot);
        }
    	
    	private boolean addIfAbsent(E e, Object[] snapshot) {
        
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
        
                Object[] current = getArray();
                int len = current.length;
                if (snapshot != current) {
        
                    // Optimize for lost race to another addXXX operation
                    int common = Math.min(snapshot.length, len);
                    for (int i = 0; i < common; i++)
                        if (current[i] != snapshot[i] && eq(e, current[i]))
                            return false;
                    if (indexOf(e, current, common, len) >= 0)
                            return false;
                }
                Object[] newElements = Arrays.copyOf(current, len + 1);
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally {
        
                lock.unlock();
            }
        }
    }