ArrayList源码探究

系统管理员 2022-01-21 10:31 262阅读 0赞

# ArrayList源码探究 #

本文全部以jdk1.8源码为根据，探究ArrayList的实现，原创blogs，转载请注明。

## 构造方法 ##

ArrayList底层是一个长度可以动态增长的数组

*  默认的构造方法是构建一个初始容量为10的空list  
    ![在这里插入图片描述][2019060920140775.png]
 *  用于默认大小的空实例的共享空数组实例。 我们将此与EMPTY\_ELEMENTDATA区分开来，以便在添加第一个元素时知道要膨胀多少。上面不是说初始容量为10吗，奇怪了，为什么这里是空数组，在add()方法中会对此进行解释。![在这里插入图片描述][20190609201435113.png]
 *  带参数的构造方法可以指定ArrayList的大小  
    ![在这里插入图片描述][20190609201452495.png]
 *  当指定长度为0的时候，为一个空数组。  
    ![在这里插入图片描述][20190609201550989.png]

## 添加方法add(E e) ##

*  添加方法的源码如下：  
    ![在这里插入图片描述][20190609201635797.png]
 *  size的默认长度为0  
    ![在这里插入图片描述][20190609201652918.png]
 *  点开扩容方法：  
    ![在这里插入图片描述][201906092017187.png]  
    如果elementData和DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA地址相同，说明是默认的数组，在这里发现minCapacity是取默认容量和minCapacity中一个较大的值，第一次添加时，minCpacity为1，所以肯定会赋值为DEFAULT\_CAPACITY，  
    ![在这里插入图片描述][20190609201752644.png]  
    可以看出默认容量为10.所以初始化的时候，才会说创建初始容量为10的一个list容器。
 *  接下来就是对数组扩容了：  
    ![在这里插入图片描述][20190609201817743.png]  
    其中newCapacity的值为 10 + 10 >> 1 = 10 + 5 = 15 每次扩容50%  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTUxNDg1_size_16_color_FFFFFF_t_70]  
    然后使用Arrays.copyOf进行扩容，为已有的数组指定容量即可。  
    注释为：  
    Copies the specified array, truncating or padding with nulls (if necessary) so the copy has the specified length. For all indices that are valid in both the original array and the copy, the two arrays will contain identical values. For any indices that are valid in the copy but not the original, the copy will contain null. Such indices will exist if and only if the specified length is greater than that of the original array. The resulting array is of exactly the same class as the original array.  
    复制指定的数组，使用空值截断或填充（如有必要），以使副本具有指定的长度。 对于在原始数组和副本中都有效的所有索引，这两个数组将包含相同的值。 对于在副本中有效但不在原始副本中的任何索引，副本将包含null。 当且仅当指定的长度大于原始数组的长度时，这些索引才会存在。 生成的数组与原始数组完全相同。  
    ![在这里插入图片描述][2019060920194574.png]

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

*  remove(Object 0)方法的注释为：  
    ![在这里插入图片描述][20190609202124845.png]  
    ![在这里插入图片描述][20190609202148179.png]  
    方法非常简单，分两种情况，null和非null，循环遍历比较后相同，则移除，然后返回true。如果两种情况都不符合，就返回false。
 *  关键在于fastRemove(index)方法  
    ![在这里插入图片描述][20190609202256411.png]  
    先确定复制的数量numMoved即size - (index + 1)，大于0的时候，就是用arracopy方法进行操作
 *  public static void arraycopy（@NotNull Object src， // 复制的源数组  
    int srcPos，// 复制的起始位置  
    @NotNull Object dest，// 复制的目标数组  
    int destPos，// 复制的目标位置  
    int length）// 复制的长度  
    将指定源数组中的数组从指定位置开始复制到目标数组的指定位置。数组组件的子序列从src引用的源数组复制到dest引用的目标数组。复制的组件数等于length参数。源数组中位置srcPos到srcPos + length-1的组件分别被复制到目标数组的destPos到destPos + length-1的位置。  
    如果src和dest参数引用相同的数组对象，则执行复制，就好像位置srcPos到srcPos + length-1的组件首先被复制到具有长度组件的临时数组，然后临时数组的内容是通过目标数组的destPos + length-1复制到destPos的位置。  
    如果dest为null，则抛出NullPointerException。  
    如果src为null，则抛出NullPointerException并且不修改目标数组。  
    否则，如果满足以下任何条件，则抛出ArrayStoreException并且不修改目标：  
    src参数指的是不是数组的对象。  
    dest参数指的是不是数组的对象。  
    src参数和dest参数引用其组件类型为不同基本类型的数组。  
    src参数引用具有基本组件类型的数组，dest参数引用具有引用组件类型的数组。  
    src参数引用具有引用组件类型的数组，dest参数引用具有基本组件类型的数组。  
    否则，如果满足以下任何条件，则抛出IndexOutOfBoundsException并且不修改目标：  
    srcPos参数为负数。  
    destPos参数是否定的。  
    长度参数是否定的。  
    srcPos + length大于src.length，即源数组的长度。  
    destPos + length大于dest.length，即目标数组的长度。  
    否则，如果从位置srcPos到srcPos + length-1的源数组的任何实际组件无法通过赋值转换转换为目标数组的组件类型，则抛出ArrayStoreException。在这种情况下，令k为小于length的最小非负整数，使得src \[srcPos + k\]不能转换为目标数组的组件类型;抛出异常时，从srcPos到srcPos + k-1位置的源数组组件已经被复制到目标数组位置destPos到destPos + k-1，并且目标数组的其他位置都不会被修改。 （由于已经逐项列出的限制，本段有效地仅适用于两个数组都具有引用类型的组件类型的情况。）  
    ![在这里插入图片描述][20190609202423518.png]  
    ![在这里插入图片描述][2019060920243933.png]
 *  最后，将数组指定位置置为null，GCRoot不可达，可以被回收。

