• 多图深度解析ArrayList源码

    文章目录

    1. 概述

    ArrayList 可以说是实际开发过程中使用最多的数据结构，我们有必要深究其原理，以便更好的提升它的效率。

    1.1 特性

    • 顺序容器：写入和读出的顺序是一致的
    • 允许存储重复值，允许你存储null值
    • 容量不足时，容器会自动增大底层数组的大小

    1.2 存储结构

    在这里插入图片描述

    2. 使用

    2.1 代码

    import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;
import java.util.ArrayList;
import java.util.Arrays;

@RunWith(SpringRunner.class)
@SpringBootTest
public class ArrayListTest {
    @Test
    public void test() {
        ArrayList<Integer> arr = new ArrayList<>();
		// size()获取到的是元素的个数
        System.out.println("默认大小： " + arr.size());

        arr.add(1);
        arr.add(2);
        arr.add(1);
        arr.addAll(Arrays.asList(5, 6));

        System.out.println("写入之后的大小： " + arr.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

    2.2 输出

    默认大小： 0
写入之后的大小： 5

    • 1
    • 2

    3. 类关系

    3.1 UML类图

    在这里插入图片描述

    4. ArrayList的实现

    4.1 类属性

    	/**
     * 初始默认数组容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 多个空 ArrayList实例之间共享的 空数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 将其与 EMPTY_ELEMENTDATA 区分开来，以便知道添加第一个元素时扩充多少
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 当 elementData  添加了第一个元素之后，容量就会被扩充到 DEFAULT_CAPACITY （10）个
 	 *
	 *	transient作用：不让elementData被序列化
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList 的大小（实际存储的元素个数）
     */
    private int 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

    4.2 构造方法

    	/**
     * 指定容量
     *
     */
    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);
        }
    }

    /**
     * 默认容量为10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 传入集合，可初始化元素
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 使用空数组代替
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    • 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

    5. 扩容机制

    5.1 自动扩容

    有一下两要点：

    • 每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容
    • 在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量

    使用时候注意：

    1. 当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量
    2. 根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
    	/**
     * @param   minCapacity   期望的最小容量
     */
    public void ensureCapacity(int minCapacity) {
    	// 从当前的元素中，计算最小的扩展个数
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // 不是空数组（说明已经有元素了），就先不扩展
            ? 0
            // 元素个数为10
            : DEFAULT_CAPACITY;
		// 要扩展的容量多于最小扩展量才进行扩展
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
	
	/**
	* 计算最小容量
	*/
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

	/**
	* 当最小容量大于当前元素大小时，进行扩容
	*/
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * ArrayList的最多元素个数  2147483639
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
	 * 扩充容量，确保数组能够至少可存 minCapacity 个元素
     */
    private void grow(int minCapacity) {
        // 数组原始个数
        int oldCapacity = elementData.length;
        /**
        * 比如原始 oldCapacity == 10（二进制为 1010）
        * 1010 >> 1 等价于 0101 （十进制为5）；PS: 整数进行位右移相当于除以2
        * 那么新的容量就是 10 + 5 = 15；相当于1.5倍扩充
        */
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

	/**
	* 确保最大容量也只能是 MAX_ARRAY_SIZE 值
	*/
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76

    以上逻辑可以展示为如图所示：
    在这里插入图片描述

    5.2 添加单个元素

    • add(E e)
    • add(int index, E element)

    这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

    5.2.1 追加 (E e)

    直接在数组当前最后一个元素后添加。

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return true (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    modCount：
    表明list被结构化修改的次数，存在于 java.util.AbstractList 中，定义方式：protected transient int modCount = 0;， 该字段由迭代器和列表迭代器实现使用，提供 fail-fast 机制。

    结构化修改的形式：

    • 指改变列表的大小。
    • 以某种方式干扰列表，使得正在进行的迭代可能产生不正确的结果。

    在这里插入图片描述

    5.2.2 追加到指定索引位置

    此种方式需要对索引位置之后的元素进行移动。

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
    	// 校验 index > size || index < 0，防止越界
        rangeCheckForAdd(index);
		
		
        ensureCapacityInternal(size + 1);  // 增加 modCount!!
        // 从指定的源数组复制数组，从指定位置到目标数组的指定位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    在这里插入图片描述

    5.3 添加多个元素

    在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。 addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。

    addAll(Collection c)

     /**
     * 如果在操作过程中修改了指定集合，则此操作的行为未定义。
     * （这意味着如果指定的集合是该列表，并且该列表是非空的，则该调用的行为是未定义的
     *
     * @param 待加入的集合
     * @return list改变之后返回 true
     * @throws 集合未定义则抛出 NullPointerException
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        // 要添加的长度
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // 增加 modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    addAll(int index, Collection c)

    	/**
     *
     * @param 插入位置
     * @param 待添加的集合
     * @return list改变之后返回 true
     * @throws index 越界则抛出 IndexOutOfBoundsException
     * @throws 集合未定义则抛出 NullPointerException
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
		// 要移动的数量
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    5.4 赋值/更改 set()

    /**
     * 替换指定索引处的值
     *
     * @param index指定要改哪个值
     * @param 元素值
     */
    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    5.5 获取指定索引处的值

        public E get(int index) {
    	// 判断 index >= size
        rangeCheck(index);

        return elementData(index);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    5.6 删除指定索引处的值

     	/**
     * 删除该值后，元素左移动
     */
    public E remove(int index) {
        rangeCheck(index);
		
		// 删除也增加更改次数
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // 将最后一个元素设置为null，让GC生效

        return oldValue;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。

    5.7 调整容量为当前数组大小

    	/**
     *最小化ArrayList的容量
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    5.8 查找元素

    indexOf()

    /**
     * 查找元素第一次出现的位置
     * 
     */
    public int indexOf(Object o) {
    	// ArrayList 可以存null值，所以要判断
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
        	// 从头开始找
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    lastIndexOf()

    /**
     * 查找元素最后一次出现的位置
     */
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
        	// 从尾开始找
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    6. Fail-Fast机制

    ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

    参考文档：
    https://pdai.tech/md/java/collection/java-collection-ArrayList.html

  • 相关阅读:
    【QT+JS】QT和JS 中的正则表达式 、QT跑JS语言
    paddleocr的cpp_infer在Liunx下编译部署
    《Linux内核精通》笔记参考目录
    JavaEE初阶——多线程(七)——定时器
    【异常、线程】全网最详细解读
    跨库查询问题
    Android GKI 架构简介
    Chromium浏览器启动参数
    【web-攻击访问控制】(5.2.1)攻击访问控制：不同用户账户进行测试、测试多阶段过程
    vue 后端返回二进制流-前端通过blob对象下载文件-图片
  • 原文地址：https://blog.csdn.net/oschina_41731918/article/details/126840316