全网最硬核的源码分析之——ArrayList源码分析

闪到太空去

ArrayList 源码分析

一.ArrayList 数据结构

ArrayList 数据结构，就是一个数组结构，如下图：

图中展示是长度为 10 的数组，从 1 开始计数，index 表示数组的下标，从 0 开始计数，elementData 表示数组本身

1.1 重要变量


二.源码分析

2.1 ArrayList 类注释解析

• 允许 put null 值，会自动扩容；
  
• size、isEmpty、get、set、add 等方法时间复杂度都是 O (1)；
  
• 是非线程安全的，多线程情况下，推荐使用线程安全类：Collections#synchronizedList；
  
• 增强 for 循环，或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常。
  

2.2 初始化实现
源码解析：
ArrayList 有三种初始化办法：无参数直接初始化、指定大小初始化、指定初始数据初始化，源码如下：


注意事项：

• ArrayList 无参构造器初始化时，默认大小是空数组，并不是大家常说的 10，10 是在第一次 add 的时候扩容的数组值。
  

2.3 新增和扩容实现
源码解析：
新增就是往数组中添加元素，主要分成两步：

• 判断是否需要扩容，如果需要执行扩容操作；
  
• 直接赋值。
  

新增：


扩容：


扩容的本质：
扩容是通过： Arrays.copyOf(elementData,  newCapacity); 这行代码实现的，这行代码描述的本质是数组之间的拷贝，扩容是会先新建一个符合我们预期容量的新数组，然后把老数组的数据拷贝过去，我们通过 System.arraycopy 方法进行拷贝，此方法是 native 的方法，源码如下:


注意事项：

• 扩容的规则并不是翻倍，是原来容量大小 + 容量大小的一半，扩容后的大小是原来容量的 1.5 倍；
  
• ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了。新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的。
  
• 源码在扩容的时候，有数组大小溢出，就是说扩容后数组的大小下界不能小于 0，上界不能大于 Integer 的最大值。
  
• 扩容完成之后，赋值是非常简单的，直接往数组上添加元素即可：elementData [size++] =  e。这种简单赋值，没有任何锁控制，所以这里的操作是线程不安全的：
  

2.4 删除实现
源码解析：
ArrayList  删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等等，我们选取根据值删除方式来进行源码说明：


上面代码已经找到要删除元素的索引位置了，下面代码是根据索引位置进行元素的删除：


注意事项：

• 新增的时候是没有对 null 进行校验的，所以删除的时候也是允许删除 null 值的；
  
• 找到值在数组中的索引位置，是通过 equals 来判断的，如果数组元素不是基本类型，需要我们关注 equals 的具体实现。
  
• 某一个元素被删除后，为了维护数组结构，我们都会把数组后面的元素往前移动
  

三.时间复杂度

经过新增或删除方法的源码解析，对数组元素的操作，只需要根据数组索引，直接新增和删除，所以时间复杂度是 O (1)。
四.线程安全

4.1 出现线程安全原因
只有当 ArrayList 作为共享变量时，才会有线程安全问题，当 ArrayList 是方法内的局部变量时，是没有线程安全的问题的。
ArrayList 有线程安全问题的原因，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被覆盖的情况。
类注释中推荐我们使用 Collections#synchronizedList 来保证线程安全，SynchronizedList 是通过在每个方法上面加上锁来实现，虽然实现了线程安全，但是性能大大降低，具体实现源码：


我们也可以使用CopyOnWriteArrayList来保证线程安全  具体对比可以参考以下表格
4.2 保证线程安全方式的对比：


五.总结

ArrayList 底层是数组结构， API 都是对数组的操作进行封装，让使用者无需感知底层实现，只需关注如何使用即可。
如果感觉对您有帮助，希望大家可以关注一下，点个赞再走，感谢！！！

作者：梦尘啊
链接：https://juejin.cn/post/6930413904422305806
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

山青云淡

不错 支持下