当前位置： 首页 > article >正文

ArrayList 源码解析和设计思路

article 2025/1/24 22:36:32

ArrayList

  • 一、继承体系
  • 二、接口继承
  • 三、标记接口
  • 四、设计目的
  • 五、框架总体结构
  • 六、工作原理
  • 七、创建List对象初始化？还是add()添加元素初始化?
  • 七、add(E e)添加元素
  • 八、remove（int index）删除元素
  • 八、线程安全问题

一、继承体系

  • ArrayList 继承自 AbstractList,AbstractList 实现了 List 接口的部分方法,为 List 的具体实现类提供了方便。
  • AbstractList 是一个抽象类,它实现了 Collection 接口,也就间接实现了 Iterable 接口。

二、接口继承

  • List 接口继承自 Collection 接口,Collection 继承自 Iterable 接口。
  • List 接口代表有序的队列

三、标记接口

  • RandomAccess 是一个标记接口,标识 ArrayList 支持快速随机访问,可以通过索引直接访问元素。
  • Cloneable 和 Serializable 也是标记接口,前者表示可复制克隆,后者表示可序列化。

四、设计目的

  • Java 集合框架的设计目的是为了更好地对集合数据进行操作,统一了访问方式,增强了代码的可读性、简洁性和可扩展性。
  • 使用接口和抽象类来定义规范,然后由具体实现类来实现不同的数据结构和算法。
  • 标记接口则用来对类型进行标记和区分,以便采取不同的算法和优化。

五、框架总体结构

  • 最顶层是 Collection接口,定义了集合的基本操作。
  • 然后分为 List、Set、Queue 等子接口,分别定义了有序、无序、队列等特性。
  • 再通过 AbstractList、AbstractSet 等抽象类为子接口提供部分方法实现。
  • 最后是具体的实现类,如 ArrayList、LinkedList、HashMap等。

六、工作原理

ArrayList 底层是通过动态数组(可自动扩容)实现的,它的工作原理如下:

  • 初始化时,为一个初始容量为0的数组
  • 当添加元素时,容量不够则自动扩容(默认扩容为原来的1.5倍)
  • 插入和访问元素通过索引直接操作数组,性能较高
  • 删除元素需要移动其他元素以保证连续存储
  • 由于自动扩容,在末尾插入元素效率很高,但在中间位置插入效率较低

ArrayList 的源码注释如下:

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

/**
 * 用于储存元素的数组缓冲区
 */
transient Object[] elementData; 

/**
 * ArrayList 中元素的数量
 */
private int size;

// 其他方法...

可以看出，ArrayList 内部通过一个 Object 数组存储元素,size 变量记录当前元素数量,通过自动扩容机制来支持动态增长。这种基于动态数组的实现,决定了 ArrayList 查询快、增删慢的特点。

七、创建List对象初始化？还是add()添加元素初始化?

在 Java JDK 1.8 中,ArrayList 的默认初始容量 10 是在第一次通过无参构造函数创建 ArrayList 对象时初始化的,而不是在添加第一个元素时初始化。

ArrayList 有三种构造方式:

  1. ArrayList()

    /**
 * 构造一个初始容量为10的空列表
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

    使用无参构造函数时,底层会初始化一个初始容量为 10 的空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

  2. ArrayList(int initialCapacity)

    /**
 * 构造一个具有指定初始容量的空列表
 */
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);
    }
}

    使用这个指定容量的构造函数,会根据指定的容量初始化底层数组大小。

  3. ArrayList(Collection<? extends E> c)

    /**
 * 构造一个包含指定collection的元素的列表,按迭代器返回元素的顺序
 */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray可能(错误地)不同时使用Object[]...
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 使用空数组替换以允许缓冲区进行正常增长
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

    使用这个构造函数会根据提供的集合的大小创建底层数组。

使用无参构造函数 ArrayList() 时,底层数组的初始容量才会被初始化为 10。其他两种构造函数要么根据用户指定的容量初始化,要么根据提供的集合大小初始化。而添加元素时则不会再初始化容量,只是在容量不足时按照需求扩容。

