Java ArrayList 学习

 

注：这里使用java 1.6版本

1.ArrayList继承AbstractList，实现List、RandomAccess、Cloneable、Serializable接口；

2.ArrayList的内部，通过数组实现。

    如下：

 

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private transient Object[] elementData;

 

 

    在ArrayList中，虽然是泛型的，但是实现的时候，使用的是Object数组；原因应该是java目前不支持泛型数组。

    ArrayList的容量是数组的长度。（注：HashMap内部也是通过数据实现的，其容量（capacity）也正好是数组的长度；不同的是，HashMap的实现是Entry数组）

3.ArrayList的初始化方法

    ArrayList有3中初始化方法：

    Public ArrayList(int initialCapacity);

    这是基本的初始化方法，代码如下：

 

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param   initialCapacity   the initial capacity of the list
     * @exception IllegalArgumentException if the specified initial capacity
     *            is negative
     */
    public ArrayList(int initialCapacity) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];
    }

 

 

    这里super()方法是一个空的方法；

    然后是参数校验；

    最后初始化数组对象，完成整个初始化方法。

 

    Public ArrayLIst();

    调用了第一个初始化，默认的容量是10；

 

    Public ArrayList(Collection<? Extends E> c);

    这是使用已有的集合类进行初始化，代码如下：

 

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
	size = elementData.length;
	// c.toArray might (incorrectly) not return Object[] (see 6260652)
	if (elementData.getClass() != Object[].class)
	    elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

 

 

    正常情况下，将原有集合中的元素拷贝到elementData数组中即可，然后设置元素的个数；对于某些情况，c.toArray()方法，可能不能返回一个Object数组，所以最后进行了一次类型检查——当类型不匹配的时候，需要执行copyof方法，将类型进行一次转换。

    Copyof方法的代码如下：

 

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> 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;
    }

 

 

    需要注意的是，这里申请了新的内存空间。

 

4.trimToSize

    减少ArrayList的长度为size；

    ArrayList的容量应是内部数组elementData的长度，这里使用实际元素的数量size进行一次裁剪。在保证内容的前提下，减少ArrayList的容量。

    实现的方式是使用前面提到的copyOf方法，这里重新申请了内存空间，将元素拷贝之后，原来的数组将会被回收。但是存在一定的开销。

    同时，使用这个方法的时候，最好能够保证后续不再会向ArrayList中写入数据了，否则数组扩容，也要有一定的开销。

    慎用。

 

5.ArrayList的扩容方法

    具体代码如下：

 

    public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

 

 

    ArrayList的扩容，通过ensureCapacity方法实现；参数是新的容量大小。

    扩容通过两步执行，先扩容1.5倍；如果新的容量还是小于参数值，那么直接将容量设置为参数值大小。所以，有可能出现执行该方法之后，新的ArrayList的容量和设置的参数值不同的情况。

    具体的执行还是通过Arrays的copyof方法进行，末尾通过null进行补全。

 

6.indexOf和lastIndexOf

    判断一个元素是否存在在ArrayList当中；

    indexOf找到该元素的第一个位置，lastIndexOf找到该元素的最后一个位置；如果找到了，则返回该元素的位置；如果没有找到，则返回-1。

    indexOf的代码如下：

 

    public int indexOf(Object o) {
	if (o == null) {
	    for (int i = 0; i < size; i++)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = 0; i < size; i++)
		if (o.equals(elementData[i]))
		    return i;
	}
	return -1;
    }

 

 

    在indexOf方法中，使用循环进行查找；所以如果数组的容量很大，在最坏的情况下（参数元素不在ArrayList中），需要遍历完所有的元素，这个性能开销还是比较大的。

    这里对于null和非null元素进行了分开判断；对于null元素的查找，直接使用“==”进行判断，对于非null元素，使用“equals方法”。这样在执行效率上略有区别。

    lastIndexOf方法和indexOf方法基本上是一样的。不同的地方在于，indexOf的遍历，从头部开始，而lastIndexOf方法的遍历，从尾部开始。所以这里就不贴出lastIndexOf方法的代码了。

    另外，在ArrayList中，contains方法也是通过indexOf方法实现的。只需要判断结果是不是-1即可。

 

7.clone

    ArrayList实现了cloneable接口，其clone()方法的实现如下：

 

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

 

 

    这里还是同Arrays的copyOf方法实现的；不过没看明白，怎么没有设置新的ArrayList的size参数。写了测试代码，发现clone之后的ArrayList，size的参数是进行了设置的；没看懂是在clone的那一步执行的……

 

