聊聊ArrayList那些事

ArrayList简介

ArrayList的底层是数组队列，与数组相比，他的容量可以动态增长，也就是常说的动态扩容。下面是它的类图

上面实现了很多接口，代表着具备很多能力，比如，List表明是列表，可以添加，删除，查找。RandomAccess代表可以快速随机访问。Cloneable代表具备拷贝能力，Serializable代表可以进行序列化等等。下面我将会说说它最关键的扩容机制。

ArrayList的扩容机制

注意：以下源码都来自于JDK1.8，所有的解释也是针对这个版本的

我们先看它的几个关键属性

    //默认容量
    private static final int DEFAULT_CAPACITY = 10;
    //存储数据的数组
    transient Object[] elementData;
    //默认空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //list长度，并不是上面数组的长度！！
    private int size;

如果你们有指定初始化时的ArrayList的长度的话，那么这个默认长度就是10。

然后我们看一下调用add方法之后它是怎么扩容的。

public boolean add(E e) {
    //决定是否扩容的方法，JDK11的时候移除掉了，因为它主要是通过创建新数组，然后数据复制的方式进行扩容的
    //这会导致额外的内存分配和数据复制，这比较损耗性能，当然也会产生一些安全问题和兼容性问题，具体的可以自己搜一搜
    ensureCapacityInternal(size + 1); // Increments modCount!!
    elementData[size++] = e;  
    return true;  
}

private void ensureCapacityInternal(int minCapacity) {  
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));  
}

我们先看一下内层方法calculateCapacity是干什么的，然后记住一下传入的参数是minCapacity，是size+1，也就是当前所需要的最小容量 = 原容量+1 （1就是你加入的这个数据）

private static int calculateCapacity(Object[] elementData, int minCapacity) {  
       //如果当前ArrayList里面的数组是一个空数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
        //就返回默认值和所需最小容量的最大值，也就是10或者传入的最小容量
        return Math.max(DEFAULT_CAPACITY, minCapacity);  
    }  
    //如果不是空数组，那么就返回最小容量
    return minCapacity;  
}

从上面的代码中我们发现个问题，就是默认容量DEFAULT_CAPACITY是干啥的？我截几个ArrayList的构造方法图。

第一个无参构造，我们经常用的。

存储数据的数组给了一个默认的空数组。所以我们发现第一件事：默认创建的ArrayList的数组的长度为0

第二个我们看一下指定了长度的构造方法

这个就是如果你指定了长度，那么数组的长度就是你指定的值，如果是0，就默认空数组。而且比较好的时候空数组声明的时候都是static final，也就是不会每次都创建新的空数组。
所以我们发现第二件事：创建一个ArrayList，他的初始长度不一定是10

再回到calculateCapacity，发现第三件事，当你第一次add的时候，同时当前这个数组是个空数组，传入的minCapacity就是0+1=1，他是默认的10取最大的，返回的初始长度就是10，否则就返回minCapacity，那返回这个数是干嘛的？看回调的那个方法ensureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) {  
    //父类中记载变化次数的
    modCount++;  

    // overflow-conscious code  
    if (minCapacity - elementData.length > 0)  
        grow(minCapacity);  
}

有这个判断minCapacity - elementData.length > 0 ==> minCapacity > elementData.length意思就是如果我的所需最小长度大于了你当前数组的长度，那么就需要扩容了,所以我们就发现第四件事：如果你的初始化长度设置的不合理，那么就会频繁的扩容

看到这终于要看到了关键方法grow

private void grow(int minCapacity) {  
    // overflow-conscious code  
    int oldCapacity = elementData.length;  
    //新的容量等于原容量+原容量向右移动1位， = 原容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);  
    //如果新容量小于最小所需容量，那么新容量就等于最小所需容量
    if (newCapacity - minCapacity  0)  
        newCapacity = hugeCapacity(minCapacity);  
    // minCapacity is usually close to size, so this is a win:  
    //然后复制数据到新数组
    elementData = Arrays.copyOf(elementData, newCapacity);  
}

