【面试】高并发中的集合

本文旨在总结多线程情况下集合的使用

Java中的集合大致以下三个时期：

第一代线程安全集合类

以Vector、HashTable为代表的初代集合，使用synchronized在修饰方法，从而保证线程安全。

缺点：效率低。

/**
 * Appends the specified element to the end of this Vector.
 *
 * @param e element to be appended to this Vector
 * @return {@code true} (as specified by {@link Collection#add})
 * @since 1.2
 */
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

/**
 * Returns the element at the specified position in this Vector.
 *
 * @param index index of the element to return
 * @return object at the specified index
 * @throws ArrayIndexOutOfBoundsException if the index is out of range
 *            ({@code index < 0 || index >= size()})
 * @since 1.2
 */
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

第二代非线程安全集合类

第二类就是以ArrayList、HashMap为代表的集合，非线程安全，但是性能好，用来代替Vector和HashTable。
因为大部分情况下集合都是在单线程中使用。

在需要线程安全时，通过Collections.synchronizedList(list)、Collections.synchronizedMap(map)进行同步处理，这两个方法会返回一个线程安全的内部集合类（定义在Collections中）。

底层使用的也是synchronized同步一个内部锁对象，相对直接锁方法有微弱性能提升。

第三代线程安全集合类

java.util.concurrent包下面添加了大量多线程类。集合相关的类以ConcurrentHashMap、CopyOnWriteArrayList(Set)类为代表。

其中，ConcurrentHashMap使用了分段锁、读写分离等方式提高了并发性。

分段锁机制（Segmentation）：ConcurrentHashMap 内部使用了分段锁的机制。它将整个哈希表分成了多个段（Segment），每个段相当于一个小的哈希表，每个段都独立地加锁。这样不同的线程在访问不同的段时可以并发进行，从而提高了并发访问的效率。当需要修改哈希表时，只有涉及到相应段的锁才会被加锁，而不是锁住整个表。

读写分离：ConcurrentHashMap 允许多个线程同时进行读操作，读操作不会阻塞，这样就提高了读操作的并发性。只有在写操作的时候才会进行加锁，以确保写操作的线程安全性。

CopyOnWriteArrayList一般用于读多写少的场景下：

它的原理是在对容器进行修改（如添加、删除元素）时，并不直接在原有数据结构上进行操作，而是先将原有的数据复制一份，在新的副本上进行修改，完成后再将修改后的副本赋值回原数据结构。因此称之为“写时复制”。