知新_RL

这个屌丝很懒，什么也没留下！

热门标签

ArrayList 万字长文解析：使用、优化、源码分析_java.util.arraylist.rangecheck(arraylist.java:659)

作者：知新_RL | 2024-06-28 15:20:01

踩

java.util.arraylist.rangecheck(arraylist.java:659)

文章目录

ArrayList 万字长文解析：使用、优化、源码分析

ArrayList 万字长文解析：使用、优化、源码分析

ArrayList 万字长文解析使用、优化、源码分析

前言

大家好，这里是 Rocky 编程日记，一位喜欢后端架构及中间件源码的CSDN博主，该篇文章主要是对 Java 集合框架体系下 ArrayList的一个解析。

梳理出来也是想和大伙探讨一下这块内容，同时也供大家学习交流，如若笔记中有不对的地方，那一定是我的理解还不够，希望你大胆的在评论区指出来噢~。

同时，如果对于该笔记存在很多疑惑，也欢迎和我交流讨论，最后也感谢您的阅读，嘿嘿，期待你的点赞，关注，收藏噢~。

前人述备矣，我只是知识的搬运工，ArrayList 文中代码示例皆在开源代码仓库中，源代码仓库地址为: https://gitee.com/Rocky-BCRJ/java-diary.git。欢迎star~。

同时，本文只是对 ArrayList 核心方法的一些讲解，如果有一些相关方法未讲解到的，欢迎评论区留言讨论，后续我也会把 JDK 注释的开源代码同步出来，敬请期待~。

ArrayList 简介

ArrayList 是一种动态数组，可以在运行时自动扩展容量。它可以存储任何类型的对象，并提供高效的随机访问和快速的插入/删除操作。ArrayList 有以下优点：

高效的随机访问：ArrayList 内部使用数组实现，因此可以通过下标快速访问任意元素。
动态扩容：ArrayList 可以在运行时自动扩展容量，因此可以存储任意数量的元素。
可以存储任何类型的对象：ArrayList 可以存储任何类型的对象，包括基本类型和自定义类型。
支持插入/删除操作：ArrayList 内部使用数组实现，因此可以通过移动元素来实现插入和删除操作。

然而，ArrayList 也有一些缺点：

插入和删除操作可能会导致数组元素的移动，因此在大量插入和删除操作时，ArrayList 的性能可能会受到影响。
ArrayList 内部使用数组实现，因此在插入和删除操作时，可能需要重新分配数组空间，这可能会导致性能下降。
ArrayList 只能存储对象，不能存储基本类型，因此需要将基本类型包装成对象，这可能会导致一些额外的开销。

ArrayList 的基本使用方法

该段介绍 ArrayList 的基本操作，如添加、删除、遍历等。

