jdk8下ArrayList源码分析实现原理

曾经终败给现在 2022-10-23 12:53 175阅读 0赞

ArrayList  
继承抽象类AbstractList  
实现接口RandomAccess、Cloneable、Serializable  
![在这里插入图片描述][20210305162717921.png]  
1.ArrayList的初始化  
ArrayList的构造函数有3个，通过new出这三个构造函数即可得到ArrayList实例  
![在这里插入图片描述][20210305163635917.png]  
那么这三个构造函数初数化的时候都做了什么操作呢？有什么区别呢？

先看看无参构造函数源码  
![在这里插入图片描述][20210305165740327.png]  
其中有两个属性：elementData和DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，来看看定义：  
![在这里插入图片描述][20210305165844453.png]  
可以看到，elementData是一个Object\[\]的数组，被transient修饰，告诉我们该对象在序列化的时候请忽略这个元素，这个属性是用来存储数据的，没错，ArrayList的数据是通过Object\[\]来存储的。  
![在这里插入图片描述][20210305170345995.png]  
DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA是一个长度为0的初始化过的Object\[\]数组，被static和final修饰，表明属性在类加载的时候就已经初始化了，只有一份，所有实例都共享此属性，并且不能被修改。

所以当调用无参的构造函数时，如：  
![在这里插入图片描述][20210305171601950.png]

获得ArrayList实例，并初数化elementData为一个长度为0的Object\[\]数组，严格来说，是将DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA对象的引用指向elementData，内存结构图大概如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70]  
如果调用无参构造函数实例化多个ArrayList  
![在这里插入图片描述][202103051721326.png]  
内存结构图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 1]  
此时会有人提出疑问，数组的长度大小是固定的，但是ArrayList添加的数据个数并不是固定的，多个实例共享此属性，其中一个实例修改其他实例的值都会改变，而且被final修饰，那么怎么添加数据呢？

2.ArrayList的add()  
这时就要看看add()方法了  
![在这里插入图片描述][20210305173532128.png]  
可以看到add方法有四种，先看看第一种  
![在这里插入图片描述][20210305213037969.png]

Person代码：  
![在这里插入图片描述][20210305212958262.png]

源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 2]  
看看方法ensureCapacityInternal(size + 1); 干了什么，先看看size定义  
![在这里插入图片描述][20210305173724643.png]  
size为基本数据类型，默认初始值为0，代表当前ArrayList的实例存储的数据个数，+1既代表下一个数据要存储的位置。那么一个实例第一次调用add的时候，调用ensureCapacityInternal(size + 1)，参数就是1了，进入ensureCapacityInternal方法：  
注意以下**数据个数**和**数组容量**的区别，**数组容量**总是>=**数据个数**  
![在这里插入图片描述][20210305205843534.png]

首先判断elementData的引用是不是指向DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA指向的对象，如果是第一次调用add方法，是成立的，会进入if执行，第二次调用add就不成立了，为什么呢，往后看：  
先看看DEFAULT\_CAPACITY的定义：  
![在这里插入图片描述][20210305193835361.png]  
可以看到注释的意思为默认初始化容量，没错，就是ArrayList里面elementData代表的Object\[\]数组的初始化大小，具体实现看ensureExplicitCapacity(minCapacity)方法，因为调用了Math.max(DEFAULT\_CAPACITY, minCapacity)，所以minCapacity的值为10  
![在这里插入图片描述][20210305210306160.png]

重头戏来了，看看grow(minCapacity)方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 3]

if(minCapacity - elementData.length > 0):如果当前数据存储的位置大于数组原有的长度，既调用grow()方法，通过拷贝进行数组容量扩容

看看数组的最大容量MAX\_ARRAY\_SIZE的值  
![在这里插入图片描述][20210305201317632.png]  
ArrayList的最大容量为Integer.MAX\_VALUE - 8

