java容器源码分析--ArrayList（JDK1.8）

作者: w1992wishes | 来源:发表于2018-03-27 16:12 被阅读21次

本篇结构：

前言
ArrayList的数据结构
ArrayList中的重要参数
常用方法
源码分析
疑问解答
ArrayList分析总结

一、前言

同HashMap一样，ArrayList是很常用的集合类了，其源码相对来说简单一些，下面简单分析一下。

二、ArrayList数据结构

ArrayList的底层数据结构就是一个Object数组，一个可变的数组，对于其的所有操作都是通过数组来实现的。

三、ArrayList中的重要参数

// 默认容量，默认10个元素
private static final int DEFAULT_CAPACITY = 10;

// 空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认空对象数组，通过空的构造参数生成的ArrayList实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// ArrayList对象实际上就是一个容器数组
transient Object[] elementData; // non-private to simplify nested class access

// 实际元素大小，默认为0
private int size;

// 最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

四、常用方法

public class ArrayListTest {
    public static void main(String[] args) {
        // 1.new
        List<String> list = new ArrayList<>();

        // 2.add
        list.add("java");
        list.add("python");
        list.add("kotlin");

        // 3.get
        System.out.println("the second element is: " + list.get(1));

        // 4.set
        list.set(1, "c++");

        // 5.遍历
        for (String s : list){
            System.out.println(s);
        }
    }
}

还有remove，indexOf等方法，就不一一列了。

对于循环遍历，有普通的for循环（for ... i这种），增强for循环，迭代器。一般而言，普通for循环效率高些，增强for循环是使用迭代器来实现的，使用更加简单。

五、源码分析

5.1、构造方法

// 1.无参构造
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 2.指定初始容量
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);
    }
}

// 3.传入一个集合，会把集合类型转化为数组类型，并赋值给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;
    }
}

三个构建方法都相对简单，直接看代码应该都能清楚。

5.2、add(E e)

// 添加元素总体可分为两步，一步是容量检测&容量动态增加，另一步是将新的元素添加到数组的末尾
public boolean add(E e) {
    // 1.容量检测&容量动态增加
    ensureCapacityInternal(size + 1);  // Increments modCount!!\
    // 2.将新的元素添加到数组的末尾
    elementData[size++] = e;
    return true;
}

// 调用该方法保证内部容量
private void ensureCapacityInternal(int minCapacity) {
    // 1-1.如果数组容器为空，初始化容器的容量，默认为10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    // 1-2.确保数组长度大于等于最小容量
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    // modCount为操作次数，每次数据结构改变，都会调用该属性modCount++
    modCount++;

    // overflow-conscious code
    // 当容器数组的长度已经满足不了需求的最小容量时，进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //位运算符扩容，容量在当前的基础上+50%
    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
    elementData = Arrays.copyOf(elementData, newCapacity);
}

add方法先要确保数组的容量足够，防止数组已经填满还往里面添加数据造成数组越界：

如果数组容量足够，则直接在数组的末尾添加元素；
如果数组容量不够，则进行扩容，容量为原数组容量的1.5倍，然后将原数组中的元素全部copy到新数组中，接着再往数组末尾添加元素；

也可以发现，如果new了一个无参的ArrayList对象，第一次调用add时会初始化一个容量为10的数组。

5.3、重载的add(int index, E element)

// 在确定索引下新增元素
public void add(int index, E element) {
    // 1.首先要确保该索引要>0并且<=数组长度（index <= size && index > 0）
    rangeCheckForAdd(index);

    // 2.确保数组容量>=size+1
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 3.将index索引位置（包括）及之后的元素都向后挪动一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 4.将index索引处设置为新增元素
    elementData[index] = element;
    size++;
}

因为涉及数组的复制，可以想象如果index后面有大量的元素，所消耗的性能是非常大的。

5.4、set(int index, E element)

public E set(int index, E element) {
    // 1.首先确保索引不能大于数组长度
    rangeCheck(index);
    
    E oldValue = elementData(index);
    // 2.直接替换元素
    elementData[index] = element;
    return oldValue;
}

该方法比较简单。

5.5、get(int index)

public E get(int index) {
    // 1.防止越界，索引不能大于数组长度
    rangeCheck(index);
    
    // 2.直接返回索引处的元素
    return elementData(index);
}

get方法也很简单，直接返回数组索引处得元素。

5.6、remove(int index)

public E remove(int index) {
    // 1.防止越界，索引不能大于数组长度
    rangeCheck(index);

    // 操作数量+1
    modCount++;
    E oldValue = elementData(index);

    // 2.将index后的元素都向前挪动一位，原index的元素就删除了
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 3.数组长度减1
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

可见删除操作也是很耗性能的，因为涉及到了数组的复制。

5.7、重载的remove(Object o)

// 因为Arraylist可以添加null，所以分两种情况，为null和非null
public boolean remove(Object o) {
    // 1.如果删除的元素是null，则遍历删除第一个null
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    // 2.非null，删除第一个equals的元素
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

// 删除，同样是将index后的元素都向前挪动一位
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; // clear to let GC do its work
}

六、疑问解答

6.1、为什么不能在ArrayList的For-Each循环中删除元素？

public class ArrayListForEachTest {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        list.add("f");

        for (String s : list) {
            if (s.equals("b")){
                list.remove(s);
            }
        }
    }
}

除了删除倒数第二个元素外，其它都会报错：

分析一下原因：

因为for-Each删除是基于迭代器。

这里面主要有两个变量在捣鬼，expectedModCount和modCount：

modCount前面介绍过，记录了ArrayList的操作次数，expectedModCount则是期望的操作此时，在其内部类Itr中可以找到。

先看看迭代器的代码，再来分析。

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

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

    @SuppressWarnings("unchecked")
    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];
    }
}

如上，当遍历时，会基于迭代器进行，此时expectedModCount = modCount，在遍历的过程中一直到remove操作，这两个值都一样，但是一旦执行了remove操作，由前面分析remove方法可知，modCount会加1，接着继续执行，会再次调用itr的hasNext（）方法，为true时，调用next方法，该方法会调用checkForComodification方法，这时modCount != expectedModCount，抛出异常。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

但如果是删除倒数第二个元素，删除后，cursor已经等于size-1，而由于已成功删除一个元素，此处的size也是原size()-1，两者相等，所以hasNext返回false，也就不会调用next，所有不会报错。

为什么不能在ArrayList的For-Each循环中删除元素

6.2、ArrayList面试题

了解了以上，相信下面几道面试题应该能解答了。

关于ArrayList的5道面试题

七、ArrayList分析总结

ArrayList底层是一个数组；
对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，如果容量不够，会在原先容量基础上扩容至1.5倍；
在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；
ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间；
常用方法：
get(index)直接读取第几个下标，时间复杂度 O(1)
add(E)添加元素，直接在后面添加，时间复杂度 O(1)
add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，时间复杂度 O(n)
remove（index），remove（E）删除元素，后面的元素需要逐个移动，时间复杂度 O(n)

当操作是大量查询和获取，或需要随机地访问其中的元素时，ArrayList非常适合，如果是向某个位置添加元素或者删除元素，因为涉及数组的复制，ArrayList效率不高。