面试官问：你看过ArrayList源码吗？一文带你深入ArrayList底层源码

亦凉 2023-07-03 04:47 32阅读 0赞

ArrayList是Java非常重要的集合类，相信大家对它并不陌生。List和Map号称是Java最常用、使用最广泛的集合类，比如，我们从数据库获取多个数据的时候，都是返回List集合，我还没见过返回过Set集合；所以相比之下，Set集合使用的场景就非常少。不过这篇博客主要讲解ArrayList面试题及源码分析，未涉及到Set集合、Map集合。

`在认识ArrayList之前，我们先回顾一下数组，因为Arrayist底层是基于变长数组实现的。`

# 数组 #

数组是基于线性数据结构实现的，在Java中创建数组时，会在内存中划分出一块连续的内存空间，然后再根据数组长度划分成跟数组长度一样的一小块内存空间。

我们来画个图简单描述一下,`下面图中创建了字符串数组，定义它的长度为5，所以就会在内存中创建一大块连续的内存，然后再分成5小块内存(等分)，并且该数组中的元素都有默认值：null。`  
![在这里插入图片描述][20200202131301495.png]  
基本所有的数组面试题，都会有一个说法：就是`数组的特点是，查询修改快，增加删除慢`。  
我们还知道在数组中有索引这个概念，`当数组内存空间分配好了之后，会为每个元素分配一个索引，从0开始，直到数组长度-1`。索引非常重要，因为数组的增删改查都是基于索引实现的。  
![在这里插入图片描述][20200202135102985.png]  
`如果我们想查询的时候，直接根据索引来查询`  
string\[0\];  
`如果我们想修改的时候，也是根据索引来修改`  
string\[0\] = “java”;

**因为查询和修改不需要改变数组的长度，所以速度非常快。**

**如果我们对数组添加元素或删除元素，就会改变数组的长度，需要花一定的时间才能完成，所以速度会很慢。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ_size_16_color_FFFFFF_t_70]  
我们通过图来说明了为什么数组是查询修改快，增加删除慢。数组的讲解就完了，接下来我们就开始ArrayList的里程了。

# ArrayList是什么 #

1.  ArrayList是一种变长的集合类，底层基于变长数组实现，所以ArrayList可以保证在O(1)时间复杂度下完成查询操作。
2.  ArrayList允许空值和重复元素，当往ArrayList中添加的元素数量大于其底层数组容量时，就会通过扩容机制重新生成一个更大的数组。
3.  ArrayList是线程不安全的类，在并发环境下，多个线程同时操作ArrayList，会引发不可预知的错误或异常。

# ArrayList的成员变量 #

了解并弄懂ArrayList的成员变量对我们阅读AraayList源码是非常有帮助的，我们先总览一下ArrayList的成员变量，然后再一个个讲解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ_size_16_color_FFFFFF_t_70 1]  
默认初始化容量为10。

/** * Default initial capacity. */
    private static final int DEFAULT_CAPACITY = 10;

定义一个空元素数组。

/** * Shared empty array instance used for empty instances. */
    private static final Object[] EMPTY_ELEMENTDATA = { };

定义一个默认容量为10的数组。哎，这不也是空数组吗，怎么说是长度为10？因为arraylist默认在添加第一个元素的时候才初始化长度为10。

/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };

真正存储ArrayList集合的元素就是这个数组。因为ArrayList底层存储数据就是通过数组的形式，ArrayList长度就是数组的长度。一个空的实例elementData为上面的DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，当添加第一个元素的时候会进行扩容，扩容大小就是上面的默认容量DEFAULT\_CAPACITY。

/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */
    transient Object[] elementData; // non-private to simplify nested class access

这个int变量是arraylist实际的长度，size()方法也是通过获取它才知道ArrayList的长度。

/** * The size of the ArrayList (the number of elements it contains). * * @serial */
    private int size;

# ArrayList的构造方法 #

知道ArrayList的成员变量之后，我们就开始了解它的构造方法，ArrayList的构造方法不多，只有三个。  
![在这里插入图片描述][2020020216565065.png]

#### 空参构造方法 ####

构造方法中将elementData初始化为空数组DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，当调用add方法添加第一个元素的时候，才会进行扩容，扩容至大小为DEFAULT\_CAPACITY=10。

