全面解析ArrayList，超详细！

红太狼 2022-12-20 02:10 138阅读 0赞

**写在前面：**

> 小伙伴儿们，大家好！上一篇我们介绍了HashMap相关知识点——[了解HashMap数据结构，超详细！][HashMap]
> 
> 今天来学习ArrayList相关内容，作为面试必问的知识点，来深入了解一波！

**思维导图：**

![78dc08d71e73c6ecbb3c497c2ee807bb.png][]

ArrayList学习图

## 1，ArrayList底层数据结构 ##

`ArrayList`就是动态数组，是`List`接口的可调整大小的数组实现；除了实现`List`接口之外，该类还提供了一些方法来操纵内部使用的存储列表的数组大小。它的主要底层实现是**数组**`Object[] elementData`。

数组的特点大家都知道，遍历**查询速度快**——数组在内存是连续空间，可以根据地址+索引的方式快速获取对应位置上的元素。但是它的**增删速度慢**——每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。

![18263565c43656805bcd45ae92eff0f1.png][]

ArrayList类架构图

`ArrayList` 是 java 集合框架中比较常用的数据结构了。继承自 `AbstractList `，实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 `RandomAccess`、`Cloneable`、`Serializable` 接口，所以`ArrayList` 是支持快速访问、复制、序列化的。

与`ArrayList`类似的是`LinkedList`，但是`LinkedList`底层是**链表**，它的数组遍历速度慢，但增删速度很快。

**小结：**

`ArrayList`底层是**数组**实现的存储，查询效率高，增删效率低。

## 2，ArrayList构造方法 ##

下面是查看API中构造方法

![878a3611c8d99425a7b193c3fdc423ff.png][]

构造方法

### 2.1，无参构造方法 ###

我们看源码中的无参构造方法：

> 无参构造，使用默认的size为10的空数组，在构造方法中没有对数组长度进行设置，会在后续调用add方法的时候进行扩容。

![bdd6dc47b96234be5a5a99774cbf6b11.png][]

无参构造

里面是一个赋值操作，右边是一个空容量数组，左边则是存储数据的容器，以下是参照源码分析；

//默认空容量数组，长度为0
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    //集合真正存储数据的容器
    transient Object[] elementData;

### 2.2，参数为指定初始化容量的构造方法 ###

来看看源码中的int型构造方法：

![2f7cd06ac68354b3fe489d5fe5480c45.png][]

指定初始化容量构造

> 参数大于0，`elementData`初始化为`initialCapacity`大小的数组；参数等于0，`elementData`初始化为空数组；参数小于0，抛出异常；

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

来看看构造方法的源码：

![bdca89d4876c29f8aa0dafb4670341ba.png][]

Collection类型构造

> 将一个参数为Collection的集合转变为`ArrayList`(实际上就是将集合中的元素换为了数组的形式)；如果传入的集合为null会抛出空指针异常。`c.toArray()`可能不会正确地返回一个 `Object[]`数组，那么使用`Arrays.copyof()`方法。如果集合转换成数组之后数组长度为0，那就直接使用自己的空成员变量初始化`elementData`。

**总结：**

上面的构造方法理解起来比较简单，无参构造和初始化容量构造的目的都是初始化底层数组`elementData(this.elementData=XXX)`；

> 无参构造方法会将`elementData`初始化一个空数组，插入元素时，扩容将会按默认值重新初始化数组；有参构造方法会将`elementData`初始化为参数值大小（>=0）的数组；

如果在构造 `ArrayList` 实例时，指定初始化值（初始化容量或者集合），那么就会创建指定大小的 `Object` 数组，并把该数组对象的引用赋值给 `elementData`；如果不指定初始化值，在第一次添加元素值时会使用默认的容量大小 10 作为 `elementData` 数组的初始容量，使用 `Arrays.conpyOf()` 方法创建一个 `Object[10]` 数组。

一般情况下，我们用默认的构造方法即可。上面说到使用无参构造时会调用`add`方法并进行扩容，下面来看看`add`方法以及扩容的细节。

## 3，添加add()方法分析 ##

看看`ArrayList`的`add()`添加方法：

![5183e9736372c72cccc6ee434cd59f5e.png][]

add()添加方法

### 3.1，列表的末尾添加指定元素 ###

public boolean add(E e)

先来看看源码分析

![10d463a48e0476ea76ce2de6069ae4ed.png][]

add()源码

我们先来看第一个添加方法add(E e)，具体流程如下：

//将添加的数据传入给e 
    public boolean add(E e) { 
        //调用方法对内部容量进行校验 
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e; 
        return true; 
    }

