高薪程序员&面试题精讲系列32之说说ArrayList的底层原理及扩容机制

一. 面试题及剖析

1. 今日面试题

说一下ArrayList的底层原理？

ArrayList怎么进行扩容？

......

2. 题目剖析

在上一篇面试文章中，壹哥 就跟大家说过，集合相关的面试题，是咱们Java程序员出去面试时的高频问题，可以说任何一个常用的集合都可能会被面试官翻来覆去的提问，就比如今天关于List的内容。List集合中最常用的肯定是ArrayList，其次就是linkedList，所以面试官动不动就会问两者的各自特点，两者的区别，这道题目可以说100个Java程序员里面得有70个会被问到。

虽然关于List的题目比较常问，但难度其实并不很大，与HashMap的难度比起来小得多。所以咱们先由易入难，请大家跟着 壹哥 一点点剖析这些常用的集合，咱们争取在面试时，大家对集合这一块的内容都可以做到手拿把掐。

二. List集合

1. List简介

壹哥 在上一篇文章中就跟大家讲过，List是一个有序列表接口，内部允许存放重复的元素，且允许存放null空值。List中所有元素都会以线性方式进行存储，我们可以通过索引来访问集合中指定的元素，所以List集合中元素的存储顺序和取出顺序是一致的。

2. List子类

从类关系上来说，List是Collection的子接口，它与其他类的关系如下图所示：

从上图中可知，List有多个子类，但是该接口的常用子类有3个，如下：

• ArrayList：最常用的List子类，底层基于 数组实现，查询快，增删慢，轻量级，但是线程不安全。
• linkedList：底层基于 双向链表实现，增删快，查询慢，也是线程不安全。

• Vector：底层基于 数组实现，重量级，线程安全，但目前使用较少。

3. List常用方法

因为List继承自Collection接口，所以就继承了Collection中的全部方法，另外还增加了一些根据元素的位置索引来操作集合的特有方法。

• void add(int index, Object element)：添加对象element到位置index上；
• boolean addAll(int index, Collection collection)：在index位置后添加容器collection中所有的元素；
• Object get(int index)：取出下标为index的位置的元素；
• int indexOf(Object element)：查找对象element 在List中第一次出现的位置；
• int lastIndexOf(Object element): 查找对象element 在List中最后出现的位置；
• Object remove(int index)：删除index位置上的元素；
• ListIterator listIterator(int startIndex)：返回一个ListIterator 跌代器，开始位置为startIndex；
• List subList(int fromIndex, int toIndex): 返回一个子列表List，元素存放为从 fromIndex 到toIndex之前的一个元素。

三. ArrayList集合(重点)

1. ArrayList简介

ArrayList是List接口的一个实现类，它是我们程序开发中最常见的一种集合类。ArrayList集合类的大部分方法都是从父类Collection和List继承过来的，其中add()方法和get()方法用于实现元素的添加和读取。

2. ArrayList用法(略)

因为 壹哥 给大家讲解的是ArrayList相关面试题，既然大家关注本文，说明各位已经进入到了求职阶段，相信你对基本的用法已经有所掌握，这里不对基本用法再做细讲。

我们面试时，面试官基本不会问我们List怎么用，更多的是问我们对这些集合底层、源码、原理的掌握情况。所以接下来 壹哥 带各位看一下ArrayList的源码，从中分析其底层的运行原理。

3. ArrayList基本原理(重点)

ArrayList在其内部封装了一个可增长的动态数组Object[]来保存数据，初始长度缺省为10。当我们存入的元素超过数组长度时，ArrayList会在内存中分配一个更大的数组来重新容纳这些元素，因此可以将ArrayList集合看作一个长度可变的数组。

ArrayList集合与数组操作一样，索引的取值范围是从0开始，到size-1为止(size是集合的长度)，不能超出此范围，否则会引发异常。add(Objecto)方法会把元素添加到集合的尾部，而add(intindex, Object o)则会把元素添加到索引index指定的位置。

在删除元素时，会将被删除元素之后的元素都向前移一个位置以填补空位。

而在用add(intindex, Object element)方法添加元素时，则是把元素插入到index指向的位置，先把该位置的元素以及后续元素都向后移一个位置。这时如果超出数组的容量，会创建更大的新数组，调用System.arraycopy()进行数据的拷贝。因为增删元素会导致大量的内存操作，所以效率低，但ArrayList允许通过索引随机的访问元素，所以查询效率高。

4. ArrayList的存储容量(重点)