七、add(E e)添加元素

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

  1. ensureCapacityInternal(size + 1): 这一行代码调用了ensureCapacityInternal方法，它用于确保ArrayList内部数组的容量足够来存放新增的元素。如果需要增加ArrayList的容量，它会创建一个新的更大的数组，并将原来的元素复制到新数组中。

  2. elementData[size++] = e;: 这一行代码将新的元素e添加到ArrayList的内部数组elementData中，并且将size变量递增，表示列表中的元素数量增加了一个。这里使用size++是因为要先将元素添加到size所指示的位置，然后再递增size，以便下次添加元素时能够添加到正确的位置。

  3. return true;: 最后，方法返回true，表示添加操作成功。

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

这段代码是ArrayList中的ensureCapacityInternal(int minCapacity)方法的部分源码

  1. if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {: 这一行代码用于检查elementData是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，该常量表示一个空数组。如果是空数组，说明当前ArrayList没有初始化容量，需要根据默认容量和需要添加的最小容量来确定实际容量。

  2. minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);: 如果elementData是空数组，则会根据默认容量DEFAULT_CAPACITY和需要添加的最小容量来确定实际的最小容量。DEFAULT_CAPACITY是ArrayList默认的初始容量大小。

  3. ensureExplicitCapacity(minCapacity);: 接下来调用ensureExplicitCapacity(minCapacity)方法来确保ArrayList的内部数组容量能够容纳至少minCapacity个元素。这个方法会比较当前数组的容量和需要的最小容量，如果当前容量不足，则会扩大内部数组的容量以满足需求。

   private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

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

-这段代码是ArrayList中的ensureExplicitCapacity(int minCapacity)方法的部分源码

  1. modCount++;: 这一行代码递增了modCount变量的值。modCount用于记录结构修改次数，主要用于在迭代过程中检测并发修改。每当进行结构性修改时（如添加或移除元素），modCount会递增，表示ArrayList的结构发生了变化。

  2. if (minCapacity - elementData.length > 0) grow(minCapacity);: 这里使用了溢出安全的计算方式来判断是否需要扩容内部数组。如果当前容量不足以容纳最小容量minCapacity个元素，则需要调用grow(minCapacity)方法来扩大内部数组的容量。

  3. grow(int minCapacity): 当需要扩容时，会调用grow(int minCapacity)方法来实现容量的扩充。grow()方法会根据需要的最小容量来确定新的容量大小，并将原来的元素复制到新的更大的数组中。

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        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);
    }

这段代码是ArrayList中的grow(int minCapacity)方法的部分源码

  1. int oldCapacity = elementData.length;: 获取当前内部数组的容量，即原来的容量大小。

  2. int newCapacity = oldCapacity + (oldCapacity >> 1);: 原来的容量大小计算出新的容量大小。新的容量大小会是原来容量的1.5倍，通过右移一位实现了除以2的操作。原来容量大小 + 容量大小的一半

  3. if (newCapacity - minCapacity < 0) newCapacity = minCapacity;: 如果新的容量仍然小于需要的最小容量minCapacity，则将新的容量调整为minCapacity，确保容量能够满足需求。

  4. if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);: 检查新的容量是否超出了最大数组大小MAX_ARRAY_SIZE，如果超出则调用hugeCapacity()方法来确定合适的容量大小，这是为了避免数组大小超出Java虚拟机的限制。

  5. elementData = Arrays.copyOf(elementData, newCapacity);: 最后，使用Arrays.copyOf()方法将原来的元素复制到新的更大的数组中，完成了内部数组的扩容过程。

grow()方法主要负责处理ArrayList内部数组的扩容问题。它会根据旧的容量大小计算出新的容量大小，并根据需要调整为满足最小容量要求的合适大小。然后将原来的元素复制到新的更大的数组中，完成数组的扩容操作。这样可以确保在需要添加大量元素时，ArrayList内部数组能够容纳足够多的元素。

八、remove（int index）删除元素

    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; // clear to let GC do its work

        return oldValue;
    }

