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

探秘 ArrayList：源码剖析与扩容策略

news 2024/10/23 19:50:08

#1024程序员节 | 征文#

在这里插入图片描述

基本介绍

ArrayList是Java中的一个集合类，这篇文章就先由ArrayList和Array的区别开始吧!

  • Array是一个静态数组，ArrayList是一个动态数组（可扩容）
  • Array可以存储基本数据类型和引用数据类型，ArrayList只能存储引用数据类型（可以用包装类）
  • Array只能通过下标获取值，ArrayList有丰富的api增删。
  • ArrayList支持泛型

在了解了这些内容后，你一定会好奇 ArrayList 是如何实现动态长度的。本文将分为两个章节：源码分析和扩容机制。对于已有源码阅读基础的读者，可以直接阅读源码分析章节来深入了解扩容机制；而对于刚开始学习 Java 的朋友，建议先阅读扩容机制章节，然后再回过头来阅读源码部分。

源码分析

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private static final long serialVersionUID = 8683452581122892189L;/*** 默认初始容量*/private static final int DEFAULT_CAPACITY = 10;/*** 如果你传入0构造0大小的数组，就返回这个给你。*/private static final Object[] EMPTY_ELEMENTDATA = {};//当你无参构造后返回这个默认的给你，再你传入第一个值后去扩容private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 保存ArrayList数据的数组，transient：不进行序列化*/transient Object[] elementData; /*** ArrayList 所包含的元素个数*/private int size;/*** 通过有参构造用户可以自定义ArrayList数组的大小*/public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//如果传入的参数大于0，创建参数大小的数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//如果传入的参数等于0，创建空数组//EMPTY_ELEMENTDATA是提前创好的，避免在创建空数组时浪费不必要的内存。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();//如果elementData数组的长度不为0if ((size = elementData.length) != 0) {// 如果elementData不是Object类型数据if (elementData.getClass() != Object[].class)//将原来不是Object类型的elementData数组的内容，赋值给新的Object类型的elementData数组elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// 如果传入集合长度为0，返回空数组。this.elementData = EMPTY_ELEMENTDATA;}}/*** 如果ArrayList中的元素比当前数组容量少，就会减少数组的大小。* 当大量清理数据后调用此方法节省内存。*/public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}//扩容机制/***	作用：在添加大量元素之前扩容，从而避免每次添加元素前都引发数组的扩容增大性能开销*/public void ensureCapacity(int minCapacity) {//如果存储数据的数组不是空数组，则minExpand为0，否则为10int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0: 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) {//calculateCapacity(elementData, minCapacity)，计算当前所需的最小容量ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}//判断是否需要扩容private void ensureExplicitCapacity(int minCapacity) {modCount++;// 如果所需最小容量大于数组的长度就扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}/*** 要分配的最大数组大小* 为什么要减8，是因为java中每个对象都有一个对象头，通常对象头的开销为8字节。所以最大存储大小要减去8.*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** ArrayList扩容的核心。*/private void grow(int minCapacity) {// oldCapacity为旧容量，newCapacity为新容量int oldCapacity = elementData.length;//扩容到旧容量的1.5倍//将oldCapacity 右移一位，其效果相当于oldCapacity /2，int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容后检查一下扩完的容量是否满足需求，如果还是不够需要容量的话直接把需要的容量赋值给new数组容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//再检查新容量是否超出了ArrayList所定义的最大容量，//若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//把旧数组copy到新数组中elementData = Arrays.copyOf(elementData, newCapacity);}//比较minCapacity和 MAX_ARRAY_SIZE确保传入的数合理，确保创建的数组是在JVM能处理的范围中。//如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

扩容机制

ArrayList的创建

