重新认识java-ArrayList

阅读量：5862 次

发布时间：2019-06-19

本文共 10195 字，大约阅读时间需要 33 分钟。

重新认识java-ArrayList

源码解读

ArrayList的声明：

public class ArrayList
    
      extends AbstractList
     
              implements List
      
       , RandomAccess, Cloneable, java.io.Serializable

通过继承和实现关系，可以看出ArrayList继承自抽象类AbstractList，实现了接口List, RandomAccess, Cloneable, java.io.Serializable.

RandomAccess接口

从RandomAccess的声明中可以看到，这只是一个类声明，没有函数和成员变量，那ArrayList的声明中为什么要添加这个接口？原来，List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

接口Clonable ，java.io.Serializable也是同样的道理。通过重写 Object.clone（）方法来定制对其进行复制的细节,如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法，则会导致抛出 CloneNotSupportedException 异常。java.io.Serializable

ArrayList的实现

常量

//list初始容量private static final int DEFAULT_CAPACITY = 10;

变量

/*** ArrayList中元素存储的地方，数组的长度就是它的容量* 不是私有的，方便嵌套类访问。后面提供了迭代类，需要访问*/transient Object[] elementData;/** *ArrayList所包含的元素的大小 */private int size;

构造方法

/** * 使用初始大小创建一个空的list * * @param  initialCapacity  list初始容量 * @throws IllegalArgumentException if the specified initial capacity *         is negative */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
     c) {    elementData = c.toArray();    if ((size = elementData.length) != 0) {        // c.toArray might (incorrectly) not return Object[] (see 6260652)        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, size, Object[].class);    } else {        // replace with empty array.        this.elementData = EMPTY_ELEMENTDATA;    }}

第一种方法需要一个默认的容量大小; 第二个是默认的构造方法，会默认创建一个容量为10的 ArrayList ; 第三个则传给一个 Collection ，注意，不管 Collection 里面是什么类型，最后放进 ArrayList 都会上转为 Object

此处的bug问题，见下节。

核心方法

add

public boolean add(E e) {    ensureCapacityInternal(size + 1);  // 保证当元素的数量超过内部数组elementData的大小后，自动扩容。防止越界    elementData[size++] = e;    return true;}

add 方法中使用了 ensureCapacityInternal 来控制容量：

private void ensureCapacityInternal(int minCapacity) {    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    ensureExplicitCapacity(minCapacity);//根据实际容量判断是不是要增加elementData容量}private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // overflow-conscious code    if (minCapacity - elementData.length > 0)        grow(minCapacity);}

modCount是用来记录 list被结构修改的次数，所谓结构上的修改是指任何添加或删除一个或多个元素的操作，或者显式调整底层数组的大小；仅仅设置元素的值不是结构上的修改；在上面的方法中，如果 minCapacity 大于现有数组长度，则执行 grow 方法：

private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);//当增长到`newCapacity > MAX_ARRAY_SIZE`时，只能创建Integer.MAX_VALUE大小的数组，不能超过这个值    // minCapacity is usually close to size, so this is a win:    elementData = Arrays.copyOf(elementData, newCapacity);}

第二个add方法：

public void add(int index, E element) {    rangeCheckForAdd(index);          //确保插入的位置是在elementData大小范围内，不会越界。    ensureCapacityInternal(size + 1);  // Increments modCount!!    System.arraycopy(elementData, index, elementData, index + 1,                     size - index);    elementData[index] = element;    size++;}

主要使用了 System.arraycopy()方法将 index 之后的元素向后移动一个位置，将 index 位空出来放入新元素

函数原型：System.arraycopy(Object[] src, int srcPos, Object[] dest, int destPos, int length) src: the source array. srcPos: starting position in the source array. dest: the destination array. destPos: starting position in the destination data. length: the number of array elements to be copied.

Clear

public void clear() {    modCount++;    // clear to let GC do its work    for (int i = 0; i < size; i++)        elementData[i] = null;    size = 0;}

clear方法比较简单，但是也会使modCount+1。

只要添加或删除元素或者显示调用底层数组，都会修改modCount

clone

public Object clone() {    try {        ArrayList
     v = (ArrayList
    ) 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(e);    }}

clone 方法只能进行浅复制，并不复制元素本身，实际在内部调用的是Object的clone()。

remove

public E remove(int index) {    rangeCheck(index);    modCount++;    E oldValue = elementData(index);    int numMoved = size - index - 1;    if (numMoved > 0)        System.arraycopy(elementData, index+1, elementData, index,                         numMoved);    elementData[--size] = null; // clear to let GC do its work    return oldValue;}

删除指定下标的元素的时候，只是将待删除后面的元素全部前移，而该元素在内存中的占用由JVM gc自动处理。

public boolean remove(Object o) {        if (o == null) {            for (int index = 0; index < size; index++)                if (elementData[index] == null) {                    fastRemove(index);                    return true;                }        } else {            for (int index = 0; index < size; index++)                if (o.equals(elementData[index])) {                    fastRemove(index);                    return true;                }        }        return false;    }

删除指定对象实例的时候，如果要移除的元素为 null ，则删除数组中第一个为 null 的元素。如果数组中有超过一个匹配的元素，仅移除第一个。

fastRemove(int index)比remove(int index)块在没做index关于elementData的边界检查。其余都是一样的。

toArray

public Object[] toArray() {	return Arrays.copyOf(elementData, size);}

这个方法被很多方法使用，它调用了 Arrays 工具类中的方法 copyOf:

public static 
    
      T[] copyOf(T[] original, int newLength) {    return (T[]) copyOf(original, newLength, original.getClass());}public static 
     
       T[] copyOf(U[] original, int newLength, Class
       newType) {    T[] copy = ((Object)newType == (Object)Object[].class)        ? (T[]) new Object[newLength]        : (T[]) Array.newInstance(newType.getComponentType(), newLength);    System.arraycopy(original, 0, copy, 0,                     Math.min(original.length, newLength));    return copy;}

trimToSize 将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量。

public void trimToSize() {    modCount++;    if (size < elementData.length) {        elementData = (size == 0)          ? EMPTY_ELEMENTDATA          : Arrays.copyOf(elementData, size);    }}

在 ArrayList 容量确定下来以后，可以调用这个方法最小化存储空间

Fast-Fail快速失败机制 此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在创建迭代器之后，除了通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException 。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为无法得到保证，快速失败迭代器会尽最大努力抛出 ConcurrentModificationException 。迭代器的快速失败行为应该仅用于检测 bug。

ArrayList 中定义了一个 modCount 来记录对容器进行结构修改的次数，在 add 、 addAll 、 remove 、 clear 、 clone 方法中都会引起 modCount 变化，而在创建迭代器时，会使用局部变量保存当前的 modCount 值：

private class Itr implements Iterator
    
      {        int cursor;       // index of next element to return        int lastRet = -1; // index of last element returned; -1 if no such        int expectedModCount = modCount;        ...

在进行迭代的过程中，会先检查 modCount 有没有发生变化，以此来判定是否有外部操作改变了容器：

final void checkForComodification() {            if (modCount != expectedModCount)                throw new ConcurrentModificationException();        }

因为 ArrayList 是非同步的，因此，在多线程环境下，如果有对容器进行结构修改的操作，则必须使用外部同步。

关于remove的坑

remove方法有两种实现：remove(int index),remove(Object obj)。但假设一个ArrayList为[5,4,3,2,1],先要删除2这个元素（不是第二号元素！），那么必须使用remove(new Integer(2))或remove(Integer.valueOf(2))，将2转为一个对象实例（不是基础类型），然后调用remove(Object)方法。

remove(数字)默认调用的是remove(index)。

bug理解

参照下面例子理解bug6260652

package com.hgf.collection.List;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import org.junit.Test;/** * @see 参考：http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 * @author hgfdo hgf的博客 * */public class Bug6260652Test {		class BaseClass{			}		class SubClass extends BaseClass{			}		@Test	public void test1(){		//subArray 是[Lcom.hgf.collection.List.Bug6260652Test$SubClass;类型		SubClass[] subArray = new SubClass[3];		System.out.println(subArray.getClass());				//因为java向上转型，所以baseArray 也是[Lcom.hgf.collection.List.Bug6260652Test$SubClass;类型		BaseClass[] baseArray =subArray; 		System.out.println(baseArray.getClass());				//异常：java.lang.ArrayStoreException: com.hgf.collection.List.Bug6260652Test$BaseClass		//因为baseArray下标0指向的内存区域是SubClass实例，现在要新		//建一个BaseClass的实例，肯定就会出错。		baseArray[0] = new BaseClass();				/*		 * 总结:有一个Object[]类型的数组，并不到别我们能将所有的类型的		 * 数据存到数组中，还取决于初始化时的数组元素的实际类型。		 */	}		@Test	public void test2(){		// 返回的是java.util.Arrays$ArrayList(java.util.Array的内部类)，不是java.util.ArrayList		List
    
      list = Arrays.asList("abc","def");		System.out.println(list.getClass());				//[Ljava.lang.String;		Object[] array = list.toArray();		System.out.println(array.getClass());				//与test1有相同的问题，数组在内存中是有具体的数据类型的，		//不能将Object类型的数据随便的赋值给object数组。		array[0] = new Object();	}		@Test	public void test3(){		//因为java.util.ArrayList是利用Object[]实现		//的，list所指向的内存中的数据也是Object类型的，所以		//使用list.toArray()方法得到的Object[]数组的内		//存类型就是Object类型，最后可以修改数组里面的对象实例。		List
     
       list = new ArrayList
      
       ();		list.add("aaa");		list.add("bbb");				//[Ljava.lang.Object;		Object[] object = list.toArray();		System.out.println(object.getClass());				//不会出错，因为object数组里面的数据类型就是Object类型的。		object[0] = new Object();			}}/** * 总结： * 为了考虑这种情况，所以源码中进行了if判断，来防止错误的数组对象导致异常。 * Arrays.copyOf(elementData, size, Object[].class);这个方法就是 * 用来创建1个Object类型，大小为size的数组，这样数组中就可以存放任意对象 * 了，也将某些在内存中实际不是Object类型的转为Object类型，达到与普通情 * 况中ArrayList利用的数组类型一致。 */