全面解析ArrayList，超详细！

程序员的时光001

发布于 2020-11-10 11:41:06

5480

发布于 2020-11-10 11:41:06

文章被收录于专栏：程序员的时光程序员的时光

写在前面：

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

思维导图：

ArrayList学习图

1，ArrayList底层数据结构

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

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

ArrayList类架构图

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

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

小结：

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

2，ArrayList构造方法

下面是查看API中构造方法

构造方法

2.1，无参构造方法

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

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

无参构造

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

//默认空容量数组，长度为0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//集合真正存储数据的容器
transient Object[] elementData;

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

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

指定初始化容量构造

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

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

来看看构造方法的源码：

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()添加方法：

add()添加方法

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

public boolean add(E e)

先来看看源码分析

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

执行流程：

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

运行结果：

结果

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

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

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

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

代码

运行结果：

结果

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

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

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

代码

运行结果：

结果

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章节的扩容步骤，来看看它的核心扩容方法：

grow()扩容方法

总结：

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

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

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

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

结果是：

结果

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

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

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

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

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

5.4，ArrayList是线程安全的吗？

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

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

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

我们来看结果：

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

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

Vector集合

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

加关键字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区别

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

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

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-11-09，如有侵权请联系 cloudcommunity@tencent.com 删除

java

编程算法

本文分享自程序员的时光微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

java

编程算法

登录后参与评论

0 条评论

热度