当我们创建一个ArrayList集合时，我们应该想一下，为什么这个集合可以存储任意类型的数据元素？这个集合的存储容量到底有多大？它能不能把我们的数据元素都给添加进去？万一存储容量不够大怎么办？这些问题，都需要我们通过查看源码才能得知。

4.1 编写实验代码

为了知道ArrayList的存储容量有多大，我们先编写下面两行代码：

public static void main(String[] args){
    ArrayList list=new ArrayList<>();
    //list.add("一一哥");
}

4.2 初始容量

在上面的代码中，壹哥 创建通过无参的构造方法，构造了一个ArrayList对象，我们由此进入到源码中查看一下。注意，一开始我把list.add添加元素的方法注释掉了。此时通过端点调试，我们观察list集合的初始大小，可以很明显的看出，在利用无参构造方法创建ArrayList对象，且没有添加任何一个数据时，list对象的初始大小就是0！！！

那么为什么是这样的呢？我们进入到源码中看看。

4.3 ArrayList()构造方法源码

此时我们进入到ArrayList()这个无参的构造方法中来，可以看到内部只有一行代码，代码中涉及到两个对象：elementData与DEFAULTCAPACITY_EMPTY_ELEMENTDATA。另外请各位注意，这段源码上面有一行注释，相信各位可以看懂，意思就是“构造一个初始化容量为10的空集合”。

我们先来看看elementData与DEFAULTCAPACITY_EMPTY_ELEMENTDATA分别是什么。

从这段源码中，我们可以看到，elementData其实就是一个Object[]数组，而且不支持对该字段进行持久化。由此我们就知道了为什么ArrayList内部可以存储任意类型的数据元素了。而且从注释中可知，elementData是作为ArrayList存储元素的缓冲数组存在的，ArrayList的为扩容之前的容量大小就是这个缓冲数组的长度。最关键的是，任何一个空ArrayList会在我们往该集合中添加第一个元素时才会进行扩容，第一次扩容大小是基于DEFAULT_CAPACITY这个值，也就是10！

我们再来看看DEFAULTCAPACITY_EMPTY_ELEMENTDATA，会发现它也是一个Object[]，而且该数组也是在第一个数据元素被添加进来时进行扩容。

接下来我把实验代码中的注释给放开，也就是此时代码如下：

public static void main(String[] args){
    ArrayList list=new ArrayList<>();
    list.add("一一哥");
}

往list空集合中添加一个数据元素，此时我们再来看看ArrayList集合的容量大小，如下图所示：

这时我们发现，list的size大小是1，但是elementData这个Object[]数组的容量已经变成了10！而且刚才上面已经说过，elementData是一个缓存数组，它的大小会与ArrayList的容量大小有关系，也就是说ArrayList的扩容就会受elementData数组大小的影响。那么为什么现在elementData数组的长度变成了10？ArrayList到底是怎么进行扩容的？请跟着 壹哥 继续往下走。

5. ArrayList的扩容机制(重点)

5.1 add()方法源码

从上面的的源码分析中我们可以知道，一个空list是在第一次执行完add()添加方法之后将elementData数组赋值为10的，所以list的扩容机制应该与add()方法有关系。既然如此，我们就先来看看add()方法的源码。

public boolean add(E e) {
    //集合扩容方法，确保容量一致，并递增modCount值
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //将元素e添加到elementData数组的size++位置上
    elementData[size++] = e;
    return true;
}

从add()方法的源码中，我们会发现其实添加方法的实现是比较简单的。ensureCapacityInternal()方法用于进行扩容，elementData[size++]则负责往缓冲数组中添加元素。其中size表示list集合中元素的实际数量，在未添加数据时size=0，添加了一个数据元素后size就等于1，且以后每添加一个数据，这个size值就会加1。也就是说在添加了第1个数据之后，minCapacity的值也等于1了。

5.2 ensureCapacityInternal(minCapacity)方法源码(重点)

• 现在我们往list集合中添加了第1个数据元素，mincapacity = 1，因为elsementData是一个Object[]数组，DEFAULTCAPACITY_EMPTY_ELEMENTDATA也是一个Object[]数组，所以在添加第1个数据元素后，calculateCapacity()方法中if判断的表达式结果为true。所以接着就会进入到if语句中，进而执行Math.max(DEFAULT_CAPACITY, minCapacity)方法。
• 我们在学习Java基础时就知道，Math.max(DEFAULT_CAPACITY, minCapacity)用于在两个数值之间取出最大值。DEFAULT_CAPACITY是ArrayList的默认大小10，而现在minCapacity = 1，所以结果不言而喻，Math.max的结果现在等于10。
• 然后这个10会被传递给形参minCapacity，接着进入到ensureExplicitCapacity()方法中，minCapacity=10，在未添加任何数据之前，elementData.length=0，所以可以进入到if()判断内部，调用grow()方法执行改变elementData的长度值。这里 壹哥 绘制了下图，大家可以参考理解。