上面的注释已经说明了扩容过程，现在再详细说几个。第一个就是他的扩容量，扩大到原来的1.5倍（奇数会舍弃小数），而且用了位运算，提高了运算效率。第二个就是它的这个比较if (newCapacity - MAX_ARRAY_SIZE > 0) MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，作者的注释是这么说的

要分配的数组的最大大小。一些vm在数组中保留一些头字。 尝试分配较大的数组可能会导致 OutOfMemory错误：请求的数组大小超过了虚拟机限制。还有一个说法是为了自留空间，为了提升数组复制的性能

第三个就是hugeCapacity()，它的情况就是如果计算出的新容量大于数组最大容量的话，那么就进入这个方法重新计算，逻辑如下

private static int hugeCapacity(int minCapacity) {  
    if (minCapacity  MAX_ARRAY_SIZE) ?  
            Integer.MAX_VALUE :  
            MAX_ARRAY_SIZE;  
}

如果当前最小所需容量大于了数组最大容量，那么新容量就是Integer的最大值，否则就返回最大数组容量。
最后调用的Arrays.copyOf方法最后就是一个native调用了。

ArrayList、LinkedList与Vector

LinkedList和他俩的差别很明显，它的实现是一个双向链表，在添加和删除的性能好，但是随机查找就比ArrayList弱了，Vector存储数据也是一个Object[].但是它每次扩容的时候是双倍空间这个是和ArrayList的区别，同时Vector是线程安全的，但是我确实很少用到这个，更多的都是ArrayList，即便面临多线程的情况下也会用CopyOnWriteArrayList

CopyOnWriteArrayList

见名知意，就是写时复制的ArrayList，这个写时复制是啥意思啊，简单来说就是大家访问同一个资源的时候，大家不排斥，随便读，当有个人想改的时候先加个锁，系统会复制一个副本，同时锁能保证只有一个副本，在副本里面改，然后改完再给回去。所以它的缺点就很明显了。

• 每次写操作都需要复制原始数据，很吃内存。
• 每次写都是加锁，然后复制，修改，替换，这个性能会有影响。
• 修改毕竟修改的是副本，所以会造成数据不一致的情况，读到的是你没改的数据。
  我在这里直接放出CopyOnWriteArrayList里面的add方法，看看和ArrayList有啥区别，注意看注释

public boolean add(E e) {  
    final ReentrantLock lock = this.lock;  
    //加锁
    lock.lock();  
    try {  
        Object[] elements = getArray();  
        int len = elements.length;  
        //复制一个新数组，同时数组长度指定了当前长度+1
        Object[] newElements = Arrays.copyOf(elements, len + 1);  
        //数组末尾加上这个数据
        newElements[len] = e;  
        //数组引用换掉
        setArray(newElements);  
        return true;  
    } finally {  
        //释放锁
        lock.unlock();  
    }  
}

主要就是加了锁，避免复制多个副本，然后它不是ArrayList那种扩成1.5倍，所以它的size方法就可以就
getArray().length来获取了。

扩展--为什么存储数据的数组elementData用transient声明

我们上面扩容机制中说了，ArrayList会预留空间，而这些空间在数据中其实都没有数据，如果不声明transient，那么序列化的时候就会序列化一些null元素，所以就声明了transient，于此同时，为了完成序列化，ArrayList就重写了writeObject和readObject方法，我们看一下writeObject方法吧

private void writeObject(java.io.ObjectOutputStream s)

throws java.io.IOException{

// Write out element count, and any hidden stuff

int expectedModCount = modCount;

s.defaultWriteObject();  

// Write out size as capacity for behavioural compatibility with clone()

s.writeInt(size);  
// Write out all elements in the proper order.

//循环了size，然后序列化的

for (int i=0; i