一、简单介绍
【1】ArrayList是List接口的可调整大小的数组实现。实现所有可选的列表操作,并允许放入任何类型的元素,包括null。除了实现List接口之外,此类还提供一些方法来操纵内部用于存储列表的数组的大小。(此类与Vector大致等效,但它是不同步的,即非线程安全的。)
【2】size isEmpty,get,set,iterator和listIterator操作在常量时间内运行。add操作以摊销常量时间(amortized constant time)运行,也就是说,添加n个元素需要O(n)时间。所有其他操作均以线性时间运行(大致而言)。与LinkedList实现相比,ArrayList的常数因子较低。
【3】每个ArrayList实例都有一个容量。容量表示在列表中存储元素的数组的大小(并不是ArrayList中元素的个数,个数是size)。它总是至少与列表大小一样大。将元素添加到ArrayList后,其容量会自动增长。除了添加元素具有固定的摊销时间成本外,没有指定增长策略的详细信息。
【4】应用程序可以使用ensureCapacity操作在添加大量元素之前增加ArrayList实例的容量。这可以减少因元素增加重新分配容量的次数。
【5】请注意,此实现不同步,因此是非线程安全的。如果多个线程同时访问ArrayList实例,并且至少有一个线程在结构上修改列表,则必须在外部进行同步。(结构修改是添加或删除一个或多个元素或显式调整后备数组大小的任何操作;仅设置元素的值不是结构修改。)通常,通过在自然封装列表的某个对象上进行同步来完成此操作。如果不存在这样的对象,则应使用Collections.synchronizedList方法“包装”列表。最好在创建时完成此操作,以防止意外的不同步访问列表:
List list = Collections.synchronizedList(new ArrayList(...));
【6】此类的迭代器和listIterator方法返回的迭代器是快速失败的:如果在创建迭代器之后的任何时间以任何方式对列表进行结构修改,除非通过迭代器自己的remove或add方法,否则迭代器将抛出ConcurrentModificationException。因此,面对并发修改,迭代器会快速干净地失败,而不会在未来的不确定时间冒着任意、不确定的行为的风险。
【7】请注意,迭代器的快速失败行为无法得到保证,因为通常来说,在存在不同步的并发修改的情况下,不可能做出任何严格的保证。快速失败的迭代器会尽最大努力抛出ConcurrentModificationException。因此,编写依赖于此异常的程序的正确性是错误的:迭代器的快速失败行为应仅用于检测错误。
二、结构修改
结构修改是添加或删除一个或多个元素或显式调整后备数组大小的任何操作;仅设置元素的值不是结构修改。
三、快速失败
如果在创建迭代器之后的任何时间以任何方式对列表进行了结构修改,则除了通过迭代器自己的remove或add方法之外,迭代器都会抛出ConcurrentModificationException。因此,面对并发修改,迭代器会快速且干净地失败,而不会在未来的不确定时间内冒任意不确定的行为的风险。
不过注意,迭代器的快速失败行为无法得到保证,因为通常来说,在存在非同步的并发修改的情况下,不可能做出任何严格的保证。快速失败的迭代器会尽最大努力抛出ConcurrentModificationException。因此,编写依赖于此异常的程序的正确性是错误的:迭代器的快速失败行为仅应用于检测错误。
四、ArrayList的默认初始容量
1.数据域
这里展示了ArrayList中的数据域,并解释了它们的含义:
private static final int DEFAULT_CAPACITY = 10; //默认的初始容量 private static final Object[] EMPTY_ELEMENTDATA = {}; //用于空实例的共享空数组实例。 /** * 共享的空数组实例,用于默认大小的空实例。 我们将此与EMPTY_ELEMENTDATA区别开来,以了解添加第一个元素时要增加多少容量。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 存储ArrayList的元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。 添加第一个元素时,任何具有elementData == * DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY。 */ transient Object[] elementData; // 非私有类型,以简化嵌套类访问 /** * ArrayList包含的元素个数 * * @serial */ private int size;
2.容量
根据1可知ArrayList的容量是elementData数组的长度。再看构造器
/** public ArrayList(int initialCapacity) { //指定容量 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } public ArrayList() { //空参 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(Collection<? extends E> c) { //构造一个列表,该列表包含指定集合的元素。 Object[] a = c.toArray(); if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. elementData = EMPTY_ELEMENTDATA; } }
【1】因此对于无参构造方法,elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA,因此初始容量初始为0且在第一次增加时改为DEFAULT_CAPACITY,也就是说默认的容量是0。
【2】对于带参方法,若容量为正,则初始化elementData = new Object[initialCapacity],初始容量为initialCapacity或集合c的长度,若容量为0,则elementData = EMPTY_ELEMENTDATA,将其指定为空数组,初始容量为0。
五、扩容机制
只有调用add()方法才可能产生扩容,add()的源码如下:
private void add(E e, Object[] elementData, int s) { if (s == elementData.length) //如果容量不够则调用grow()函数增加容量 elementData = grow(); elementData[s] = e; size = s + 1; } public boolean add(E e) { //在末尾添加元素 modCount++; //表示结构修改次数检测快速失败,如果modCount不正确地增加,那么就会发生快速失败 add(e, elementData, size); return true; } public void add(int index, E element) { //在指定位置添加元素 rangeCheckForAdd(index); //检查index是否越界 modCount++; //表示结构修改次数检测快速失败,如果modCount不正确地增加,那么就会发生快速失败 final int s; Object[] elementData; if ((s = size) == (elementData = this.elementData).length) elementData = grow(); System.arraycopy(elementData, index, elementData, index + 1, s - index); //本地方法,用于复制数组 elementData[index] = element; size = s + 1; } private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, /* minimum growth */ oldCapacity >> 1 /* preferred growth */); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } } private Object[] grow() { return grow(size + 1); }
从上述代码可以看出:
【1】快速失败机制由modCount实现。
【2】扩容时,比较的是minCapacity - oldCapacity(最少应加容量)以及oldCapacity >> 1 (当前容量的一半,参考增加容量),并取其中的较大者,并根据这个值增加容量。(扩容机制)
【3】从这里我们也可以看出,ArrayList不适合插入、删除元素,因为它的数组更新方式是System.arraycopy,它需要将索引后面所有的元素都复制。