java源码-ArrayList

开篇

 ArrayList主要由如下特性：

• ArrayList实际上是通过一个数组去保存数据的，当我们构造ArrayList时，如果使用默认构造函数，ArrayList的默认容量大小是10。

• 当ArrayList容量不足以容纳全部元素时，ArrayList会自动扩张容量，新的容量 = 1.5*原始容量。

• ArrayList的克隆函数，将全部元素克隆到一个数组中，采用Arrays.copyOf方法实现。

• ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写出“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

• 在做ArrayList的遍历的时候有3中遍历的方法，分别是随机访问遍历，用迭代器遍历和强制for循环遍历，按照效率来说最快的是随机访问遍历，最差的是迭代器遍历。

• ArrayList的遍历是不安全的，在遍历的时候如果改变了集合的结构会抛出ConcurrentModificationException异常。

ArrayList类图

ArrayList类图

ArrayList类定义

 ArrayList的类定义比较简单，基本上可以看出来默认值数组大小为10，数据存储通过elementData变量。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    // 默认初始化大小
    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //默认是package-private access，保存数据
    transient Object[] elementData; 

    //实际保存的数据量大小
    private int size;
}

ArrayList构造函数

 ArrayList的构造数非常简单，根据传入的参数initialCapacity初始化数组大小。如果不传参数就默认构建空数组。

    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) {
        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;
        }
    }

ArrayList常用操作

ArrayList的add操作

  ArrayList的add操作其实就是分两步走：

• 以size+1的大小去看下是否容纳的下新元素，否则就以1.5的原有空间扩容。
• 在扩容后的新数组的index位置插入新元素。
• grow()方法内部实现扩容和旧元素的拷贝，采用Arrays.copyOf(elementData, newCapacity)实现。

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


    public void add(int index, E element) {
        rangeCheckForAdd(index);

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

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    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);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList的remove操作

  ArrayList的remove操作分两步走：

• 将待移除的index往后的元素拷贝至index开始的位置。
• 将最后一位元素置null并且size-1即可。
  ArrayList的clear操作负责将数组全部置null即可。

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;
    }


public void clear() {
        modCount++;

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

        size = 0;
    }

ArrayList迭代器

  ArrayList的迭代器实现很简单，通过创建Itr对象。在Itr类当中将cursor初始化为0，next过程中就是返回变量同时将cursor+1，hasNext()方法只是判断cursor是否等于size的值。

public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        int cursor;       // 默认初始化值为0
        int lastRet = -1; // 上一个返回值的下标
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        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];
        }
    }

参考文章

ArrayList的特性