这段代码是ArrayList中的remove(int index)方法的部分源码

  1. rangeCheck(index): 这一行代码调用了rangeCheck方法来检查索引是否越界，确保要移除的元素在有效范围内。如果索引不在有效范围内，会抛出IndexOutOfBoundsException。

  2. modCount++: 这里递增了modCount变量的值。modCount用于记录结构修改次数，主要用于在迭代过程中检测并发修改。每当进行结构性修改时（如添加或移除元素），modCount会递增，表示ArrayList的结构发生了变化。

  3. E oldValue = elementData(index): 这一行代码获取要移除的元素，并将其保存为oldValue。

  4. int numMoved = size - index - 1;: 计算需要向前移动的元素个数，即原始数组中位于被删除元素后面的元素个数。

  5. System.arraycopy(elementData, index+1, elementData, index, numMoved): 如果存在需要向前移动的元素，则使用System.arraycopy方法将这些元素向前移动，以填补被删除元素的位置。

  6. elementData[--size] = null: 将列表中最后一个元素置空，以便让GC进行清理工作。

  7. 返回oldValue：返回被删除的元素的值。

通过以上步骤，remove()方法实现了在指定位置上删除元素的功能。它首先进行了参数的合法性检查，然后递增了modCount，接着移动需要向前移动的元素，将列表中最后一个元素置空，并返回被删除的元素的值。

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

这段代码是ArrayList中的remove(Object o)方法的部分源码

  1. 如果传入的对象 o 为空（null）：

    • 通过 for 循环遍历 elementData 数组，寻找为 null 的元素。
    • 当找到第一个为 null 的元素后，调用 fastRemove(index) 方法进行删除，并返回 true。

  2. 如果传入的对象 o 不为空（non-null）：

    • 通过 for 循环遍历 elementData 数组，寻找与传入对象相等的元素。
    • 当找到第一个与传入对象相等的元素后，调用 fastRemove(index) 方法进行删除，并返回 true。

  3. 如果未找到符合条件的元素，则直接返回 false。

fastRemove(index) 方法用于快速删除指定索引位置的元素。通过这种方式，remove(Object o) 方法能够在列表中移除满足特定条件的第一个元素，并返回是否成功移除的布尔值。

八、线程安全问题

ArrayList存在线程安全问题的本质在于其内部的elementData、size和modCount等变量，在进行各种操作时没有加锁，并且这些变量的类型也不是volatile的。因此，如果多个线程对这些变量进行操作，则可能出现值被覆盖的情况。需要强调的是，只有当ArrayList作为共享变量时，才会出现线程安全问题；当ArrayList是方法内的局部变量时，则不存在线程安全问题。


http://www.kler.cn/a/271935.html

相关文章：

  • Unity编辑拓展显示自定义类型
  • Django 的 `Meta` 类和外键的使用
  • AI Agent：数字文明的暗物质，如何悄然改变我们的世界？
  • 【2024 博客之星评选】请继续保持Passion
  • map和set的使用（一）详解
  • RK3568笔记七十七：RTMP实时推流
  • python-0008-修改django数据库为mysql
  • Docker入门二（应用部署、迁移与备份、DockerFile、docker私有仓库、Docker-Compose）
  • 泽众云真机-机型支持ADB调试功能即将上线
  • SpringBoot 中配置日期格式
  • springboot/ssm电子印章管理系统Java印章审批信息管理系统web
  • DDos攻击如何被高防服务器有效防范？
  • （三）OpenOFDM符号对齐
  • 嵌入式学习39-程序创建数据库及查找
  • 网络安全JavaSE第二天（持续更新）
  • [Golang]K-V存储引擎的学习 从零实现 （RoseDB mini版本）
  • 微信小程序（一）
  • Linux字符设备驱动开发一
  • HarmonyOS-鸿蒙系统概述
  • 0基础 三个月掌握C语言（11）
  • 代码算法训练营day9 | 28. 实现 strStr() 、459.重复的子字符串
  • linux gcc使用方法
  • 数据结构——lesson8二叉树的实现
  • OpenCV4.9.0在windows系统下的安装
  • zookeeper基础学习之六: zookeeper java客户端curator
  • 【图论】计算图的n-hop邻居个数，并绘制频率分布直方图