看看工具类Arrays的copyOf(elementData, newCapacity)的方法  
![在这里插入图片描述][20210305201547136.png]  
调用了另外一个重载方法copyOf(original, newLength, original.getClass())  
![在这里插入图片描述][2021030520170773.png]  
最终调用了System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength))方法  
![在这里插入图片描述][20210305201807464.png]  
此方法为一个native方法，也就是说实现不是用java语言写的  
总结：Arrays的两个copyOf()是用来复制数组的，  
底层调用的System.arraycopy(Object src, int srcPos,Object dest, int destPos, int length)  
System.arraycopy()也是用来复制拷贝数组的，参数如下  
***src***:原数组，即被拷贝的数组  
***srcPos***:从原数组的哪个下标开始拷贝  
***dset***:目标数组，即拷贝到哪个数组上  
***destPos***:以目标数组的哪个下标开始接收拷贝  
***length***:拷贝多少个元素

**总体来说，就是将elementData的Object\[\]数组重新拷贝一份，并扩容，长度为grow()方法里面计算的newCapacity的值(大概每次扩容的容量为以前容量的1.5倍)，然后将elementData的指针指向新的被拷贝的数组。从此elementData和全局实例共享的不能被修改的DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA指向的Object\[\]数组在没有关系**

此时还没有进行存储操作，如果是第一次add，只是新建了一个容量为10的ArrayList实例，内存结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 4]

如果不是第一次操作，那么就是扩容后的ArrayList实例(大小大概为以前的1.5倍，之前的数据被复制进去了)，新值存在size的位置，然后size的大小增加1  
![在这里插入图片描述][20210305203950738.png]  
size的大小总是和ArrayList里面数据的个数相等，list1.size()获取的就是此size的值  
![在这里插入图片描述][20210305212325578.png]  
添加数据后（第一次）内存结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 5]  
4.ArrayList的其他构造函数  
第二个构造函数可以指定初始化时，ArrayList的大小，即内部Object\[\] elementData数组初始化大小  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 6]  
第三个构造函数可以传入一个集合，然后根据集合的内容构建ArrayList的实例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 7]  
其他add方法  
第二个add(int,E)方法：将元素添加到指定下标处。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 8]  
来看看rangeCheckForAdd(index);方法  
![在这里插入图片描述][20210306132931436.png]  
注意这里的元素个数：如果一个新ArrayList(默认长度为10)只添加了一个元素，而index为2，哪怕还剩9个空容量，也会抛异常  
,  
执行以下代码的原理：  
![在这里插入图片描述][20210306121538407.png]  
原理图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 9]  
第三个addAll(Collection<? extends E>)方法可以添加其他集合到末尾  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 10]

第四个addAll(int, Collection<? extends E>)可以添加其他集合到指定的位置  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 11]

如下代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 12]  
if (numMoved > 0)代表不是从末尾开始添加，进行第一次拷贝，操作的是同一个数组  
也就是list1的emementData![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 13]  
然后第二次拷贝，操作的是被转换为Object\[\]的list2和list1的emementData  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 14]  
如果(numMoved = size - index)=0既标识向末尾添加，直接进行后面的拷贝，将list2的数据拷贝到list1的末尾。numMoved是不可能小于0的  
![在这里插入图片描述][20210306151530776.png]

3.ArrayList的remove()

。  
。  
。  
其他不常用方法：  
1.给定一个容量，如果当前ArrayList实例的容量>给定的容量，那么将容量扩展为给定的容量![在这里插入图片描述][20210307154136682.png]

2.给定一个集合，删除当前集合中不包含给定集合的元素的所有元素。也就是给定集合的元素在当前集合中存在，就不删除，否则就删除。  
![在这里插入图片描述][20210307160010645.png]  
3.将集合的容量修改为和当前元素个数相等。内部实现需要进行拷贝操作  
![在这里插入图片描述][20210307160657992.png]

