阿里面试官没想到,一个Java 的 CopyOnWriteArrayList,我都能跟他吹半小时,惊呆了。
先看再点赞,给自己一点思考的时间,微信搜索【沉默王二】关注这个靠才华苟且的程序员。
本文 GitHub github.com/itwanger 已收录,里面还有一线大厂整理的面试题,以及我的系列文章。
hello,同学们,大家好,我是沉默王二,在我为数不多的面试经历中,有一位姓马的面试官令我印象深刻,九年过去了,我还能记得他为数不多的发量。
老马:“兄弟,ArrayList 是线程安全的吗?”
王二:“不是啊。”
老马:“那有没有线程安全的 List?”
王二:“有啊,Vector。”
老马:“还有别的吗?”
王二:“Vector 不就够用了吗?”
老马看了一下左手腕上的表,说道:“今天差不多就到这里吧,你回去等通知。”
(不是,我特么不是刚进来,就回答了三个问题而已,就到这了?)
现在回想起来当时一脸懵逼的样子,脸上情不自禁地泛起了红晕,老马的意思是让我说说 Java 的 CopyOnWriteArrayList,可惜我当时几乎没怎么用过这个类,也不知道它就是个线程安全的 List,惭愧啊惭愧。
(地上有坑吗?我想跳进去。)
真正的勇士敢于直面过去的惨淡,经过这么多年的努力,我的技术功底已经大有长进了,是时候输出一波伤害了。希望这篇文章能够给不太了解 CopyOnWriteArrayList 的同学一点点帮助,到时候给面试官一个好看。
注:我用的是 OpenJDK 14。
01、Vector
Vector 的源码文档上直截了当地说了,“如果不需要线程安全,推荐使用 ArrayList 替代 Vector。”说实话,在我十多年的编程生涯中,的确很少使用 Vector,因为它的线程安全是建立在每个方法上都加了 synchronized 关键字的基础上,锁的粒度很高,意味着性能就不咋滴。
public synchronized boolean add(E e) { modCount++; add(e, elementData, elementCount); return true; } public synchronized E remove(int index) { modCount++; if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue = elementData(index); int numMoved = elementCount - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--elementCount] = null; // Let gc do its work return oldValue; }
就连 size() 这样的方法上都加了 synchronized,可想而知,Vector 有多铺张浪费,有多锦衣玉食。
如果对 synchronized 关键字不太了解的话,可以点击下面的链接查看我之前写的一篇文章。
我去,你竟然还不会用 synchronized
高并发的情况下,一般都要求性能要给力,Vector 显然不够格,所以被遗忘在角落也是“罪有应得”啊。
02、SynchronizedList
那有些同学可能会说,可以使用 Collections.synchronizedList() 让 ArrayList 变成线程安全啊。
public static <T> List<T> synchronizedList(List<T> list) { return (list instanceof RandomAccess ? new Collections.SynchronizedRandomAccessList<>(list) : new Collections.SynchronizedList<>(list)); }
无论是 SynchronizedRandomAccessList 还是 SynchronizedList,它们都没有在方法级别上使用 synchronized 关键字,而是在方法体内使用了 synchronized(this) 块。
public void add(int index, E element) { synchronized (mutex) {list.add(index, element);} } public E remove(int index) { synchronized (mutex) {return list.remove(index);} }
其中 mutex 为 this 关键字,也就是当前对象。
final Object mutex; // Object on which to synchronize
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
03、ConcurrentModificationException
ConcurrentModificationException 这个异常不知道同学们有没有遇到过?我先来敲段代码让它发生一次,让同学们认识一下。
List<String> list = new ArrayList<>(); list.add("沉默王二"); list.add("沉默王三"); list.add("一个文章真特么有趣的程序员"); for (String str : list) { if ("沉默王二".equals(str)) { list.remove(str); } } System.out.println(list);
运行这段代码就会抛出 ConcurrentModificationException:
Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1012)
at java.base/java.util.ArrayList$Itr.next(ArrayList.java:966)
通过异常的堆栈信息可以查找到,异常发生在 ArrayList 的内部类 Itr 的 checkForComodification() 方法中。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
也就是说,在执行 checkForComodification() 方法的时候,发现 modCount 和 expectedModCount 不等,就抛出了 ConcurrentModificationException 异常。
为什么会这样呢?之前的代码也没有调用 checkForComodification() 方法啊!
那就只能来看一下反编译后的字节码了,原来 for-each 这个语法糖是通过 Iterator 实现的。
List<String> list = new ArrayList();
list.add("沉默王二");
list.add("沉默王三");
list.add("一个文章真特么有趣的程序员");
Iterator var3 = list.iterator();
while (var3.hasNext()) {
String str = (String) var3.next();
if ("沉默王二".equals(str)) {
list.remove(str);
}
}
System.out.println(list);
在执行 list.iterator() 的时候,其实返回的就是 ArrayList 的内部类 Itr。
public Iterator<E> iterator() {
return new ArrayList.Itr();
}
1
2
3
迭代器 Iterator 是 fail-fast 的,如果以任何方式(包括 remove 和
add)对迭代器进行修改的话,就会抛出 ConcurrentModificationException。
迭代器在执行 remove() 方法的时候,会对 modCount 加 1。remove() 方法内部会调用 fastRemove() 方法。
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
当在进行下一次 next() 会执行 checkForComodification() 方法,结果发现 modCount 为 4,而 expectedModCount 为 3,于是就抛出了异常。
之所以在单线程的情况下就抛出 ConcurrentModificationException,就是为了在多线程并发的情况下,不冒任何的危险,提前规避掉其他线程对 List 修改的可能性。
ArrayList 返回的迭代器是 fail-fast 的,Vector 的也是,SynchronizedList 的也是。这就意味着它们在多线程环境下通过 for-each 遍历进行增删操作的时候会出问题。