我们看到add方法中在添加元素之前，会先判断size的大小，所以我们来看看`ensureCapacityInternal`方法的细节之处

private void ensureCapacityInternal(int minCapacity) { 
            //判断集合存数据的数组是否等于空容量的数组 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            //通过最小容量和默认容量 出较大值 (用于第一次扩容) 
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 
            } 
            //将if中计算出来的容量传递给下一个方法,继续校验 
            ensureExplicitCapacity(minCapacity); 
        }

当 要 add 进第1个元素时，`minCapacity`为(size+1=0+1=)1，在`Math.max()`方法比较后，`minCapacity` 为10。然后紧接着调用`ensureExplicitCapacity`更新`modCount`的值，并判断是否需要扩容。接下来看`ensureExplicitCapacity`方法

private void ensureExplicitCapacity(int minCapacity) { 
            //实际修改集合次数++ (在扩容的过程中没用,主要是用于迭代器中) 
            modCount++; 
            //判断最小容量    - 数组长度是否大于    0 
            if (minCapacity - elementData.length > 0) 
            //将第一次计算出来的容量传递给    核心扩容方法 
            grow(minCapacity); 
        }

然后是扩容的核心\*\*grow()\*\*方法：

private void grow(int minCapacity) { 
            //记录数组的实际长度,此时由于木有存储元素,长度为0 
            int oldCapacity = elementData.length; 
            //核心扩容算法   原容量的1.5倍 
            int newCapacity = oldCapacity + (oldCapacity >> 1); 
            //判断新容量-最小容量是否小于0, 如果是第一次调用add方法必然小于
            if (newCapacity - minCapacity < 0) 
            //还是将最小容量赋值给新容量 
            newCapacity = minCapacity; 
            //判断新容量-最大数组大小是否>0,如果条件满足就计算出一个超大容量
            if (newCapacity - MAX_ARRAY_SIZE > 0) 
            newCapacity = hugeCapacity(minCapacity); 
            // 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给
            elementData elementData = Arrays.copyOf(elementData, newCapacity); 
    }

执行流程：

![53b9c669ff8269333eadb59ac003fbda.png][]

### 3.2，指定位置添加指定元素 ###

public void add(int index, E element)

**先来看看源码分析**