找来找去，没有找到自动缩容的代码段，这里问题来了，ArrayList不能缩容吗？？其实是可以的，有一个方法可以缩容：  
![在这里插入图片描述][201906092026266.png]

# 其他部分API #

*  public int size()  
    ![在这里插入图片描述][20190609203545591.png]![在这里插入图片描述][20190609203554449.png]  
    直接返回size的值即可。
 *  public E get(int index)  
    ![在这里插入图片描述][20190609203634490.png]  
    先验证索引是否合理，是否大于size的值  
    检查给定索引是否在范围内。 如果不是，则抛出适当的运行时异常。 此方法不\*检查索引是否为负数：它始终在数组访问之前立即使用，如果索引为负，则抛出ArrayIndexOutOfBoundsException。  
    ![在这里插入图片描述][20190609203702371.png]  
    然后从elementData数组中取得即可  
    ![在这里插入图片描述][20190609203723133.png]  
    ![在这里插入图片描述][20190609203733135.png]
 *  public String toString()  
    java.util.AbstractCollection.java  
    用迭代器进行遍历输出，很简单。  
    ![在这里插入图片描述][2019060920381098.png]
 *  public Iterator iterator  
    ![在这里插入图片描述][20190609203835625.png]  
    在ArrayList中提供了一个内部类，实现了Iterator接口  
    ![在这里插入图片描述][20190609203851346.png]
 *  public boolean contains(Object o)  
    ![在这里插入图片描述][20190609203954394.png]  
    indexOf(0)就是遍历比较呗，有则返回索引，无则返回 -1；  
    ![在这里插入图片描述][20190609204022110.png]  
    ArrayList源码相对其他容器类较为简单，下面会分析其他容器类的底层源码。

[2019060920140775.png]: /images/20220121/fec75536193a433c87dbf774a2be1204.png
[20190609201435113.png]: /images/20220121/9d8f48ba07944602a953f26092533e35.png
[20190609201452495.png]: /images/20220121/4cb978751f404941bbefdff5b0d6e727.png
[20190609201550989.png]: /images/20220121/7895d9e655d541d5a1da1b93352b968d.png
[20190609201635797.png]: /images/20220121/4c56a3280b284c5ab81409d9629e6d78.png
[20190609201652918.png]: /images/20220121/c74b164afc284911879451f05a8079ff.png
[201906092017187.png]: /images/20220121/2ee29d731dde46cf90cf55e034e6edc8.png
[20190609201752644.png]: /images/20220121/cb2b2d4902c142d68eba60cfc9e2ef87.png
[20190609201817743.png]: /images/20220121/85ffa2ae248144cfb939c76a309a1064.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5OTUxNDg1_size_16_color_FFFFFF_t_70]: /images/20220121/07380b177134476b8b3c426957339882.png
[2019060920194574.png]: /images/20220121/8ff2116053b345ddb0bf532ad18b352a.png
[20190609202124845.png]: /images/20220121/75b7e4835546443ba79760ca29bbefd9.png
[20190609202148179.png]: /images/20220121/f05df5ab22c74dcc9c503b38d2005744.png
[20190609202256411.png]: /images/20220121/1edd37638bdd4f46b9233c368f743a52.png
[20190609202423518.png]: /images/20220121/ebd9b0f850264b7594a824b6ec19becc.png
[2019060920243933.png]: /images/20220121/c6171c0362ee41678ddf327526db9567.png
[201906092026266.png]: /images/20220121/f7be70b79144435b8b684c19666a5298.png
[20190609203545591.png]: https://img-blog.csdnimg.cn/20190609203545591.png
[20190609203554449.png]: /images/20220121/9956d5d7b17c4f66a9e4f3c9200eeba8.png
[20190609203634490.png]: /images/20220121/9b1fd70639d944e6be080f20d6b7e95c.png
[20190609203702371.png]: /images/20220121/4cc3eb4f8bc14489824554d711e83fe3.png
[20190609203723133.png]: /images/20220121/9b6264d5e57a4beb92f34aca29417876.png
[20190609203733135.png]: /images/20220121/bc69d5812105483c88dfdad8f4e82bd4.png
[2019060920381098.png]: /images/20220121/5781d43981704cabb71d47650ee1f4f4.png
[20190609203835625.png]: /images/20220121/e2c57fa5d24041ac94bf7aa4193df596.png
[20190609203851346.png]: /images/20220121/3c5ad0b5aa464e108c1cb9f3dadb8280.png
[20190609203954394.png]: /images/20220121/8067a3e236a6408a89ab797af382b324.png
[20190609204022110.png]: /images/20220121/cc1b0f61638049bdb54c7a43e52323bd.png