常见并发容器总结

Java中并发集合类有很多，其结构关系如下图所示：

本文主要介绍两个最常用的并发集合类：ConcurrentHashMap和CopyOnWriteArrayList。

ConcurrentHashMap

ConcurrentHashMap是Java中线程安全的hashmap。自从被提出后，另外一个线程安全的哈希类Hashtable就被弃用了，因为其效率过低。为什么HashTable慢？

因为其实现使用了synchronized关键字对put等操作进行加锁，而synchronized关键字加锁是对整个对象进行加锁，也就是说在进行put等修改Hash表的操作时，锁住了整个Hash表，从而使得其表现的效率低下。

在JDK1.5~1.7和JDK1.8中，ConcurrentHashMap有着不同的实现，下面分别进行介绍。

ConcurrentHashMap-JDK1.7

在JDK1.5~1.7版本，Java使用了分段锁机制实现ConcurrentHashMap.

简而言之，ConcurrentHashMap在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段；而每个Segment元素，即每个分段则类似于一个Hashtable；这样，在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后对该Segment加锁即可。因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作。接下来分析JDK1.7版本中ConcurrentHashMap的实现原理。

一、数据结构

ConcurrentHashMap的数据结构如下图所示：

ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。

再具体到每个 Segment 内部，其实每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全，所以处理起来要麻烦些。

二、初始化

和HashMap类似，主要有两个重要参数：

• initialCapacity： 初始容量，这个值指的是整个 ConcurrentHashMap 的初始容量，实际操作的时候需要平均分给每个 Segment。
• loadFactor： 负载因子，之前我们说了，Segment 数组不可以扩容，所以这个负载因子是给每个 Segment 内部使用的。

初始化完成，我们得到了一个 Segment 数组。我们就当是用 new ConcurrentHashMap() 无参构造函数进行初始化的，那么初始化完成后:

• Segment 数组长度为 16，不可以扩容
• Segment[i] 的默认大小为 2，负载因子是 0.75，得出初始阈值为 1.5，也就是以后插入第一个元素不会触发扩容，插入第二个会进行第一次扩容
• 这里初始化了 segment[0]，其他位置还是 null，至于为什么要初始化 segment[0]，后面的代码会介绍
• 当前 segmentShift 的值为 32 - 4 = 28，segmentMask 为 16 - 1 = 15，姑且把它们简单翻译为移位数和掩码，这两个值马上就会用到

关于put、remove等操作的源码分析可以参考Java全站知识体系。

ConcurrentHashMap-JDK1.8

在JDK1.7之前，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制。因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS和synchronized实现。

其数据结构和HashMap基本一样，不过为了保证线程安全，其源码要更复杂一点，感兴趣的可以自行研究。

CopyOnWriteArrayList

CopyOnWriteArrayList利用CopyOnWrite思想，即在写时复制一份副本进行修改，修改完成后，再将新值赋值给旧值，为保证线程安全，需要在所有的写操作加悲观锁或者乐观锁，而读操作不必加锁，这就使得读写分离，读读不互斥，读写不互斥，空间换时间，性能大大提升。

CopyOnWriteArrayList属性中有一个可重入锁，用来保证线程安全访问，还有一个Object类型的数组，用来存放具体的元素。当然，也使用到了反射机制和CAS来保证原子性的修改lock域。

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 版本序列号
    private static final long serialVersionUID = 8673264195747942595L;
    // 可重入锁
    final transient ReentrantLock lock = new ReentrantLock();
    // 对象数组，用于存放元素
    private transient volatile Object[] array;
    // 反射机制
    private static final sun.misc.Unsafe UNSAFE;
    // lock域的内存偏移量
    private static final long lockOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> k = CopyOnWriteArrayList.class;
            lockOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("lock"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

CopyOnWrite利用写时复制副本加锁修改，而读不加锁的思想达到读写分离的效果，以空间换时间，提升性能。而其弊端也正是其思想的体现：

• 内存占用问题：CopyOnWrite因为复制副本所以双倍占用内存，可能造成频繁的 Yong GC 和 Full GC。（利用CopyOnWrite机制更新大对象需要注意）
• 数据一致性问题：CopyOnWrite只保证了数据最终一致性，数据的实时一致性不能保证，所以读数据可能会有一定的延迟。

缺陷决定了CopyOnWriteArrayList使用场景的局限性，CopyOnWriteArrayList适合读多写少，复制数据对象不宜过大的场景。

总的来说，CopyOnWriteArrayList具有以下特征：

1. 是ArrayList的线程安全版本；

2. 有写操作的时候会copy一份数据，然后写完再设置成新的数据；

3. 适用于读多写少的并发场景， 每次add/set都要重新复制数组，这个代价实在太高昂了。

4. 不适用于实时读的场景，拷贝数据、新增元素比较耗时，读取到的数据还可能是旧的（读的时候不加锁）。

   在线程x执行get操作的时候并不是直接通过全局array访问数组元素而是通过方法的形参a访问的，a指向的地址和array指向的地址在调用get方法的那一刻是一样的，都指向了堆内存的数组对象。之后改变array指向的地址并不影响get的访问，因为在调用get方法的那一刻形参a指向的内存地址就已经确定了，不会改变。所以读的仍然是旧数组。

还需要注意的一点是：CopyOnWriteArrayList中的COWIterator迭代器没有fail-fast检查。

例如ArrayList在迭代器遍历想删除元素，只能使用迭代器的删除方法，而使用外部ArrayList删除方法会抛ConcurrentModificationException异常，为什么呢？

因为ArrayList成员变量维护了一个modCount，每次修改操作都会modCount++，而迭代器中也维护了一个expectedModCount，新建迭代器时modCount赋值给expectedModCount，在迭代器遍历时会检查modCount != expectedModCount，不相等则抛出ConcurrentModificationException，在迭代器遍历中调用迭代器外部的修改方法只会更新modCount，不会更新迭代器的expectedModCount，而迭代器内部提供的修改方法既更新了modCount，同时也将最新的modCount值赋值给expectedModCount。

然而这个限制在COWIterator中不存在！在使用COWIterator迭代器遍历时可以调用外部的修改方法，不会抛出异常。这是因为COWIterator迭代器中复制了一份原数组副本，外部修改数组只是修改了原数组，并不会影响迭代器中正在遍历的数组。

同时COWIterator迭代器也不支持调用迭代器内部的修改方法，全都会抛出UnsupportedOperationException。

既然COWIterator迭代器中遍历的数组是一个副本，修改原数组也不会影响到副本，这就出现一个问题：数据的实时一致性。

打赏