Java集合05 - ArrayList

小灰灰 2022-12-27 14:18 63阅读 0赞

**目录**

1.ArrayList是什么

2.ArrayList底层实现

2.1 被transient修饰的问题

2.2 ArrayList的扩容机制

2.3 ArrayList增删改查方法时间复杂度

3.ArrayList的fail-fast特性

--------------------

## 1.ArrayList是什么 ##

一个基于动态数组的List实现，继承自AbstractList，实现了List、RandomAccess、Cloneable、Serializable，支持快速随机访问、克隆及序列化（不了解的小伙伴可以移步我前几篇博文，对这几个接口有做详细的说明）。源码上的注释告诉了我们以下几件事：

**       底层实现**：ArrayList基于动态可调整的数组实现，可存null，实现List接口方法的同时还提供了一些操作内部用于存储元素数组的方法，非线程安全。

**       扩容机制：**每一个ArrayList实例都有一个容量参数capacity，至少和列表大小一样大。当有元素新增时，容量会自动增长，在添加大量元素之前可以使用ensureCapacity方法进行扩容，这可能会减少增量重新分配的数量。

**时间复杂度：**往ArrayList中添加元素时，时间复杂度O(n)。

**同步机制：**ArrayList的实现是不同步的，如果多个线程同时访问ArrayList实例，并且至少有一个线程在结构上进行了修改，则必须在外部同步。（结构修改是指添加、删除一个或多个元素，或显式调整底层储存数组容量的操作；仅仅设置元素的值不是结构修改），这通常是通过在ArrayList实例对象上进行同步来实现。 如果不存在这样的对象，应使用Collections.synchronizedList(new ArrayList(...))来创建线程同步的集合。

**fail-fast特性：**迭代器为快速失败，用迭代器遍历ArrayList时，迭代器的remove()和add()会抛出ConcurrentModificationException异常，迭代器的fail-fast行为在不同步的并发修改时不能得到硬性保证，fail fast行为应仅用于检测错误，不要依赖此异常进行编程。

个人理解：注释有些说的不全，笔者会在接下来逐条补充。其实搞懂一个集合无非也就是从这几方面入手，集合的底层实现，增加删除扩容方法的具体实现，具体时间复杂度分析，是否支持同步，如果不支持同步的解决方案是什么，集合的特性是什么，注意事项是什么。

## 2.ArrayList底层实现 ##

###      2.1 被transient修饰的问题 ###

ArrayList底层实现着重看以下两个属性：

![20201215163231967.png][]

![20201215163241781.png][]

elementData即为ArrayList底层存储结构，为一个Object\[\]类型的数组，我们注意到被transient修饰，被此关键字修饰的变量不会被序列化为字节流（这里涉及到序列化机制的问题，不了解的小伙伴可以移步我这篇文章[Java集合02 - Serializable][Java_02 - Serializable]），那么问题来了，上面还在说ArrayList支持序列化，到这你说它底层数组不支持序列化，Are you kidding me？？？别急，我们知道可以通过字节流实现对象的序列化，ArrayList对stream的read方法自己进行了实现，writeObject：

private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{
        //下行代码和快速失败机制有关，可以先略过此代码，不影响整体流程
        int expectedModCount = modCount;
        //创建一个默认的outputStram
        s.defaultWriteObject();
        //设置需要写入的容量
        s.writeInt(size);
        //for循环写入数组元素
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        //下行代码和快速失败机制有关，可以先略过此代码，不影响整体流程
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

我们可以看到ArrayList对writeObject的实现逻辑为：按需序列化，只保存了非null的数组位置上的数据，精准而优雅。

###      2.2 ArrayList的扩容机制 ###

**扩容的概念：**顾名思义就是当底层数组存储容量不够的时候扩大存储容量

**扩容时机：**出现在add()和readObject()方法，在添加时和从对象流导入对象时。

**扩容方法源码：**

private void grow(int minCapacity) {
        //入参为实际容量，获取原数组容量
        int oldCapacity = elementData.length;
        //进行1.5倍扩容，计算新数组容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果扩容后的容量比实际容量还小的话，直接使用实际容量进行扩容
        if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
        //如果扩容后的容量比最大容量还大的话，进入最大化扩容判断。实际容量比数组最大容量还大，则取Integer最大值，如果实际容量比最大容量小，则取数组最大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
        //计算好需扩容容量后进行实际扩容操作
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

源码比较简单，可以看到ArrayList底层默认1.5倍扩容。这里两个考点，1. Arrays.copyOf底层调用的System.arraycopy，拷贝原理为利用反射新建扩容后的数组，然后进行数组元素的复制，最后将新数组引用返回。2. 判断是否需要扩容的函数（ensureCapacityInternal）内部会对modCount（判断是否触发fail-fast机制的变量）进行+1操作。

###      2.3 ArrayList增删改查方法时间复杂度 ###

**增加：**

add(E e)：添加元素到末尾，平均时间复杂度为O(1)，数组的特性，根据索引直接定位元素位置。

add(int index, E element)：添加元素到指定位置，平均时间复杂度为O(n)，因为添加当前索引元素后还需对后续其他元素进行右移。

**删除：**

remove(int index)：删除指定索引位置的元素，平均时间复杂度为O(n)，因为删除当前索引元素后还需对后续其他元素进行左移。

**修改：**

set(int index, E element)：修改指定索引位置的元素，平均时间复杂度为O(1)，数组的特性，根据索引直接定位元素位置。

** 查询：**

get(int index)：获取指定索引位置的元素，时间复杂度为O(1)，数组的特性，根据索引直接定位元素位置。

## 3.ArrayList的**fail-fast特性** ##

** **fail-fast特性不光ArrayList有，其它集合也有，所以笔者单独起了一篇文章写了java的fail-fast，有兴趣的小伙伴可以移步：[Java中的fail-fast机制][Java_fail-fast]。

[20201215163231967.png]: /images/20221120/b931816720c541328d025bd935661b2c.png
[20201215163241781.png]: /images/20221120/ec582a05316c4d098e3d3fb6f54a03ab.png
[Java_02 - Serializable]: https://blog.csdn.net/qq_36756682/article/details/110924264
[Java_fail-fast]: https://blog.csdn.net/qq_36756682/article/details/111246631