另外这里modCount++主要是用于ArrayList的快速失败机制，其和扩容没关系，我们不做研究。

5.3 grow()方法源码

接下来我们看看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);
    }

首先我们可以从grow()方法的注释中可知，grow()方法用于递增capacity的值，以确保ArrayList可以有足够的空间来存储数据元素。那具体是怎么实现递增和扩容的呢？别急，请继续往下看。

5.4 扩容步骤详解(重点)

在grow()的源码中，在list添加第1个数据元素之前，minCapacity = 10，elementData.length=0，我们先分析第1个数据元素被添加到list集合后的变化过程，如下：

5.4.1 第1行代码进行赋值操作：

//oldCapacity== 0
int oldCapacity = elementData.length; 

因为在未添加数据元素之前，elementData.length=0，所以oldCapacity=0；

5.4.2 第2行代码向右位移运算后再进行赋值操作：

// newCapacity = 0 + 0/2 = 0
int newCapacity = oldCapacity + (oldCapacity >> 1);

我们知道，向右位移等同于数字除以2，所以 oldCapacity >> 1 的结果，就等于 oldCapacity/2，所以最终newCapacity的结果还是等于0。

5.4.3 第3行代码进行判断：

if (newCapacity - minCapacity < 0)
    //newCapacity=10
    newCapacity = minCapacity;

因为此时newCapacity=0，minCapacity=10，所以结果你懂得，newCapacity - minCapacity < 0，接着进入到第一个if()语句内部，所以这时newCapacity=10。

5.4.4 第4行代码判断ArrayList集合有没有超过最大范围：

if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);

这段代码就是判断ArrayList的容量newCapacity有没有超过限定的最大范围MAX_ARRAY_SIZE，MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8，这个值非常大，所以我们现在不关心它会不会超限。

5.4.5 第5行代码，进行数组copy操作：

elementData = Arrays.copyOf(elementData, newCapacity);

利用这段代码，就会把缓存数组elementData里的数据元素，复制到一个长度为newCapacity的新数组中，所以当我们往list集合中添加了第1个数据元素后，ArrayList中elementData[]的length就等于10了，但是size还是等于1。

这样，当第1个数据元素被添加到list集合后，elementData.length就等于10了！但是大家注意，这里其实还不是ArrayList的扩容，这只是把elementData数组的长度从0改成了10而已，真正的扩容是指当这个容量10不够用了，会在10的空间基础上进行增加。

5.4.6  所以接下来，如果ArrayList集合中已经有了10个数据元素，我们再想往该集合中添加一个新的元素，该集合会继续按照上述步骤进行扩容操作，接下来才是真正的第1次扩容，这里我的分析步骤如下：

// oldCapacity == 10
int oldCapacity = elementData.length;

// newCapacity = 10 + 10/2 = 15
int newCapacity = oldCapacity + (oldCapacity >> 1); oldCapacity >> 1 = 5
    
// 15 - 10 >0，所以if判断进不来，直接执行Arrays.copyOf()代码去   
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
	......
    ......
elementData = Arrays.copyOf(elementData, newCapacity);  

上述各种计算和判断过后，会接着执行Arrays.copyOf()，并设置这个集合的容量newCapacity为15，这样就完成了第一次扩容。所以ArrayList每次扩容都是原来得1.5倍，而且数组进行扩容时，会将旧数组中的元素重新拷贝一份到新数组中。以后每当ArrayList集合需要扩容时，就会按照这个步骤进行扩容，这就是ArrayList的扩容机制。

最后 壹哥 把扩容机制再给大家简单梳理总结一下。

每个ArrayList实例都有一个存储容量，该容量是指存储列表元素的elementData数组的大小，不是指集合size的大小。该容量至少等于会列表数组的大小，且会随着ArrayList不断的添加元素，其容量值也在自动增长，并会将原来数组的元素向新数组进行copy。为了提高集合性能，如果我们可以提前预判数据量的大小，请尽量在构造ArrayList时指定其容量大小。

至此，壹哥 就给大家讲清楚了ArrayList的底层原理及其扩容机制，下一篇我会给大家继续讲解linkedList的底层原理，欢迎继续关注哦！