//在元素序列index位置处插入
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //1，检测是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //2，将index及其之后的元素都向后移一位
        System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
        // 3. 将新元素插入至 index 处
        elementData[index] = element;
        size++;
    }
    private void rangeCheckForAdd(int index) {
        //这里判断的index>size，index小于0，超出指定范围就报错
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

我们再看看它的使用方法：

import java.util.ArrayList;
    
    /**
     * @author 公众号:程序员的时光
     * @create 2020-11-03 17:05
     * @description
     */
    public class Test03 {
        public static void main(String[] args) {
            ArrayList<String> list=new ArrayList<>();
            list.add("海心焰");
            //在index为1的位置处添加数据
            list.add(1,"玄黄炎");
            System.out.println(list);
        }
    }

运行结果：

![bf206dcca9134dd2737b581c92ec9bf7.png][]

结果

### 3.3，按照指定的元素顺序，将所有元素添加到此列表的尾部 ###

public boolean addAll(Collection<? extends E> c);

这个方法的描述是，按指定集合的Iterator返回的顺序将指定集合中的所有元素**追加**到此列表的末尾。

简单来讲，就是**将一个集合的元素全部添加到另外一个集合中去**。

![016e83b6d72c8c163f15353c926e76b4.png][]

代码

运行结果：

![a7d9de1fb15c96fd806457d2d987cef2.png][]

结果

### 3.4，将指定集合中的所有元素插入到此列表中，从指定位置开始 ###

public boolean addAll(int index, Collection<? extends E> c);

这个方法和上面的方法都是**把一个集合中的元素**添加到**另外一个集合中去**，不同的在于上面的方法是**默认添加至目标集合的尾部**，而此方法是包含索引的，也就是**在指定位置开始插入元素**。

![1f0a9eb67c60cef3508bd0c21f27b6f4.png][]

代码

运行结果：

![ae06901b55bd1afb9ed8003cd3a4b824.png][]

结果

## 4，其他方法分析 ##

ArrayList包括很多方法，我们来简单回顾一下。

//移除指定位置上的元素
    public E remove(int index);
    //移除此列表中首次出现的指定元素（如果存在）
    boolean remove(Object o);
    //修改集合元素
    public E set(int index, Object o);
    //查找集合元素
    public E get(int index);
    //清空集合所有数据
    public void clear();  
    //判断集合是否包含指定元素
    public boolean contains(Object o);
    //判断集合是否为空
    public boolean isEmpty()

## 5，常见面试题（精华） ##

### 5.1，ArrayList是如何扩容的？ ###

这个请参照3.1章节的扩容步骤，来看看它的核心扩容方法：

![ef7face8bfa360506058ce838eed0a9a.png][]

grow()扩容方法

**总结：**

> 1.  扩容的大小是原先数组的1.5倍；
> 2.  若值`newCapacity`比传入值`minCapacity`还要小，则使用传入`minCapacity`，若`newCapacity`比设定的最大容量大，则使用最大整数值；

### 5.2，ArrayList频繁扩容导致性能下降，如何处理？ ###

比方说现在需要往数组里添加10w条数据，我们来看看前后的时间变化：

![daa62efcc7fc2c0812849eaaf1b51d7d.png][]

使用指定初始化容量的构造方法

结果是：

![5060151adeb64b9ac076bf5b4ed4f4f1.png][]

结果

> **ArrayList底层是数组实现的，那么每次添加数据时会不断地扩容，这样的话会占内存，性能低，所以导致时间很长。**
> 
> **我们可以用ArrayList的指定初始化容量的构造方法来解决性能低的问题。**

### 5.3，ArrayList在增删元素的时候是怎么进行的，还有为何很慢？ ###

在前面我们说过，它有按照索引添加，也有直接添加的。在这之前需要校验长度问题**ensureCapacityInternal**，如果长度不够，则需要进行扩容操作。

而前面的扩容是扩大原来的1.5倍，采用位运算，右移一位。

![7470c536793cd384f323d03948e12489.png][]

如果后面的数据量级过大，在100万条数据中新增一个元素，后面的元素都要拷贝以及移动位置，所以说效率很低。

### 5.4，ArrayList是线程安全的吗？ ###

ArrayList线程是不安全的。线程安全的数组容器是Vector，它的原理是把所有的方法都加上`synchronized`。

我们来测试一下，先准备一个线程任务类：

![579d9f4b691c0c0307df27a5b49b6b6f.png][]

然后定义测试类，对任务类进行测试：

![46936f44e0d3e4e3175c8487a726c1f4.png][]

我们来看结果：

![782030d3ae72edcc02b621d821280636.png][]

可以看到会报异常错误，有的线程还是为null，这说明ArrayList线程是不安全的。

当然可以用线程安全的集合Vector来代替ArrayList

![70ddeb6ff6b71d5602440ece676e8ba3.png][]

Vector集合

或者我们可以直接加`synchronized`关键字，把不安全的线程变成安全的：

![9b15ed9096df17f945b51d386136501c.png][]

加关键字synchronized

这样也是可以保证线程安全的。

**为啥ArrayList线程不安全？**

线程不安全：

> 线程安全就是多线程访问时，采用了加锁机制，当一个线程访问该类的某个数据时，进行保护，其他线程不能进行访问直到该线程读取完，其他线程才可使用。不会出现数据不一致或者数据污染。
> 
> 线程不安全就是不提供数据访问保护，有可能出现多个线程先后更改数据造成所得到的数据是脏数据。

List接口下面有两个实现，一个是ArrayList，另外一个是Vector。从源码的角度分析，因为Vector的方法前加了synchronized关键字。

ArrayList在添加一个元素时，有两步来完成，1. 在 Items\[Size\] 的位置存放此元素；2. 增大 Size 的值。

> 在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1；
> 
> 而如果是在 多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0（注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。
> 
> 那好，我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了。

### 5.5，ArrayList和LinkedList区别 ###

1.  **底层数据结构**：`ArrayList`底层使用的是**数组**；`LinkedList`底层使用的是**双向链表**；
2.  **插入和删除元素操作**：`ArrayList`采用的是数组存储，所以插入和删除元素是跟元素的位置有关系。`LinkedList`采用的是链表存储，删除元素是不受元素位置影响的；如果是要在指定位置i插入和删除的话`（（add(int index，E element））`时间复杂度近似为O(n)，因为需要先移动再插入。
3.  **随机访问**：`ArrayList`对于**随机元素访问**的效率明显比`LinkedList`高。随机访问就是通过元素的索引来获取元素（也就是set和get(int index)方法）。
4.  **线程不安全**：`ArrayList`和`LinkedList`都是不同步的，也就是说都是**线程不安全**的。
5.  **接口实现**：`ArrayList`实现了`RandomAccess`可以支持随机元素访问，而`LinkedList`实现了`Deque`可以当做队列使用
6.  **内存空间占用情况**：`ArrayList`的空间占用主要体现在list列表的末尾会有一定的容量空间，它的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅度降低内存的性能开销，提高效率；`LinkedList`的空间占用体现在每一个元素都需要消耗空间内存，要存放前驱后继等数据。

> 当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用`ArrayList`会提供比较好的性能；
> 
> 当操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,使用`LinkedList`会更好。

[HashMap]: http://mp.weixin.qq.com/s?__biz=MzIzNzE1ODExNw==&mid=2247486087&idx=1&sn=d463bc6b83d3f2bbe21ed115594a858c&chksm=e8cda10ddfba281b19806fe3574444fadfe85d992e84b934df68a407959d4343cace451f2718&scene=21#wechat_redirect
[78dc08d71e73c6ecbb3c497c2ee807bb.png]: /images/20221120/6e38961e91f4458aa6c92202ea39878c.png
[18263565c43656805bcd45ae92eff0f1.png]: /images/20221120/51af701b21e643afa34b0b52147ed888.png
[878a3611c8d99425a7b193c3fdc423ff.png]: https://img-blog.csdnimg.cn/img_convert/878a3611c8d99425a7b193c3fdc423ff.png
[bdd6dc47b96234be5a5a99774cbf6b11.png]: https://img-blog.csdnimg.cn/img_convert/bdd6dc47b96234be5a5a99774cbf6b11.png
[2f7cd06ac68354b3fe489d5fe5480c45.png]: https://img-blog.csdnimg.cn/img_convert/2f7cd06ac68354b3fe489d5fe5480c45.png
[bdca89d4876c29f8aa0dafb4670341ba.png]: https://img-blog.csdnimg.cn/img_convert/bdca89d4876c29f8aa0dafb4670341ba.png
[5183e9736372c72cccc6ee434cd59f5e.png]: https://img-blog.csdnimg.cn/img_convert/5183e9736372c72cccc6ee434cd59f5e.png
[10d463a48e0476ea76ce2de6069ae4ed.png]: https://img-blog.csdnimg.cn/img_convert/10d463a48e0476ea76ce2de6069ae4ed.png
[53b9c669ff8269333eadb59ac003fbda.png]: https://img-blog.csdnimg.cn/img_convert/53b9c669ff8269333eadb59ac003fbda.png
[bf206dcca9134dd2737b581c92ec9bf7.png]: https://img-blog.csdnimg.cn/img_convert/bf206dcca9134dd2737b581c92ec9bf7.png
[016e83b6d72c8c163f15353c926e76b4.png]: https://img-blog.csdnimg.cn/img_convert/016e83b6d72c8c163f15353c926e76b4.png
[a7d9de1fb15c96fd806457d2d987cef2.png]: https://img-blog.csdnimg.cn/img_convert/a7d9de1fb15c96fd806457d2d987cef2.png
[1f0a9eb67c60cef3508bd0c21f27b6f4.png]: https://img-blog.csdnimg.cn/img_convert/1f0a9eb67c60cef3508bd0c21f27b6f4.png
[ae06901b55bd1afb9ed8003cd3a4b824.png]: https://img-blog.csdnimg.cn/img_convert/ae06901b55bd1afb9ed8003cd3a4b824.png
[ef7face8bfa360506058ce838eed0a9a.png]: https://img-blog.csdnimg.cn/img_convert/ef7face8bfa360506058ce838eed0a9a.png
[daa62efcc7fc2c0812849eaaf1b51d7d.png]: https://img-blog.csdnimg.cn/img_convert/daa62efcc7fc2c0812849eaaf1b51d7d.png
[5060151adeb64b9ac076bf5b4ed4f4f1.png]: https://img-blog.csdnimg.cn/img_convert/5060151adeb64b9ac076bf5b4ed4f4f1.png
[7470c536793cd384f323d03948e12489.png]: https://img-blog.csdnimg.cn/img_convert/7470c536793cd384f323d03948e12489.png
[579d9f4b691c0c0307df27a5b49b6b6f.png]: https://img-blog.csdnimg.cn/img_convert/579d9f4b691c0c0307df27a5b49b6b6f.png
[46936f44e0d3e4e3175c8487a726c1f4.png]: https://img-blog.csdnimg.cn/img_convert/46936f44e0d3e4e3175c8487a726c1f4.png
[782030d3ae72edcc02b621d821280636.png]: https://img-blog.csdnimg.cn/img_convert/782030d3ae72edcc02b621d821280636.png
[70ddeb6ff6b71d5602440ece676e8ba3.png]: https://img-blog.csdnimg.cn/img_convert/70ddeb6ff6b71d5602440ece676e8ba3.png
[9b15ed9096df17f945b51d386136501c.png]: https://img-blog.csdnimg.cn/img_convert/9b15ed9096df17f945b51d386136501c.png