public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

#### 指定容量大小的构造方法 ####

这个构造方法是让我们创建ArrayList的时候指定其容量大小，分为3种情况：

1.  参数大于0：elementData初始化为initialCapacity大小的数组。
2.  参数等于0：elementData初始化为空数组。
3.  小于0：抛异常。

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);
        }
    }

#### 参数为Collection类型的构造方法 ####

这个构造方法将一个Collection集合转为ArrayList集合，如果传入的Collectiion集合为null，就会报空指针异常(c.toArray())。

public ArrayList(Collection<? extends E> c) { 
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            if (elementData.getClass() != Object[].class)
            	//c.toArray()可能不会正确地返回一个Object[]数组，那么使用Arrays.copyOf()方法
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            //如果集合转换为数组之后数组长度为0，就直接使用数组初始化elementData
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

我们将ArrayList集合的成员变量和构造方法介绍完了，它们主要是规定ArrayList是使用默认初始容量，还是自己定义初始容量。  
我们还说过使用空参构造方法的时候，在第一次add的时候，会进行扩容，那我们来看看add方法以及扩容的细节。

#### ArrayList的add方法 ####

add方法是将元素添加到arraylist的末尾。在add方法中，调用了ensureCapacityInternal方法，在这个方法中初始化arraylist的默认容量，并且判断要不要扩容。

public boolean add(E e) { 
    	//因为是添加元素，可能导致容量不够用，所以需要判断要不要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

#### ensureCapacityInternal方法解析 ####

首先判断elementData数组是不是为空数组，如果使用的是空参构造方法并且是第一次添加的时候，那么minCapacity = size+1 = 1，然后比较minCapacity和DEFAULT\_CAPACITY的大小，很明显是DEFAULT\_CAPACITY大，所以第一次添加的时候就初始化默认容量为10。然后调用ensureExplicitCapacity方法，这个方法才是判断要不要扩容。

private void ensureCapacityInternal(int minCapacity) { 
    
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity(minCapacity);
    }

#### ensureCapacityInternal方法解析 ####

这个方法就是判断需不需要进行扩容操作。当`minCapacity - elementData.length > 0`成立时，说明即将添加的元素索引已经大于数组的长度了，需要进行扩容，而grow方法就是执行扩容操作。

private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

#### grow方法解析 ####

1.  oldCapacity为旧数组的容量
2.  newCapacity为新数组的容量，`oldCapacity + (oldCapacity >> 1)`：即新容量为旧容量的1.5倍
3.  判断新容量是否小于最小需要容量，如果小于那就将最小容量最为数组的新容量
4.  判断新容量是否大于MAX\_ARRAY\_SIZE，如果大于，则通过hugeCapacity方法比较minCapacity与MAX\_ARRAY\_SIZE的大小
5.  扩容并拷贝原数组中的元素

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);
    }

#### hugeCapacity方法解析 ####

这个方法只是判断minCapacity与MAX\_ARRAY\_SIZE的大小。

