Arraylist源码分析

ArrayList底层是一个数组，所以对arraylist的增删改操作，其实就是对数组的增删改。它具有数组的特性：查询时间复杂度o(1)，修改的时间复杂度与需要被修改的元素个数成正比，最坏情况下（在头部插入或者删除一个元素）是o(n)。

arraylist与数组的不同在于他是可以动态扩容，也就是不断的拷贝老数据到新的更大的数组中。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。

ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。

ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

下面，我们通过代码来深入了解一下arraylist。

ArrayList属性

//默认容量大小为10
private static final int DEFAULT_CAPACITY = 10;
//容量为0时的数组对象，用于有参构造设置initialCapacity为0返回
private static final Object[] EMPTY_ELEMENTDATA = {};
//官方注释描述它:用于默认大小的空数组对象，EMPTY_ELEMENTDATA两者的区别是当插入数据时知道扩容多少，即用于无参构造返回
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//用于存放数组内容
transient Object[] elementData; 
//数组里实际所有值数量
private int size;

构造函数

传入容量大小，不为0初始化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);
        }
    }

无参构造函数，返回DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

入参为Collection的实现类

1. 先将入参c转为array赋值给elementData
2. 如果入参的大小为0的话，将elementData设置为EMPTY_ELEMENTDATA
3. 否则重新将elementData重新拷贝为Object[]

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是如何实现扩容呢？答案是：开一个新的数组，将之前的数据拷贝进去。这也说明了，arraylist增删的开销极大，尽可能在查多改少的场景下使用。

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

这里的ensureCapacityInternal(size + 1)就是扩容的核心方法了，他用来判断数组是否有足够的空间。

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

方法很简单，如果elementData的数量不够，扩容，传入需要的容量大小。

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的扩容没有盲目的容量+1，通过oldCapacity + (oldCapacity >> 1)将容量扩大到现在的1.5倍。再次判断扩容后的大小是否满足需要的长度，如果不够就扩大到需要的大小。这一步是为了确保在addAll(Collection<? extends E> c)方法中合并数组不会出现问题。
扩容之后，在size位置上插入元素，size+1，完成了一次插入。

上面的方法是插入单个元素，插在数组尾，那么我们在指定位置插入数据会是怎么样操作的呢？

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

1. 检查index是否越界，判断数组长度满足插入
2. 将从插入位置直到最后一个元素拷贝到新的位置上去
3. 插入新值

除此之外，arraylist还提供了addAll(int,collection)，实现思想已经在上面都提到过了。

删

arraylist的删除的操作也就是将后面的数组复制到前面来，覆盖老的值，然后将最后删除个数的数组设为null，方便gc。值得注意的一点是删除指定对象时的循环是根据equals来进行删除的。

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采用equals。

改

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

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

直接设置值，没啥好说的。

查

1. rangeCheck(int index)方法是判断数组越界与否，即index>size，越界抛出异常
2. index合理后，根据数组下标获取到元素返回。elementData(int index)方法就是直接返回的elementData[index]

    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

ArrayList只提供了这一个方法获取指定下标的元素，不过还可以根据迭代器Iterator循环获取数组的元素，这里不再占用篇幅，我会写另一篇文章专门分析迭代器以及list循环多种方式的优劣。