一、问题导读
1. ArrayList如何扩容?
2. 什么时候会有ConcurrentModificationException？
3. 当我们一般提到ArrayList的话都会脱口而出它的几个特点：有序、可重复、查找速度快，但是插入和删除比较慢，线程不安全，那么问题来了：为什么说是有序的？怎么有序？为什么又说插入和删除比较慢？为什么慢？还有线程为什么不安全？所以带着这些问题，我们一一的来源码中来找找答案。
二、ArrayList数据结构
三、核心代码
1. add方法
//将指定的元素追加到列表的末尾
public boolean add(E e) {
ensureCapacityInternal(size +1); // 增量模式计数!!
elementData[size++] = e;
returntrue;
}
//确定内部容量的方法
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//判断当前集合是否超多最大容量，即是否有容量溢出现象
if (minCapacity - elementData.length >0)
grow(minCapacity);
}
//集合内部维护的是数组扩容
private void grow(int minCapacity) {
int oldCapacity = elementData.length;//拿到当前集合大小
int newCapacity = oldCapacity + (oldCapacity >>1);//计算集合新的容量大小
if (newCapacity - minCapacity <0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE >0)
newCapacity = hugeCapacity(minCapacity);
//复制旧集合数据到新的集合中（内部维护的数组扩容-产生新的数组）
elementData = Arrays.copyOf(elementData, newCapacity);
}
扩容机制
2. Fail-Fast
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。
ArrayList自己实现了序列化和反序列化的方法，因为它自己实现了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
3. 为什么说是线程不安全的
以add方法为例，整个add()方法可以拆为两步，第一步在elementData[Size] 的位置存放此元素，第二步增大 Size 的值。我们都知道我们的CUP是切换进程运行的，在单线程中这样是没有问题的，但是一般在我们项目中很多情况是在多线程中使用ArrayList的，这时候比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 ，所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。这样就会得到元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这样就造成了我们的线程不安全了。
四、COW 隆重登场
CopyOnWriteArrayList是Java并发包中提供的一个并发容器，它是个线程安全且读操作无锁的ArrayList，写操作则通过创建底层数组的新副本来实现，是一种读写分离的并发策略，我们也可以称这种容器为"写时复制器"。
为什么没有ConcurrentModificationException？
1. 实现原理
集合框架中的ArrayList是非线程安全的，Vector虽是线程安全的，但由于简单粗暴的锁同步机制，性能较差。而CopyOnWriteArrayList则提供了另一种不同的并发处理策略（当然是针对特定的并发场景）。
很多时候，我们的系统应对的都是读多写少的并发场景。通过空间换时间的方式来提高读的效率并保证写的安全性。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。
2. 核心代码
add方法
public boolean add(E e) {
//ReentrantLock加锁，保证线程安全
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//拷贝原容器，长度为原容器长度加一
Object[] newElements = Arrays.copyOf(elements, len +1);
//在新副本上执行添加操作
newElements[len] = e;
//将原容器引用指向新副本
setArray(newElements);
returntrue;
} finally {
//解锁
lock.unlock();
}
}
remove方法
public E remove(int index) {
//加锁
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
//如果要删除的是列表末端数据，拷贝前len-1个数据到新副本上，再切换引用
setArray(Arrays.copyOf(elements, len - 1));
else {
//否则，将除要删除元素之外的其他元素拷贝到新副本中，并切换引用
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
//解锁
lock.unlock();
}
}
3. COW缺陷
CopyOnWrite容器有很多优点，但是同时也存在两个问题，即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。
内存占用问题。因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比如说200M左右，那么再写入100M数据进去，内存就会占用300M，那么这个时候很有可能造成频繁的Yong GC和Full GC。
针对内存占用问题，可以通过压缩容器中的元素的方法来减少大对象的内存消耗，比如，如果元素全是10进制的数字，可以考虑把它压缩成36进制或64进制。或者不使用CopyOnWrite容器，而使用其他的并发容器。
数据一致性问题。CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。
五、总结
ArrayList
增删改查中， 增导致扩容，则会修改modCount，删一定会修改。 改和查一定不会修改modCount。
扩容操作会导致数组复制，批量删除会导致 找出两个集合的交集，以及数组复制操作，因此，增、删都相对低效。 而 改、查都是很高效的操作。
和Vector的区别，Vector的内部也是数组做的，区别在于Vector在API上都加了synchronized所以它是线程安全的，以及Vector扩容时，是翻倍size，而ArrayList是扩容50%。
ArrayList自己实现了序列化和反序列化的方法。
COW
CopyOnWriteArrayList中写操作需要大面积复制数组，所以性能肯定很差，但是读操作因为操作的对象和写操作不是同一个对象，读之 间也不需要加锁，读和写之间的同步处理只是在写完后通过一个简单的“=”将引用指向新的数组对象上来，这个几乎不需要时间，这样读操作就很快很安全，适合 在多线程里使用，绝对不会发生ConcurrentModificationException ，所以最后得出结论：CopyOnWriteArrayList适合使用在读操作远远大于写操作的场景里，比如缓存。
疑问点：
为什么CopyOnWriteArrayList的set/remove/add等方法上锁代码不是this.lock.lock(),而非要来弄个引用指向？有心还是无意。CopyOnWriteArrayList的这些方法为什么要通过数组的拷贝来实现？不是已经有锁来保证了安全吗？这样做性能不是很低吗。
网友评论