8.toArray

    ArrayList的toArray方法，返回数组形式的元素；

    这里通过Arrays.copyOf方法进行实现，所以这里的返回结果还是新的对象，改动不会变更原有的ArrayList的结果。

    还有一种toArray的实现：

 

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
	System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

 

 

    这里是将ArrayList的元素写入指定的数组a中。

    默认的toArray方法，返回的是Object数据；而带参数的toArray方法，返回的类型是T或者T的子类，类型是有保证的。同时，带参数的toArray方法，一般情况下，返回的数组就是参数a的数组，但是当a的长度小于size时，就会是一个新的数组。此时，新数组的创建是有额外的开销的，使用的时候需要特别注意。

    在ArrayList中，对于元素的拷贝有多处使用。

 

9.get方法

    ArrayList的get方法如下：

 

    public E get(int index) {
	RangeCheck(index);

	return (E) elementData[index];
    }

 

 

    首先使用RangeCheck方法，检查数组是否越界；

    如果越界，则抛异常出来；正常情况下，返回对应的结果。这里对于返回的结果进行了强制类型转换。

 

    private void RangeCheck(int index) {
	if (index >= size)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);
    }

 

 

10.set方法

    set方法将元素写入到ArrayList中。

 

    public E set(int index, E element) {
	RangeCheck(index);

	E oldValue = (E) elementData[index];
	elementData[index] = element;
	return oldValue;
    }

 

 

    首先，还是进行类型检查；正常后，保存旧值，写入新值；最后，返回旧值。

    相对来说比较简单的操作。

 

11.add方法

    add方法像ArrayList中插入新的元素，元素写到末尾。

 

    public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

 

 

    这里先是进行容量检查，如有必要，进行扩容处理；

    然后将正确的结果写入数组的末尾，size增加1。

    这里，进行容量检查的时候，modCount会加1，无论最后是否进行了扩容。

    还有一种带参数的add方法，将元素E，写入指定的位置。

 

    public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);  // Increments modCount!!
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
    }

 

 

    还是先进行数据越界检查；容量检查；然后从index位置开始，将所有元素的位置向后移一位；最后把新的元素插入到index的位置。

 

12.remove方法

    ArrayList提供了两种remove方法，一种是remove某个位置的元素，另外一种是删除元素E。

 

    public E remove(int index) {
	RangeCheck(index);

	modCount++;
	E oldValue = (E) elementData[index];

	int numMoved = size - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work

	return oldValue;
    }

 

 

    流程如下：

    数组越界检查；

    modCount自增；

    获取要删除的位置上的元素；

    通过移位操作，将从该位置开始的元素，向前移动1位；

    设置最后的数组元素为null，其值将被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;
    }

 

    这里基于元素的删除，是将首次出现的该元素进行删除；如果该元素出现在ArrayList中，则进行删除；否则，返回false。

    这里先进行元素的查找，和contains方法中的一致；

    查找到对应的元素之后，使用fastRemove方法进行删除。这里的fastRemove方法就是移位删除，和前面的基于位置的删除是一样的。

    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work
    }

 

13.clear方法

    将ArrayList中的所有数组中的元素设置为null；size清零。同时modCount加一，ArrayList总的数组长度不变。

    public void clear() {
	modCount++;

	// Let gc do its work
	for (int i = 0; i < size; i++)
	    elementData[i] = null;

	size = 0;
    }

 

14.addAll方法

    ArrayList提供两种添加集合的方法。

    先看第一种：

    public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
        int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
	return numNew != 0;
    }

 

    这个方法和add方法基本类似。

    第二种，将集合元素加入ArrayList的某个位置。

    public boolean addAll(int index, Collection<? extends E> c) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: " + index + ", Size: " + size);

	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount

	int numMoved = size - index;
	if (numMoved > 0)
	    System.arraycopy(elementData, index, elementData, index + numNew,
			     numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
	size += numNew;
	return numNew != 0;
    }

 

    这里将数据形式的集合元素，插入从index元素开始的位置。

    流程如下：

    检查参数index，保证其大于0，小于size；

    获取集合元素的数组形式；

    容量检查；

    将从index位置开始的ArrayList元素，向后移动；

    将集合元素插入到ArrayList中，通过system的arraycopy完成。

    Size完成变更；

    返回。

    这个返回结果，有点莫名其妙……

 

15.removeRange

    删除ArrayList中，某个范围内的元素。

    如下：

    protected void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

	// Let gc do its work
	int newSize = size - (toIndex-fromIndex);
	while (size != newSize)
	    elementData[--size] = null;
    }

 

    还是通过system的arraycopy完成；将末尾的元素全部设置为null。

    这里没有对from和to进行检查。不过，这是个protected的方法，不公开访问。

 

16.最后，ArrayList为了满足序列化的要求，实现了writeObject和readObject的方法。

    相对来说，ArrayList比HashMap稍微简单一些。