[20210305162717921.png]: /images/20221023/c0636d74fba14f65b49ff5055223896c.png
[20210305163635917.png]: /images/20221023/15d833b52f6546b99099fcc473cb4380.png
[20210305165740327.png]: /images/20221023/83b952ec6b1e4ed1b9e7d9ccc14357a2.png
[20210305165844453.png]: /images/20221023/d6a6173744af447b88b66bb8460fb11c.png
[20210305170345995.png]: /images/20221023/1177af7873f5494c9a32a84f7a367103.png
[20210305171601950.png]: /images/20221023/0aedb80cced8434aa7febf0614c6f59e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70]: /images/20221023/e2994e42f7244340b7f5cd73288a6ef0.png
[202103051721326.png]: /images/20221023/c2849f15d49a4eb198e3a5b1bef2fe5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/4b9ea574e012438bb2a4e16eb7786072.png
[20210305173532128.png]: /images/20221023/27d7c22bde9a4ef3a619eaed53bd3de2.png
[20210305213037969.png]: /images/20221023/cd7d02598be143d09b295b31eabd2d32.png
[20210305212958262.png]: /images/20221023/dd30c96023e542179e3bcfe3eca3e376.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/f51876ea7bde4dcebcbf1fe5fce90a1f.png
[20210305173724643.png]: /images/20221023/3195eea5eb8743a2bd82a3772920f12b.png
[20210305205843534.png]: /images/20221023/e3a19a870dd742f984c5488022f63c8e.png
[20210305193835361.png]: /images/20221023/5aaecdd8313146cc9c4d8091000d0b6e.png
[20210305210306160.png]: /images/20221023/051ee71c067f4d83a5228341884af8a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 3]: /images/20221023/984670639e1d4b1b8fa928d1e941d57e.png
[20210305201317632.png]: /images/20221023/9982334d592b406781354ec98183850e.png
[20210305201547136.png]: /images/20221023/cacaf643f3fe4df4b4c953f549d6ad57.png
[2021030520170773.png]: /images/20221023/d93e102878b04044a653c0edac6aedc4.png
[20210305201807464.png]: /images/20221023/8c3160520e0a4eca94d5a5b74c67bded.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 4]: /images/20221023/2d1626725dfb4992ad8bb75eedc71b68.png
[20210305203950738.png]: /images/20221023/9d728b28fda44c4a8238f807c9746037.png
[20210305212325578.png]: /images/20221023/15e1c2e3a4a144a68daf025d72c550ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 5]: /images/20221023/9328f65fc39847558d0ad57ae046b3d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 6]: /images/20221023/07705591e4c04f1db5088d9fa08f9a15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 7]: /images/20221023/6cb8f8373c0944928c85d85d0bcd9972.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 8]: /images/20221023/46ba85bd58fd462990b9360ad9258382.png
[20210306132931436.png]: /images/20221023/47c5029523324b2f9a878bb2f24b0e11.png
[20210306121538407.png]: /images/20221023/3a011220bf9c4890982779ac09bb3417.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 9]: /images/20221023/570975cbb3c84f9fb9106b212756cd4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 10]: /images/20221023/b8d957f765ae417cb760e66092e37458.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 11]: /images/20221023/b2b67a6dc7da4ac9b89671afaa6769e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 12]: /images/20221023/06b51df289604864a2e9c0d1764bdfc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 13]: /images/20221023/d310827991834a6f88b88ff54b22d08d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RpZ2xsZQ_size_16_color_FFFFFF_t_70 14]: /images/20221023/ecddf4cfe7a34bfcb4f89f66790fa808.png
[20210306151530776.png]: /images/20221023/432447634cbd4091976dfc65ebe4ecd6.png
[20210307154136682.png]: /images/20221023/b118b7a134fc4be889363796b2ce5cbd.png
[20210307160010645.png]: /images/20221023/f685c663f164420c97b7cc72a1b6f604.png
[20210307160657992.png]: /images/20221023/64f5aabce3244bc1a6662b119bc8793b.png