Java源码解析之ArrayList-一一网

ArrayList是Java中最常用的集合之一，本文就通过源码来看下它底层的实现

先来说下ArrayList的底层是基于数组实现的，它的优点是随机读的效率很高，对应的缺点就是随机写的效率比较低，因为需要将写入位置以后的所有元素进行移位，以便插入需要写入的元素。同理，删除元素的时候也需要将后面的所有元素向前移位，效率也也会比较低

下面我们来看下ArrayList的主要几个方法的源码：

1. add方法

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

ensureCapacityInternal方法是判断当前数组已经塞满了，剩余容量是否足够放入新元素，如果不够就会进行扩容，这个方法源码我们放到最后单独来看

elementData[size++] = e;这里的elementData就是底层的数组，size表示数组里的元素个数，这行代码就是将新元素赋值到数组已有元素的后面一个位置上，同时size属性加1

比如：当前size=2，elementData数组里有2个元素：a，b，此时add一个新元素c，那么就会将c放入elementData数组的第三个位置，同时size加1变成3

上面两行代码执行成功之后，整个add方法就返回true，元素添加成功

2. get方法

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

        return elementData(index);
    }
复制代码

get方法内部实现很简单

rangeCheck(index);检查数组是否越界

elementData(index);直接通过数组索引定位到元素然后返回，这就是ArrayList随机高效率高的原因

3. set方法

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

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
复制代码

rangeCheck(index);同get方法，检查数组越界

E oldValue = elementData(index);获取需要set的数组位置上的老元素

elementData[index] = element; 直接将新元素赋值到set的数组位置上

最后返回老元素

4. 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;
    }
复制代码

remove方法相对长一点，它的实现原理是通过数组元素拷贝来达到删除的目的，remove方法里同样的方法就不赘述了，重点来看下面这几行代码

  int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null;
复制代码

int numMoved = size – index – 1;这行代码计算出需要拷贝的元素的个数

System.arraycopy(elementData, index+1, elementData, index, numMoved);这行代码是重点，将当前数组从index+1开始的元素拷贝到当前数组的index开始的各个位置，一共拷贝numMoved个元素，这里其实就删除了index位置元素，因为已经被拷贝覆盖了

elementData[–size] = null;将数组最后一位赋值为null，便于回收内存。

举个栗子：
当前elementData=[“a”,”b”,”c”,”d”]，此时size就是4，如果执行remove（2）方法就是删除第3个元素c

通过代码int numMoved = size – index – 1;计算出numMoved = 4-2-1 = 1；说明只有1个需要拷贝的元素

System.arraycopy(elementData, index+1, elementData, index, numMoved);方法从第4个元素d开始拷贝，拷贝1个元素d，然后拷贝到第3个元素c的位置上，结果elementData数组就变成了[“a”,”b”,”d”,”d”]，最后执行elementData[–size] = null，数组就变成[“a”,”b”,”d”]，第3个元素c被删除

5. ensureCapacityInternal方法

最后来看下ensureCapacityInternal方法

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
复制代码

calculateCapacity(elementData, minCapacity)这个方法会返回数组需要的容量，默认最小是10

   if (minCapacity - elementData.length > 0)
            grow(minCapacity);
复制代码

ensureExplicitCapacity()里会判断上面的容量是否大于当前数组的长度，如果大于，则进入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);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
复制代码