无参
    /*** Shared empty array instance used for default sized empty instances. We* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when* first element is added.*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

有的同学会说ArrayList的默认空间不是10吗?怎么无参构造返回的是空数组?

当你调用无参构造方法初始化ArrayList，会返回给你一个默认创建好的空数组。等到你添加第一个元素进去的时候他才会扩容到默认容量（一般是10）。

为什么空数组提前创建好了？

为了避免初始化ArrayList时创建空数组的性能开销。

有参
	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);}}

当你用有参构造方法初始化ArrayList，那它会帮你创建一个对应大小的数组。

ArrayList的扩容

add

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

调用add方法后会调用ensureCapacityInternal方法并传入当前集合的长度。

ensureCapacityInternal

	private void ensureCapacityInternal(int minCapacity) {//calculateCapacity(elementData, minCapacity)，计算当前所需的最小容量ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}// 根据给定的最小容量和当前数组元素来计算所需容量。private static int calculateCapacity(Object[] elementData, int minCapacity) {// 如果当前数组是默认的空数组，那么返回默认容量和所需空间的最大值。if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}// 否则直接返回最小容量return minCapacity;}

根据calculateCapacity计算当前集合所需列表，然后再传入ensureExplicitCapacity中。

ensureExplicitCapacity

	//判断是否需要扩容private void ensureExplicitCapacity(int minCapacity) {modCount++;// 如果所需最小容量大于数组的长度就扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}

如果需要容量小于集合长度就进行扩容

核心方法：grow

	/*** ArrayList扩容的核心。*/private void grow(int minCapacity) {// oldCapacity为旧容量，newCapacity为新容量int oldCapacity = elementData.length;//扩容到旧容量的1.5倍//将oldCapacity 右移一位，其效果相当于oldCapacity /2，int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容后检查一下扩完的容量是否满足需求，如果还是不够需要容量的话直接把需要的容量赋值给new数组容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//再检查新容量是否超出了ArrayList所定义的最大容量，//若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//把旧数组copy到新数组中elementData = Arrays.copyOf(elementData, newCapacity);}//比较minCapacity和 MAX_ARRAY_SIZE确保传入的数合理，确保创建的数组是在JVM能处理的范围中。//如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}
  1. 通过位运算把长度扩为原来的1.5倍。
  2. 判断当前容量是否够用，如不够直接将所需容量赋给newCapacity
  3. 判断当前容量是否超出MAX_ARRAY_SIZE（ArrayList最大容量），未超出就扩容到MAX_ARRAY_SIZE。

MAX_ARRAY_SIZE

	/*** 要分配的最大数组大小* 为什么要减8，是因为java中每个对象都有一个对象头，通常对象头的开销为8字节。所以最大存储大小要减去8.*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

对象头开销: 在 Java 中，每个对象（包括数组）都有一个对象头，用于存储对象的元数据。这个对象头的大小通常为 8 字节（在 64 位 JVM 中）。因此，为了保证有效的数组大小，必须考虑到这个开销。

为了防止数组溢出，需要确保数组创建时能容纳头部的开销。

ensureCapacity

	/***	作用：在添加大量元素之前扩容，从而避免每次添加元素前都引发数组的扩容增大性能开销*/public void ensureCapacity(int minCapacity) {//如果存储数据的数组不是空数组，则minExpand为0，否则为10int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY;//如果存储数据需要的容量大于已有的空间if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);}}

预防扩容: 通过在添加新元素之前确保容量，ensureCapacity 可以减少动态扩容的频率，从而避免在每次添加元素时都引发数组复制的性能开销。


http://www.mrgr.cn/news/57019.html

相关文章：

  • 汽车3d动画效果怎么样？云渲染提升汽车营销体验
  • STM32_实验5_中断实验
  • 机器学习1
  • 系统性能优化——绑核
  • Android 通过计算器暗码启动应用
  • C++类和对象之对象模型和this指针
  • 虚拟内存与物理内存：计算机存储系统的核心要素
  • ETLCloud搭配MySQL | 让关系型数据库更智能
  • 中国云厂出海：如何绕过暗礁，找到宝藏？
  • vue3.0 + vite打包完成后，将dist下的资源包打包成zip
  • 用哪种建站程序做谷歌SEO更容易？
  • DAG和Steps
  • C++ 红黑树
  • 接口测试 —— Postman 变量了解一下！
  • 提高爬虫性能的 5 个关键技巧：从并发到异步执行
  • 【Linux】僵尸进程和孤儿进程
  • 【算法笔记】前缀和算法原理深度剖析（超全详细版）
  • 使用 Cursor 和 Devbox 快速开发并上线 Gin 项目
  • Java 使用 itextpdf 自定义 生成 pdf
  • javascript实现aes算法
  • Ping32：企业级防泄密能力的强大守护者
  • Windows API --- Unicode简介 2.1
  • python--pyQt 单选按钮控件 -QRadioButton
  • Java面试题库——网络编程
  • 洛谷 P3130 [USACO15DEC] Counting Haybale P
  • 科大讯飞AI开发者大赛颁奖典礼，万码优才荣获前三甲！