开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> ArrayList底层结构和源码分析 -> 正文阅读

[数据结构与算法]ArrayList底层结构和源码分析

ArrayList的底层是由数组实现的，数组的特点是固定大小，而ArrayList实现了动态扩容。

那么实现ArrayList的数组是什么样的，如何创建使用的？
这个扩容机制又是什么样子的呢？
以上两个问题是我们本篇文章将要探讨的主要内容

以下分析使用的是JDK8

结论

ArrayList中维护了一个Object类型的数组elementData
```
transient Object[] elementData;
```
当创建ArrayList对象时，如果使用的是无参构造器，则初始化elementData容量为0，第1次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为原先的1.5倍
如果使用的是指定大小的构造器，则初始化elementData容量为指定大小，如果需要扩容，则会直接扩容elementData为1.5倍

ArrayList的源码分析

这里以如下代码为切入点进行源码分析

public class ArrayListSource {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
//        ArrayList list = new ArrayList(8);
        for (int i = 0; i <= 10; i++) {
            list.add(i);
        }
        for (int i = 11; i <= 15; i++) {
            list.add(i);
        }
        list.add(100);
        list.add(200);
        list.add(null);
    }
}

初始化ArrayList

首先从这一行进行debug
在这里插入图片描述

进入ArrayList的空参构造，源码如下图
在这里插入图片描述

this.elementData（存放我们放入集合中数据的数组缓冲区）：ArrayList底层就是通过这个elementData来实现的。我们放入ArrayList中的元素最终都会放到这个数组中来。查看这个elementData变量的源码，如下该数组是一个被transient修饰的不可序列化的一个数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认容量为空的一个数组，说明我们在实例化创建ArrayList集合的时候默认创建的是一个空的数组，查看DEFAULTCAPACITY_EMPTY_ELEMENTDATA的源码如下

如此ArrayList集合的空参构造我们就说清楚了。
总结一下：
ArrayList集合使用空参构造器创建一个集合底层其实就是创建了一个长度为0的Object类型的数组

添加元素

当debug走到如下这一行
在这里插入图片描述
此时要添加的元素为int类型的1
注意：
因为集合只能够添加对象作为元素，所以基本数据类型int是不能直接添加到ArrayList中的，这里首先会自动的进行装箱操作，将int类型的1装箱为integer类型的1在进行添加操作
然后进入ArrayList的add方法，源码如下
在这里插入图片描述

E e：泛型表示任意类型的元素，就是我们调用方法传入的元素
size：这个size变量表示的是当前elementData数组中元素的数量，其实它的就是下一次用于给elementData数组赋值的指针
ensureCapacityInternal()：该方法的作用是在添加新的元素之前查看我们存储集合元素的Object数组的容量是否足够，如果不够那么需要进行扩容操作
elementData[size++]：就是简单的将我们通过add方法加入的元素复制到集合对应的索引位置，然后指针size向后移动一位（就表示数组内总容量加一）

总结ArrayList的add方法：

先确定是否需要扩容，如果需要扩容就进行扩容
然后将新加入的元素赋值给elementData数组

扩容机制

ensureCapacityInternal()方法

我们来详细看一下ensureCapacityInternal()的源码的扩容机制,ensureCapacityInternal()源码如下
在这里插入图片描述

minCapacity：表示当前集合需要的最小容量

解读：
如果说我们当前elementData这个数组就是我们默认容量为空的时候的数组的话，说明这次这一次是第一次进行要进行扩容操作。
我们就通过Math.max这个方法从我们传入进来的minCapacity和DEFAULT_CAPACITY这个常量的最大值作为新的minCapacity（当然这里肯定是10，因为第一给集合添加数据的话，传递进来的参数值肯定是1），这是为了获取从空数组（构造器中的elementData是一个长度为0的Object数组）扩容到有长度的数组的第一次扩容的大小
查看这个DEFAULT_CAPACITY常量，源码如下
在这里插入图片描述
可以看到从空数组第一次进行扩容时扩容到长度为10
反之如果不是第一次进行扩容的话，需要扩容到的长度就是传入进来的参数值也就是当前集合需要的最小容量

最终调用ensureExplicitCapacity()方法

总结ensureCapacityInternal方法
ensureCapacityInternal()方法中判断elementData数组是否为空，也就是判断是否是第一次添加元素，如果是第一次添加元素，则设置初始化大小为默认容量10，否则为传入的参数。这个方法的目的就是获取初始化数组容量。获取到初始化容量后调用ensureExplicitCapacity(minCapacity)方法，判断是否需要扩容

ensureExplicitCapacity()方法

然后查看ensureExplicitCapacity()方法的源码，源码如下
在这里插入图片描述

modCount：用来记录当前集合被修改的次数，主要为了当多个线程同时操作该数组出现线程安全问题的时候及时抛出错误
该字段的源码如下：

解读if后的内容：
如果我们当前需要的最小容量大于我们的elementData数组的容量的话，表示我们就需要对数组进行扩容操作了

