转载

jdk1.8-Java集合框架之二-ArrayList源码分析

一、说到ArrayList，大家都知道是有序集合，有下标，读速度快，写速度慢。但是问一句为什么是有序、为什么有下标、为什么读速度快、为什么什么写速度慢，估计很多人答不上来。那么接下来我们就从源码的角度来分析。

二、我们先来看一张图：

通过这张图，我们可以看到，ArrayList类，继承了一个抽象类AbstractList，实现了四个接口，分别是Cloneable、Serializable、RandomAccess、List这四个接口。Cloneable、Serializable这两个接口我们知道是对象克隆和序列化相关的，我们暂时不管。

我们先看一下RandomAccess接口。

复制代码

打开源码一看，这是一个空接口，即标记接口，这个接口的作用就是使ArrayList具备快速随机访问的功能。什么是随机访问？就是随机访问ArrayList中的任何一个元素。那ArrayList是如何快速随机访问任何一个元素的呢，我们稍后再说明。 2. 我们再来看下父类AbstractList，从上面的图1可以看出，AbstractList是一个抽象类，也同样实现了List接口，我们可以猜想，AbstractList是对List的具体实现类进行的抽象化的提取。由于篇幅原因，代码为就不贴了。 3. 接下来我们就看ArrayList类代码的具体实现，首先我们看到ArrayList类定义了4个常量，2个实例变量，分别是：

//默认容量 private static final int DEFAULT_CAPACITY = 10; //空元素数组 private static final Object[] EMPTY_ELEMENTDATA = {}; //默认容量对应的空元素数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //元素，被transient关键字修饰，无需序列化 transient Object[] elementData; // non-private to simplify nested class access //长度 private int size; //最大长度 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

从以上源码我们可以猜想，ArrayList是通过内部维护一个的Object对象数组实现的，且默认的ArrayList容量是10。 4. 接下来看下ArrayList的构造函数，ArrayList一共定义了3个构造函数，分别是：

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //指定初始化容量，如果指定容量大于0，则设置元素数组为指定长度的对象数组；
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //如果指定容量等于0，那么设置元素数组为空数组；
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //如果指定容易小于0，则抛出异常；
            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) {
            // 如果元素数组长度不为0，且数组对象不是Object，则将数组元素转为Object对象；
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果元素数组长度为空，则替换成常量空数组；
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
复制代码

接下来我们具体分析下ArrayList的几个常用方法，首先是get：

public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    E elementData(int index) {
        return (E) elementData[index];
    }
复制代码

很明显，我们能看得出，get方法纯粹就是ArrayList内部维护的元素数组操作，通过数组下标取值，非常简单。至此，回顾一开始的问题，ArrayList为什么读取快？因为是数组下标直接读取操作，复杂度是O(1)。

继续看无参数add方法：

public boolean add(E e) { 
        //将数组长度+1作为add操作需要的最小容量传入方法中
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;    //将元素添加到数组末端，因此主要逻辑在前一句代码
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    //根据当前元素数组长度，和add操作需要的最小容量做比较，确定操作需要的最小容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    //该步骤确保元素数组满足操作所需的最小容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 若所需的最小容量大于当前元素数组长度，则对元素数组进行扩容处理
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //扩容操作
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 新容量=旧容量+旧容量/2；
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //若第一步扩容后，新容量还是不满足所需最小容量，则将新容量设置为所需最小容量；
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 若新容量比最大的允许容量还大，那么需要重新计算新容量；
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 计算完毕，将元素复制到新容量的数组上
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
复制代码

以上无参数的add方法源码，其实带参数的add方法跟无参数的基本一样，只是增加了一个指定位置到数组末端元素复制的方法，如下：

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

能看得出，ArrayList的无参数add方法，需要经过两个大步骤，第一步是计算容量，第二步是如果扩容了，需要将原来数组内的元素，全量复制到新的数组上。至此，我们又能回答一开始的问题，ArrayList为什么写操作慢？因为ArrayList写操作会对部分甚至全部元素进行移动操作，同理，对于set、remove等写操作的方法，整体上都是这样的操作，所以写操作效率低。

原文 https://juejin.im/post/5e0a14b4f265da33c42825a2

正文到此结束