ArrayList源码解析 基于JDK1.8
2022/7/4 14:20:18
本文主要是介绍ArrayList源码解析 基于JDK1.8，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
1.问题产生原因
最近在写leetcode的题目https://leetcode.cn/problems/subsets/时，在评论区看到了一种解法，其中出现了
List<Integer> newNumber = new ArrayList<>(result); //result为List<Integer>类型
的代码语句，一般来说ArrayList的初始化为
List<Integer> some=new ArrayList<>();
即括号内没有参数，那如果里面有参数是什么意思。这需要我们去解读ArrayList的源码。
2.源码解析
2.1类声明
ArrayList继承了一个抽象类，实现了四个接口
分析：
- 为什么要先继承AbstractList，而让AbstractList先实现List
？而不是让ArrayList直接实现List ？ - 这里是有一个思想，接口中全都是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法，正是利用了这一点，让AbstractList是实现接口中一些通用的方法，而具体的类，如ArrayList就继承这个AbstractList类，拿到一些通用的方法，然后自己再实现一些自己特有的方法，这样一来，让代码更简洁，将继承结构最底层的类中通用的方法都抽取出来，先一起实现了，减少重复代码。所以一般看到一个类上面还有一个抽象类，应该就是这个作用。
- ArrayList实现了哪些接口？
List<E>接口：ArrayList的父类AbstractList也实现了List接口，那为什么子类ArrayList还是去实现一遍呢？最终在stackOverFlow找到了答案。网址为 http://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete。开发这个collection 的作者Josh说，这其实是一个mistake，因为他写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。 RandomAccess接口：一个标记性接口，它就是用来快速随机存取，实现了该接口的话，使用普通的for循环来遍历，性能更高，例如arrayList。而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如linkedList。所以这个标记性只是为了让我们知道用什么样的方式去获取数据性能更好。Cloneable接口：实现该接口标识着该类可以被克隆/复制，其内部实现了clone方法供使用者调用来对 ArrayList 进行克隆，但本质是通过Arrays.copyOf完成对 ArrayList的浅复制，也就是改变复制后的元素，源元素也会改变。Serializable接口：序列化接口 。实现该接口，表明该类可以被序列化，序列化简单的说，就是能够将类变为字节流传输，然后还能将字节流变为原来的类。
2.2类属性
// 序列化自动生成的一个码，用来在正反序列化中验证版本一致性，一致可以进行反序列化
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量大小为10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 静态共享空数组实例（用于空实例）
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 静态共享空数组实例（用于默认大小空实例）
* 将它和EMPTY_ELEMENTDATA区别开来，
* 以便在添加第一个元素时知道数组容量需要扩容多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList数据的数组，transient修饰此对象
* ArrayList的容量是这个数组缓冲区的长度
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList当前元素个数，默认为 0
*/
private int size;
/**
* 可以分配的最大容量
* Integer.MAX_VALUE - 8 是因为数组中有一个额外的元数据，
* 用于表示数组的大小（8bytes）
* 强制分配可能会导致 OutOfMemoryError
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
除上面的属性之外，还有一个经常用到的属性是从AbstractList继承过来的属性modCount，代表ArrayList集合的修改次数。
分析：
EMPTY_ELEMENTDATA：当有参构造方法的参数为0时使用该变量给elementData赋值。DEFAULTCAPACITY_EMPTY_ELEMENTDATA：当无参构造方法使用时，使用该变量给elementData赋值。- 两个空数组是用来区分是空构造函数还是带参数构造函数构造的ArrayList,可以针对有参无参的构造在扩容时做区分走不同的扩容逻辑，优化性能。
- 之所以是一个空数组，不是null，是因为使用的时候我们需要制定参数的类型，如果是null，那就根本不知道元素类型是什么了。
- 在无参构造函数创建ArrayList时其实创建的是一个容量为0的数组，只有在第一次新增元素时才会被扩容为10。
补充：JDK7无参构造初始化ArrayList对象时，直接创建了长度为10的 数组elementData
modcount：用于记录修改操作的次数，当数组有变动时，它就会+1。该属性是快速失败机制所需要的，主要是为了保证在迭代器使用时不会出现越界而设置，因为如果迭代器开始使用后，其它线程删除了数组的几个元素就会出现越界。如果操作前后的修改次数对不上，那么有些操作就是非法的。expectedModCount：迭代器初始化时记录的 modCount 值，每次访问新元素时都会检查 modCount 和 expectedModCount 是否相等，不相等就会抛出异常。这种机制叫做 fail-fast/快速失败，所有集合类都有这种机制。fail-fast/快速失败机制：是集合类应对并发访问在对集合进行迭代过程中，内部对象结构发生变化的一种防护措施。- 如果在创建迭代器之后的任何时间以任何方式对数组进行了结构修改，则除了通过迭代器自己的remove或add方法之外，迭代器都会抛出ConcurrentModificationException。
- 因此，面对并发修改，迭代器会快速且干净地失败，而不会在未来的不确定时间内冒任意不确定的行为的风险。不过注意，迭代器的快速失败行为无法得到保证，因为通常来说，在存在非同步的并发修改的情况下，不可能做出任何严格的保证。快速失败的迭代器会尽最大努力抛出ConcurrentModificationException。
- 因此，编写依赖于此异常的程序的正确性是错误的：迭代器的快速失败行为仅应用于检测错误。
- elementData：ArrayList 的数据域，我们代码中的add的数据都会被放在这个数组里。transient修饰此属性表示它不需要自动序列化即需要手动序列化。序列化时会调用 writeObject 写入流，反序列化时调用 readObject 重新赋值到新对象的 elementData。
- 手动序列化的原因是elementData的长度即ArrayList的容量通常大于等于ArrayList的size，我们不希望在序列化的时候将其中的空元素也序列化到磁盘中去，所以需要手动序列化数组对象,所以使用了transient来禁止自动序列化这个数组。
size：不是elementData数组的长度，而是elementData数组里包含的数据长度。没有使用volatile修饰，非线程安全。
2.3构造函数
2.3.1 ArrayList()
无参构造函数
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.3.2 ArrayList(int initialCapacity)
带参构造函数，参数为用户指定的初始容量
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
2.3.3 ArrayList(Collection<? extends E> c)
带参构造函数，参数为其他集合
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
//将集合转为 Object[] 类型数组
elementData = c.toArray();
//更新size的值，同时判断size的大小
if ((size = elementData.length) != 0) {
//c.toArray might (incorrectly) not return Object[] (see 6260652)
//这里c.toArray 返回的可能不是 Object[]，是因为继承：
//所有继承Collection的类都可以重写toArray方法，
//当子类重写父类同名的方法时，若返回值类型不一致，
//默认调用的是子类的方法,所以可能导致返回的类型不为Object[]
if (elementData.getClass() != Object[].class)
//返回类型不为Object[]则使用copeof方法拷贝一份
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
2.3.4 错误例子
当我们运行下面的代码时，会报错
public static void main(String[] args) {
ArrayList<String> list=new ArrayList<>(5);
list.add(2,"xx");
}
- 分析
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
add首先调用rangeCheckForAdd，而此时size为0，index=2>size=0，所以出错，抛出异常
- 解决方法
使用ArrayList的另一个有参构造函数
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
ArrayList<String> list=new ArrayList<>(Arrays.asList(new String[5]));
Class<ArrayList> aClass = ArrayList.class;
Field field = aClass.getDeclaredField("elementData");
field.setAccessible(true);
Object[] objects = (Object[]) field.get(list);
System.out.println("list:"+list);
System.out.println("size:" + list.size());
System.out.println("length:" + objects.length + " elementData:" + Arrays.toString(objects));
list.add(2,"xx");
System.out.println("after add");
field = aClass.getDeclaredField("elementData");
field.setAccessible(true);
objects = (Object[]) field.get(list);
System.out.println("list:"+list);
System.out.println("size:" + list.size());
System.out.println("length:" + objects.length + " elementData:" + Arrays.toString(objects));
}
使用集合构造ArrayList时，size被赋值为elementData.length，所以输出为5，再执行add函数，不会出错，并且list的size加1,变为6，而ArrayList的容量变为5*1.5=7
2.4扩容机制函数
以无参构造函数创建的 ArrayList 为例分析
2.4.1 add(E e)
添加特定的元素到集合末尾
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//尝试容量加1，检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//将元素插入到最后一位，线程不安全
elementData[size++] = e;
return true;
}
JDK11 移除了ensureCapacityInternal() 和 ensureExplicitCapacity() 方法
2.4.2 ensureCapacityInternal(int minCapacity)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
2.4.3 calculateCapacity(Object[] elementData, int minCapacity)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
- add第1个元素时，minCapacity为1，并且elementData为空数组，所以执行Math.max()方法后minCapacity为10即elementData.length=10。
- add第2个元素时，minCapacity为2，但是elementData已经不为空数组，所以不执行 Math.max()方法，minCapacity 为2。
- add第3、4...n个元素时，都不执行 Math.max()方法。
2.4.4 ensureExplicitCapacity(int minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//修改次数 +1，用于 fail-fast 机制
//当所需要的最小容量大于elementData的长度时才进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- add第 1 个元素时，minCapacity为10。此时，minCapacity-elementData.length=10-0=10>0成立，所以会执行grow方法。
- add第 2 个元素时，minCapacity 为 2。此时elementData.length(容量)在添加第一个元素后扩容成 10 了（通过grow函数中的elementData=Arrays.copyOf(elementData, newCapacity)）。此时，minCapacity - elementData.length=-8>0不成立，所以不会执行grow方法。
- 添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。
- 直到添加第11个元素，minCapacity为11，比elementData.length（为 10）要大。执行grow 方法进行扩容。
2.4.5 grow(int minCapacity)
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//将oldCapacity 右移一位，其效果相当于oldCapacity /2，
//整句运算式的结果就是将新容量更新为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//检查新容量是否大于最小需要容量，
//若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量大于MAX_ARRAY_SIZE,
//执行hugeCapacity方法比较minCapacity 和 MAX_ARRAY_SIZE，
//如果minCapacity大于最大容量，则新容量为Integer.MAX_VALUE，
//否则，新容量为MAX_ARRAY_SIZE即为Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 因为int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）。
- 奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数。
">>"（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity右移了1位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源
-
add第1个元素时，minCapacity为10，oldCapacity为0，newCapacity也为0，第一个if为真，newCapacity变为10。第二个if为假，不执行hugeCapacity方法。最后，数组elementData的长度变为10（即ArrayList的容量变为10），size 增为1。
-
add第11个元素时，minCapacity为11，oldCapacity为10，newCapacity为15，第一个if和第二个if都为假。最后，数组elementData的长度扩为15，size增为11。
补充： -
java中的length属性针对数组，如果想看这个数组的长度就用length这个属性。
-
java中的length()方法针对字符串，如果想看这个字符串的长度就用length()这个方法。
-
java中的size()方法针对泛型集合，如果想看这个泛型有多少个元素，就用size()这个方法。
2.4.6 hugeCapacity(int minCapacity)
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2.4.7 扩容总结
-
-
无参构造器使用DEFAULTCAPACITY_EMPTY_ELEMENTDAT，而对于new ArrayList(0)使用的是EMPTY_ELEMENTDATA，前者是不知道需要的容量大小，后者预估元素较少。因此ArrayList对此做了区别，使用不同的扩容算法（无参：10->15->22...，有参且参数为0：0->1->2->3->4->6->9...)。
-
JDK1.7中，没有通过两个空数组对用户行为进行区分，因此容量为0的话，会创建很多空数组new Object[0]，JDK1.8对这种情况进行了优化
//JDK 1.7
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList() {
this(10);
}
- 扩容其实就是将一个旧数组中的全部元素复制到一个长度为所需扩容大小的新数组中。所以相对来说比较消耗性能。因此阿里巴巴Java开发手册中第一章第五小节第九条建议建议我们：集合初始化时，指定集合初始值大小。
- 假设我们需要一个容量为50的ArrayList，调用它的无参构造：
- 第一次调用add方法时，进行一次扩容，此时elementData数组容量为10；
- 当元素数量小于等于10时都不会再进行扩容；
- 当元素数量大于10时，进行第二次扩容，此时elementData数组容量为15（10+5）；
- 当元素数量大于15时，进行第三次扩容，此时elementData数组容量为22（15+7）；
- 当元素数量大于22时，进行第四次扩容，此时elementData数组容量为33（22+11）；
- 当元素数量大于33时，进行第五次扩容，此时elementData数组容量为49（33+16）；
- 当元素数量大于49时，进行第六次扩容，此时elementData数组容量为73（49 + 24）；
- 也就是说我们需要一个容量为50的ArrayList，最后却得到了一个容量为73的ArrayList，这不仅浪费了空间，同时每执行一次grow()方法都会进行数组copy，这是极其消耗性能的。所以，假如我们可以提前预知元素的数量，就应该在集合初始化的时候指定其大小，以减少多次扩容带来的效率问题。
2.5 System.arraycopy()和Arrays.copyOf()方法
2.5.1 System.arraycopy()
源码
//arraycopy 是一个 native 方法
/**
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
在ArrayList中的应用
/**
*在此列表中的指定位置插入指定的元素
*/
public void add(int index, E element) {
// 调用 rangeCheckForAdd 对 index 进行界限检查
rangeCheckForAdd(index);
// 保证容量足够
ensureCapacityInternal(size + 1); // Increments modCount!!
//自己复制自己，使 index 之后的元素全部向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将element插入到index位置
elementData[index] = element;
size++;
}
测试
public static void main(String[] args) {
int[] a=new int[5];
a[0]=12;
a[1]=2;
System.arraycopy(a,1,a,2,2);
a[1]=88;
for(int i:a){
System.out.print(i+" ");
}
}
2.5.2 Arrays.copyOf()
源码
public static int[] copyOf(int[] original, int newLength) {
//申请一个新的数组
int[] copy = new int[newLength];
//调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
在ArrayList中的应用
public Object[] toArray() {
//elementData：要复制的数组；size：要复制的长度
return Arrays.copyOf(elementData, size);
}
测试
public static void main(String[] args) {
int[] a=new int[5];
a[0]=12;
a[1]=2;
a[2]=88;
a[3]=6;
a[4]=55;
int[] b= Arrays.copyOf(a,4);
for(int i:b){
System.out.print(i+" ");
}
System.out.println(b.length);
int[] c=Arrays.copyOf(a,10);
for(int i:c){
System.out.print(i+" ");
}
System.out.println(c.length);
}
可以简单认为，使用 Arrays.copyOf()方法主要是为了改变原有数组的容量
2.5.3 两者对比
-
联系
Arrays.copyOf()内部调用了System.arraycopy() -
区别
System.arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置，而Arrays.copyOf()是系统自动在内部新建一个数组，并返回该数组。
2.6 ensureCapacity(int minCapacity)
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
- 最好在add大量元素前使用ensureCapacity方法，以减少扩容的次数
测试
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法前："+(endTime - startTime));
}
public static void main(String[] args) {
ArrayList<Object> list = new ArrayList<>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("使用ensureCapacity方法后："+(endTime - startTime));
}
3.总结
- ArrayList允许存放（不止一个）null元素
- ArrayList底层是动态数组，当数组新容量超过原始集合大小时，进行扩容，扩容主要方法为grow(int minCapacity)，不支持缩容
- ArrayList是线程不安全的
- ArrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环
- 快速失败机制由modCount实现
4.主要参考博客
https://javaguide.cn/java/collection/arraylist-source-code.html#_3-4-ensurecapacity%E6%96%B9%E6%B3%95
https://juejin.cn/post/6844903582194466824#heading-13
https://www.jianshu.com/p/97874e3384ab
https://www.cnblogs.com/zhangyinhua/p/7687377.html
https://cloud.tencent.com/developer/article/1792774
https://www.cnblogs.com/ZhaoxiCheung/p/Java-ArrayList-Source-Analysis.html
https://blog.csdn.net/yuzhangzhen/article/details/108822997
https://blog.csdn.net/qq_35387940/article/details/123050667?spm=1001.2101.3001.6650.13&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-13-123050667-blog-102522476.pc_relevant_multi_platform_whitelistv2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-13-123050667-blog-102522476.pc_relevant_multi_platform_whitelistv2&utm_relevant_index=17
https://blog.csdn.net/Tian_ttt/article/details/107138504?spm=1001.2101.3001.6650.14&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-14-107138504-blog-102522476.pc_relevant_multi_platform_whitelistv2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-14-107138504-blog-102522476.pc_relevant_multi_platform_whitelistv2&utm_relevant_index=18
这篇关于ArrayList源码解析 基于JDK1.8的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门：从零开始的编程之旅
- 2024-11-23Java创业入门：新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门：初学者的简单教程
- 2024-11-23JAVA副业入门：初学者的实战指南