package cn.rocky.other;

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayListDemo {

    public static void main(String[] args) {
        // 创建 ArrayList 对象
        ArrayList<String> list = new ArrayList<>();

        // 添加元素
        list.add("Java");
        list.add("Python");
        list.add("C++");

        // 获取元素
        System.out.println("第二个元素是：" + list.get(1));

        // 修改元素
        list.set(1, "JavaScript");
        System.out.println("修改后的第二个元素是：" + list.get(1));

        // 删除元素
        list.remove(0);
        System.out.println("删除后的第一个元素是：" + list.get(0));

        System.out.println("for遍历元素：");
        // for
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }

        System.out.println();
        System.out.println("for each 遍历元素：");
        // for each 遍历元素
        for (String s : list) {
            System.out.print(s + " ");
        }

        System.out.println();
        System.out.println("迭代器遍历元素：");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.print(element + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

ArrayList 性能优化

当使用 ArrayList 时，可以考虑以下性能优化技巧：

指定 ArrayList 的初始容量：在创建 ArrayList 时，可以指定其初始容量，这可以避免在添加元素时频繁地扩展数组。例如，如果预计 ArrayList 中将包含 100 个元素，可以使用以下代码创建 ArrayList：

ArrayList<String> list = new ArrayList<>(100);
1

使用 Iterator 迭代器遍历 ArrayList：使用 Iterator 迭代器遍历 ArrayList 可以避免使用 for 循环时频繁地调用 get() 方法。例如：

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    // do something with element
}
1
2
3
4
5

使用 for-each 循环遍历 ArrayList：使用 for-each 循环遍历 ArrayList 可以使代码更加简洁，也可以避免使用 for 循环时频繁地调用 get() 方法。例如：

for (String element : list) {
    // do something with element
}
1
2
3

使用 toArray() 方法将 ArrayList 转换为数组：如果需要频繁地访问 ArrayList 中的元素，可以使用 toArray() 方法将 ArrayList 转换为数组，以提高访问速度。例如：

String[] array = list.toArray(new String[0]);
1

使用 subList() 方法获取子列表：如果需要对 ArrayList 中的部分元素进行操作，可以使用 subList() 方法获取子列表，以避免对整个 ArrayList 进行操作。例如：

List<String> subList = list.subList(0, 10);
// do something with subList
1
2

这些技巧可以帮助提高 ArrayList 的性能，但需要根据具体情况进行选择。在实际使用中，还需要考虑其他因素，比如数据量、操作频率等。

ArrayList 的源码分析

在这一部分中，我们将深入分析 ArrayList 的源码，以深入理解其实现原理和性能特点。我们将会讨论 ArrayList 的内部结构、扩容机制、迭代器实现等重要内容。

内部结构

数组元素：ArrayList 内部使用 Object 类型的数组来存储元素，可以通过数组下标来访问元素。
元素数量：ArrayList 中的元素数量，也就是当前数组中实际存储的元素数量。
容量大小：ArrayList 中数组的容量大小，也就是数组能够存储的最大元素数量。当元素数量超过容量大小时，ArrayList 会自动扩容。
修改次数：ArrayList 中记录修改次数的变量，用于在迭代器遍历时检测是否有其他线程对 ArrayList 进行修改。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 默认初始化容量 10
		private static final int DEFAULT_CAPACITY = 10;
	  // 共享的空数组对象
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 共享的空数组对象 
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 思考？ 这里为啥要加 transient。
    // 存储 ArrayList 中元素的数组
    transient Object[] elementData; 
		// 实际存储的元素数量
    private int size;
    // 父类的元素
    // modCount 变量表示 ArrayList 的结构修改次数，
    // 用于在迭代器遍历时检测是否发生了结构性修改，如果发生了则抛出 ConcurrentModificationException 异常
    protected transient int modCount = 0;
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

构造方法解析

		// 默认构造函数
		public ArrayList() {
        // 将 elementData 成员变量初始化为一个空数组，表示 ArrayList 的初始容量为 0。
        // 当第一个元素被添加到 ArrayList 中时，elementData 数组会被扩容成默认容量 10。
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
1
2
3
4
5
6

		public ArrayList(int initialCapacity) {
        // 初始化容量大于 0 时，创建 Object 数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        }
         // 初始化容量等于 0 时，使用 EMPTY_ELEMENTDATA 对象
        else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } 
        // 初始化容量小于 0 时，抛出 IllegalArgumentException 异常
        else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

		public ArrayList(Collection<? extends E> c) {
      	// 将 集合 c 转换成 Object 数组。 思考？这里能用 elementData去接么 element = c.toArray(); 
        Object[] a = c.toArray();
      	// 数组包含 元素时(length != 0)
        if ((size = a.length) != 0) {
            // 类型为 ArrayList,直接赋值
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } 
            // 集合元素不是 Object[] 类型，则会创建 新的 Object[] 数组，并将 元素赋值到其中，最后赋值给 elementData。 
            else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } 
        // 如果数组中不包含 元素时(length == 0),则使用 EMPTY_ELEMENTDATA 。
        else {
            elementData = EMPTY_ELEMENTDATA;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

扩容机制

 		public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 加元素
        elementData[size++] = e;
        return true;
    }
1
2
3
4
5
6

		private void ensureCapacityInternal(int minCapacity) {
	// 计算 calculate 得到的容量大小 ，判断是否需要进行扩容 
      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
1
2
3
4

    // 计算容量 1.当前数组 2.minCapacity = size + 1
		private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果当前数组等于{}, 返回默认初始化大小 10;
      	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
      	// 返回 size + 1;
        return minCapacity;
    }
1
2
3
4
5
6
7
8
9

		private void ensureExplicitCapacity(int minCapacity) {
        // 修改次数 +1
      	modCount++;

        // overflow-conscious code
      	// 需要的minCapacity容量大于数组元素长度，则需要进行扩容
        if (minCapacity - elementData.length > 0)
          	// 扩容
            grow(minCapacity);
    }
1
2
3
4
5
6
7
8
9
10

	 // 扩容方法	
	 private void grow(int minCapacity) {
        // overflow-conscious code 
     		// 意思是指在编写代码时考虑数据溢出的情况，避免因为数据溢出而导致程序出错或崩溃。
     		// 例如，在进行数值计算时，如果结果超出了数据类型的范围，就会发生数据溢出，此时就需要使用 overflow-conscious code 来避免这种情况。
     	  // 旧数组容量大小,也即当前数组容量
        int oldCapacity = elementData.length;
     	  // 计算新数组容量，新数组容量 = 旧数组容量 + 1/2旧数组容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新数组容量小于最小容量，则将最小容量作为新的数组容量
     		if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果新的数组容量超过了数组最大容量(Integer.Max - 8)，则调用 hugeCapacity 方法进入扩容
      	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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

		// 计算扩容的最大容量, 在 Java 中，数组的最大长度是 Integer.MAX_VALUE, hugeCapacity 方法就能保证在扩容时，不会超过数组的最大长度限制。
		private static int hugeCapacity(int minCapacity) {
        // 传入的 minCapacity 小于 0，抛出 oom
      	if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 如果 minCapacity 大于 MAX_ARRAY_SIZE，则返回 Integer.MAX_VALUE，否则返回 MAX_ARRAY_SIZE。
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
1
2
3
4
5
6
7
8
9
10

System.arraycop与 Arrays.copyof 实现方式与使用场景

System.arraycopy() 和 Arrays.copyOf() 都可以用来复制一个数组，但是它们的实现方式和使用场景略有不同。

System.arraycopy() 是一个本地方法，它可以快速地将一个数组的一部分复制到另一个数组中的指定位置。它的语法如下：

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
1

其中，src 是源数组，srcPos 是源数组中要复制的起始位置，dest 是目标数组，destPos 是目标数组中要复制到的起始位置，length 是要复制的元素数量。

Arrays.copyOf() 是一个静态方法，它可以将一个数组复制到一个新的数组中，并且可以指定新数组的长度。它的语法如下：

public static <T> T[] copyOf(T[] original, int newLength);

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
1
2
3
4
5
6
7
8
9
10
11

其中，original 是要复制的原始数组，newLength 是新数组的长度。

总的来说，System.arraycopy() 适用于需要高效复制数组的场景，而 Arrays.copyOf() 则更适用于需要创建一个新数组并且长度不确定的场景。另外，Arrays.copyOf() 还支持将原始数组的元素类型转换为另一种类型，而 System.arraycopy() 不支持。

迭代器

迭代器的作用：迭代器是一种用于遍历集合类中元素的工具，它可以让我们轻松地遍历 ArrayList 中的元素，而不需要使用传统的 for 循环或者 foreach 循环。
迭代器的使用方法：通过调用 ArrayList 的 iterator() 方法可以获取一个迭代器对象，然后可以使用 hasNext() 方法和 next() 方法来遍历 ArrayList 中的元素。需要注意的是，在使用迭代器遍历元素时，不能直接使用 ArrayList 的 get() 方法获取元素。
迭代器的优点：相比传统的 for 循环或者 foreach 循环，使用迭代器遍历集合类中的元素有以下几个优点：
- 可以在遍历过程中删除元素，而不会出现 ConcurrentModificationException 异常。
- 可以遍历所有实现了 Iterable 接口的集合类，而不需要关心具体的集合类型。
- 可以避免使用索引来访问元素，从而避免出现数组越界等异常。
迭代器的缺点：使用迭代器遍历集合类中的元素也有一些缺点：
- 不能在遍历过程中修改元素，否则会出现 ConcurrentModificationException 异常。
- 遍历过程中不能向集合中添加新的元素，否则会导致遍历不完整。

JDK 8版本 ArrayList bug 示例

public class TestList {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3);
        Object[] array = list.toArray();
        // JDK8 返回 Integer[] 数组，JDK9+ 返回 Object[] 数组。
        System.out.println("class name : " + array.getClass().getSimpleName());
        // JDK 8 和 JDK9+ 表现不同, 前者会报 ArrayStoreException 异常, 后者不会 
        array[0] = new Object();
    }
}
1
2
3
4
5
6
7
8
9
10
11

ArrayList 使用注意事项代码演示

当使用 subList() 方法获取 ArrayList 的子列表时，返回的是一个新的列表对象，但是它与原来的列表对象共享同一个数据存储区域，也就是说，对子列表的修改会影响到原来的列表对象。如果在对子列表进行修改的同时，原来的列表对象也被修改了，就会导致 ConcurrentModificationException 异常的抛出。

package cn.rocky.other;

import java.util.ArrayList;
import java.util.List;

public class TestList04 {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        List<String> subList = list.subList(0, 2);

        list.add("D"); // 修改原列表

        subList.clear(); // 修改子列表

        // 此时会抛出 ConcurrentModificationException 异常
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

结果如下:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1241)
	at java.util.ArrayList$SubList.size(ArrayList.java:1050)
	at java.util.AbstractList.clear(AbstractList.java:234)
	at cn.rocky.other.TestList04.main(TestList04.java:18)
1
2
3
4
5

多线程环境下操作 ArrayList 也会出现一些其妙的问题，代码如下:

package cn.rocky.other;

import java.util.ArrayList;

public class TestList05 {
    public static void main(String[] args) throws InterruptedException {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            list.add(i);
        }

        Thread thread1 = new Thread(() -> {
            for (int i = 0; i < 500; i++) {
                list.remove(i);
            }
        });

        Thread thread2 = new Thread(() -> {
            for (int i = 0; i < 500; i++) {
                list.remove(i);
            }
        });

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();

        System.out.println(list.size());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32