1.  如果是minCapacity，那么将Integer.MAX\_VALUE作为新数组的大小
2.  如果是MAX\_ARRAY\_SIZE，那么将MAX\_ARRAY\_SIZE作为新数组的大小，`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;
    }

#### add方法执行流程总结 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ_size_16_color_FFFFFF_t_70 2]  
`上面的执行流程是指通过空参构造方法创建ArrayList，并添加第一个元素时。添加第一个元素之后，arraylist容量就变为10了。`

1.  当添加第二个元素时，调用ensureCapacityInternal方法并传递参数2(size+1=2)。
2.  在ensureCapacityInternal方法中，elementData ==DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA不成立，所以直接执行ensureExplicitCapacity方法。
3.  ensureExplicitCapacity方法中minCapacity为刚刚传递的2，所以if判断不会成立，则不会进入 grow 方法。
4.  假设又添加3、4…10个元素(其中过程类似，但是不会执行grow扩容方法)。
5.  当add第11个元素时候，会进入grow方法，计算得到newCapacity为15，比minCapacity（为10+1=11）大，第一个if判断不成立。新容量没有大于MAX\_ARRAY\_SIZE ，不会进入hugeCapacity方法。最后数组容量扩为15。  
    **以上就是对添加第二个元素以及多个元素时的流程解析，这样，我们就对add方法了解透彻了，也对ArrayList的扩容机制非常清楚了。**

接下来我们对ArrayList另一个add方法进行解析.

#### ArrayList的add(int index, E element)方法 ####

这个添加方法是在指定索引位置添加元素。

1.  首先调用`rangeCheckForAdd方法`判断指定的索引是否越界，越界就报IndexOutOfBoundsException异常。
2.  不越界，就调用`ensureCapacityInternal方法`判断是否需要扩容，之后调用`System.arraycopy方法`将index及其之后的所有元素都向后移一位。
3.  最后将新元素插入到index位置。

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++;
    }

#### rangeCheckForAdd方法 ####

这个方法主要是判断指定的索引是否在数组长度范围内。

private void rangeCheckForAdd(int index) { 
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

`介绍完添加方法之后，我们接下来对获取方法进行解析。`

#### ArrayList的get(int index)方法 ####

在get方法中，通过index获取元素。

1.  首先调用rangeCheck方法判断index是否合法，不合法就报IndexOutOfBoundsException异常。
2.  合法，就调用elementData方法返回index处的元素。

public E get(int index) { 
        rangeCheck(index);
    
        return elementData(index);
    }

#### rangeCheck方法 ####

private void rangeCheck(int index) { 
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

#### elementData方法 ####

直接通过index获取数组元素，时间复杂度为O(1)。

E elementData(int index) { 
        return (E) elementData[index];
    }

`介绍完获取方法之后，我们接下来对删除方法进行解析。`ArrayList支持两种删除元素的方式。

#### remove(int index)方法 ####

这个方法是按索引删除。

1.  调用remove方法判断索引index是否合法，不合法，抛异常。
2.  合法，就根据index获取数组元素`E oldValue = elementData(index);`。
3.  计算需要向左移动元素的个数，`int numMoved = size - index - 1;`，因为我们删除了数组的元素，需要把后面的元素依次向左移，这样才会保证数组的连续性。
4.  如果numMoved大于0，说明需要向左移动元素；如果等于0，说明是最后一个元素，不需要移动。需要移动元素则调用`System.arraycopy方法`。
5.  将原数组的最后一个元素赋值为null，当垃圾回收器工作的时候会清理掉它。

public E remove(int index) { 
        rangeCheck(index);
    
        modCount++; //只要是对ArrayList进行增删改查，就需要更新这个值。
        E oldValue = elementData(index);
    
        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
    
        return oldValue;
    }

#### remove(Object o)方法 ####

根据元素删除，会删除和参数匹配的第一个元素。

1.  如果参数为null，则遍历存储元素的数组，找到第一个为null的元素index，然后调用fastRemove方法根据索引删除。
2.  如果参数不为null，也遍历存储元素的数组，也是找到第一个跟参数匹配的元素索引，然后调用fastRemove方法根据索引删除。

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;
    }

#### fastRemove方法 ####

这个方法主要是根据索引删除索引处的元素。原理跟上面的`remove(int 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
    }

`介绍完删除方法，我们接下来介绍修改方法`

#### set(int index, E element)方法 ####

这个方法是根据index修改index处元素的值。

1.  首先判断index是否合法，不合法，报异常。
2.  合法，则根据index查询元素，最后把index处的元素替换为新元素，并返回旧元素。

public E set(int index, E element) { 
        rangeCheck(index);
    
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

`最后我们来介绍size()，也就是获取ArrayList长度的方法。`

#### size()方法 ####

这个方法直接返回size变量，我们知道在添加元素的时候，会size++。而删除元素的时候，会–size。

public int size() { 
        return size;
    }

private int size;

[20200202131301495.png]: https://img-blog.csdnimg.cn/20200202131301495.png
[20200202135102985.png]: https://img-blog.csdnimg.cn/20200202135102985.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200202141611990.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200202164022469.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ==,size_16,color_FFFFFF,t_70
[2020020216565065.png]: https://img-blog.csdnimg.cn/2020020216565065.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200203194447484.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE3NjE2OQ==,size_16,color_FFFFFF,t_70