ArrayList分析

2019-11-10 20:52:02

字体：大中小

来源：转载

供稿：网友

ArrayList应该是最常用的容器吧，使用非常简单，那我就从源码简单分析下。首先看看ArrayList的继承体系：这里写图片描述先说说其对这些接口的支持吧，

Serializable 一个标记，表明实现此接口的类具有序列化的能力。Cloneable 一个标记，表明实现此接口的类能够调用 java.lang.Object.clone()方法，不然会抛出CloneNotSupportedException；对于Cloneable接口，需要注意一点，属于浅度复制，使用时需要注意，对于引用类型的字段，只会复制引用。public class T01 implements Cloneable{ int i = 3; Object o = 3; public static void main(String[] args) throws CloneNotSupportedException { T01 t = new T01(); T01 t1 = (T01)t.clone(); System.out.PRintln(t1.i == t.i); System.out.println(t1.o == t.o); }}

打印：

truetrue

证明不同引用类型指向同一处内存空间。我们来看下ArrayList对于clone的支持，先看源码：

public Object clone() { try { @SuppressWarnings("unchecked") ArrayList<E> v = (ArrayList<E>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); //集合的内容进行了深度拷贝 v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(); } }

使用ArrayList的clone能够获得和当前引用完全相同的数据。这种写法，对于我们有很重要的借鉴意义，通常实现Cloneable接口的类，最好的做法就是如同上面的代码一样，提供公有的非受检clone方法。对于ArrayList本身的这个方法，估计会用的比较少，因为实现与接口分离的思想，大多数人都会这么写：

List<Integer> list = new ArrayList<Integer>()

而List接口是不提供克隆方法的。

Random access 这个估计一般都会被忽视，主要作用是表示实现此接口的类，应用随机访问比使用迭代器会有更好的性能。下面段代码来自Collections public static <T> void fill(List<? super T> list, T obj) { int size = list.size(); if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i<size; i++) list.set(i, obj); } else { ListIterator<? super T> itr = list.listIterator(); for (int i=0; i<size; i++) { itr.next(); itr.set(obj); } } }

一般情况对于ArrayList都应该使用迭代器进行遍历，不容易出错，尤其应该使用foreach语法。在性能和代码清晰与简单上比较，不是特殊情况，都应该偏向后者，毕竟简单清晰的东西会很容易理解，就算有问题也容易优化。写代码也应该是这种思路，清晰简单的实现最佳，如果难以看出代码的意图，那么就难以保护其中的设计，更难以维护。

闲扯到此为止，现在进入主题。 ArrayList其实就是长度可变的数组，数据长度不是固定的吗，如何进行扩容呢，没办法，只能重新new一个数组，然后把现有的东西复制进去。这就是ArrayList实现的原理。从上面可以看出，性能的优化点主要在减少数据复制或者不复制，怎么办，初始化合理的数组长度，会有助于性能优化。

public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; }

对于ArrayList讨论最多的也就是并发环境下的异常：ConcurrentModificationException，那么什么情况下会抛出呢，看源码：

@SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new **ConcurrentModificationException**(); cursor = i + 1; return (E) elementData[lastRet = i]; }final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

这是遍历器的部分源码，大致可以看出modCount != expectedModCount时抛出异常，expectedModCount是在内部类初始化的时候赋值外部类的modCount 。当两值不同时，肯定是有些操作改变了外部类的modCount ，那是哪些方法呢。分析源码发现，只要是引起底层数组长度变化的方法，都会改变modCount,都有可能抛出异常，为什么是有可能呢？因为没有正确的同步，其他线程对modCount值的改变可能对执行遍历的线程不可见，这也是兼顾性能后做出的最大的努力，快速失败（fail-fast）。所以在并发的环境有写操作，ArrayList有很大的风险，会造成遍历的失败，对于并发使用，JUC中提供了CopyOnWriteArrayList，遍历开始指向原数组空间，写的时候复制原数组形成新数组，最后赋值给原数组引用，由于遍历器是指向的原数组地址空间，写操作并不会对遍历产生影响。但是具体如何使用，还得具体问题具体分析，只有熟悉了各自的不足，才能正确的规避。

上一篇：SQLServer2012数据库降级方法

下一篇：codeforces#395