集合框架 -------- ArrayList源码分析

一、简介

这篇文章主要介绍一下ArrayList的相关细节，它的底层是基于数组实现的，数组是在内存中划分出一块连续的地址空间用来进行元素的存储，它存在一个致命的缺陷，就是在初始化时必须要指定大小，并且不能改变，而ArrayList则解决了这个问题，实现了一个动态的数组（自动扩容机制），与此同时，它也具备了数组的一些特性：查询快，增删慢。下面我们来看一下类图：

ArrayList继承结构

• Serializable接口：类实现此接口以启用其序列化功能。可序列化类的所有子类型本身都是可序列化的。序列化接口没有方法或字段，仅用于标识可序列化的语义。
• Cloneable接口：类实现了 Cloneable 接口，以指示Object.clone()方法可以合法地对该类实例进行按字段复制。按照惯例，实现此接口的类应该使用公共方法重写 Object.clone（它是受保护的）。
• List接口：定义了一个有序、可重复的集合（也称序列）。
• RandomAccess：用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

二、底层实现

先来看一下它的几个字段，可以发现它的内部维护了一个Object数组用于存储元素，也就是说它可以存储任何类型的元素（最好使用泛型约束存储的类型），当创建一个新的实例时，可以指定初始大小，若不指定则不会分配内存空间而是使用空的对象数组，在添加第一个元素时再进行内存分配。

//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量空对象数组（即添加第一个元素时会自动扩容至默认容量）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储ArrayList的元素，它的大小即size大小
transient Object[] elementData;
//此集合的大小（即集合中元素的数量）
private int size;
//集合最大长度，若依然不够会进一步扩容到Integer.MAX_VALUE
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

接下来我们再来看一下它的增删改查方法，emmm。。。基于数组的操作，也没什么可写的。

//在末尾增加一个元素
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);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}
//移除此列表中首次出现的指定元素（如果存在）。
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;
}
//用指定的元素替代此列表中指定位置上的元素。
public E set(int index, E element) {
    //下标合法性检查 
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
//获得指定位置元素
public E get(int index) {
    //下标合法性检查
    rangeCheck(index);
    return elementData(index);
}

扩容机制及本人的思考

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //扩容为原长度的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //扩容后的长度若大于MAX_ARRAY_SIZE，进一步扩容到Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

从源码中可以看到，ArrayList的最大长度为Integer.MAX_VALUE - 8，而数组对象相比标准java对象多了一个用于存储大小的元数据，即 2^31 -8 (for storing size )，若试图分配更大空间可能会导致OutOfMemoryError，下面贴出源码注释：

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

虽然注释上是这么说的，但是仔细看源码还有这么一行：

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

当MAX_ARRAY_SIZE长度的集合也不足够的时候，则会扩容至Integer.MAX_VALUE，那么问题来了，这样操作占用了本用来存储header words的空间，按注释所言可能会报OutOfMemoryError，那这里又是如何处理的呢？？？

三、总结

又到了文章的最后，我们来总结一下ArrayList的特点：

• 增删慢，查询快（增删会导致后续数据移位）
• 不是线程安全的
• 默认初始容量为10，每次扩容为原大小的1.5倍，在初始化时需要指定合适大小，避免频繁扩容导致的性能损耗
• 最大大小为Integer.MAX_VALUE