总结ensureExplicitCapacity方法
ensureExplicitCapacity(minCapacity)方法用来判断是否需要扩容，如果当前需要集合的最小长度大于数组本身的长度，那么就说明容量不够了就调用grow(minCapacity)方法进行扩容。
假如第一次添加元素，minCapacity为10，elementData容量为0，那么就需要去扩容。调用grow(minCapacity)方法。

grow(minCapacity)方法

然后我们进入grow(minCapacity)方法来查看ArrayList扩容机制最核心的源码内容，如下
在这里插入图片描述

解读
1、

int oldCapacity = elementData.length;

首先获取elementData原来的长度。
注意第一次扩容的时候原来的长度是0
2、

int newCapacity = oldCapacity + (oldCapacity >> 1);

以上代码就是扩容每一次都扩容1.5倍的具体实现了
新的容量大小=旧的容量大小+旧的容量大小的一半
这里位运算1位就相当于/2的操作了
注意第一次扩容的时侯根据这个公式得到的新的容量大小为0
3、

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

上述代码就是为了解决第一次扩容的时候根据公式计算出来的新的容量为0的情况，第一次扩容的时候0减去10肯定小于0，然后将新扩容的大小设置为第一次的minCapacity这个值也就是10
4、

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

这里的MAX_APPAY_SIZE如下是一个常量
在这里插入图片描述
如果当前扩容后的数组大小大于最大的数组长度（就是MAX_ARRAY_SIZE这个常量），就调用hugeCapacity方法，hugeCapacity方法源码如下

如果当前需要的最小容量小于0，那么说明出现异常了，抛出OOM异常。如果一切正常判断当前需要的最小容量是否大于常量MAX_ARRAY_SIZE数组能够定义的最大值，如果大于的话就返回int的最大值防止溢出，不大于就返回常量MAX_ARRAY_SIZE这个长度

5、

// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);

最终通过Arrays数组的工具类中的copyOf复制方法将elementData数组扩容到新的容量

总结
grow(minCapacity)方法对数组进行扩容，扩容大小为原数组的1.5倍，如果计算出的扩容容量比需要的容量小，则扩容大小为需要的容量，如果扩容容量比数组最大容量大，则调用hugeCapacity(minCapacity)方法，将数组扩容为整数的最大长度，然后将elemetData数组指向新扩容的内存空间并将元素复制到新空间。

当需要的集合容量特别大时，扩容1.5倍就会非常消耗空间，因此建议初始化时预估一个容量大小。

指定大小初始化ArrayList

此时我们使用如下方式创建集合

public class ArrayListSource {
    public static void main(String[] args) {
        ArrayList list = new ArrayList(8);
    }
}

使用debug查看有参构造的源码

指定数组初始化大小的源码如下
在这里插入图片描述
创建一个预估大小的数组，指定大小后只是指定了数组初始值的大小，不影响后面扩容，指定的好处就是可以节省内存及时间上的开销。

删除元素

ArrayList提供两种删除元素的方法，可以通过索引和元素进行删除。两种删除大同小异，删除元素后，将后面的元素一次向前移动。

ArrayList.remove(int index)源码：
在这里插入图片描述
1、

rangeCheck(index);

通过rangeCheck(index);方法判断参数是否大于数组的长度从而越界
rangeCheck(index);的源码内容如下
在这里插入图片描述
2、

modCount++;

用来记录当前集合被修改的次数，主要为了当多个线程同时操作该数组出现线程安全问题的时候及时抛出错误
3、

E oldValue = elementData(index);

根据索引获取数组对应的该下标的值
elementData(index)方法源码如下
在这里插入图片描述
4、

int numMoved = size - index - 1;

获取要删除的索引后面的所有需要向前移动的元素个数

5、

if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);

如果需要移动的个数大于0，那么就通过System.arraycopy方法将从要删除的索引的后面的numMoved个元素，拷贝到从要删除的索引开始的位置往后依次插入
5、

elementData[--size] = null;

最终将最后elementData的最后一个元素置为null

最终返回删除掉的值

删除元素总结
删除元素时，首先会判断索引是否大于ArrayList的大小，如果索引范围正确，则将索引位置的下一个元素赋值到索引位置，将ArrayList的大小减一，最后返回移除的元素。操作图如下，假如我要移除索引为1的元素：
在这里插入图片描述

源码分析总结

ArrayList底层是数组实现的，可以进行动态扩容，扩容大小为原来的1.5倍，虽然可以通过动态扩容，但是数组非常大时会特别浪费空间，因此建议初始化时预估数组大小。ArrayList允许插入重复值和空值。ArrayList实现了RandomAccess接口，支持快速随机访问，就是可以通过索引快速查到某个元素，因此遍历时使用for循环的方式效率更高。ArrayList是线程不安全的，可以通过Collections.synchronizedList将其转变为线程安全的集合，不过一般不会使用，Vector和CopyOnWriteArrayList是线程安全的，Vector性能一般，逐渐被CopyOnWriteArrayList取代了。

部分内容参考与如下博客
https://www.cnblogs.com/zhixie/p/14137332.html