【JavaSE】ArrayList的扩容机制源码分析

news/2024/10/30 11:21:27/

文章目录

  • 1. ArrayList概述
  • 2. ArrayList构造方法源码分析
  • 3. ArrayList.add()源码分析
  • 4. ArrayList.addAll()源码分析
  • 5. 总结

1. ArrayList概述

ArrayList是Java集合框架中比较常用的一个数据结构了，它底层是基于数组实现的。数组是固定大小的，但是ArrayList的扩容机制可以实现容量大小的动态变化。

数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容。

ArrayList的扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去。

image-20230201153601407

ArrayList添加元素有下面两种方式

  1. public boolean add(E e)
  2. public boolean addAll(Collection<? extends E> c)

下面进行源码分析

2. ArrayList构造方法源码分析

创建ArrayList集合的时候，会调用其构造方法

//存放元素的数据
transient Object[] elementData;
//默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//集合长度
private int size;//无参构造
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}//指定元素长度构造
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);}
}//构造参数为集合
public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}
}
  1. 无参构造：无参构造会使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为存放元素的数据的数组，也就是默认集合底层的数组长度为0。
  2. 指定元素长度构造：指定元素长度构造则是使用构造参数initialCapacity作为数组的长度。this.elementData = new Object[initialCapacity];
  3. 构造参数为集合：使用构造参数集合c的长度作为底层数组elementData的长度，并将集合的元素拷贝成一个新数组赋值给elementData

3. ArrayList.add()源码分析

先准备一段添加数据进行的代码，添加的数据长度为15。

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

首先，创建ArrayList集合的时候，会调用其无参构造方法，ArrayList底层数组为长度为0的空数组。

下面是add方法的源码

public boolean add(E e) {//检查是否需要扩容ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}

在添加元素进集合集合之前，需要先调用ensureCapacityInternal方法，检查是否要扩容。

参数为底层存储数据的数组的长度+1

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

ensureCapacityInternal里面ensureExplicitCapacity方法。

在执行ensureExplicitCapacity之前需要调用calculateCapacity方法计算需要扩容的长度。

//默认的初始化容量大小
private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}

calculateCapacity方法有两个参数，elementData是底层用来存储数据的数组，而minCapacity就是新的数组长度。

在这个方法里，首先判断一下elementData是不是默认的空数组（也就是是否和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是同一个对象）**，如果是，则取新数组的长度和默认的初始化容量的长度的最大值返回。**也就是说，如果集合中第一次添加元素，那么默认的容量大小为10。

如果不是默认的空数组，则将minCapacity也就是新的数组长度返回。

//该参数是记录列表结构以被修改的次数
protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);
}

接着比较现在新数组长度minCapacity和底层数组长度elementData.length的大小

如果minCapacity小于等于elementData.length则不需要扩容。

如果minCapacity大于elementData.length则需要扩容，调用grow(minCapacity)方法。

参数为新数组的长度。

//数组最大容量，-8是因为有些VM会在数组中保留一些词
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {// overflow-conscious code//记录底层数组的长度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);
}

这个grow方法就是扩容的关键所在了。

扩容后的数组长度的关键就是这一行代码

int newCapacity = oldCapacity + (oldCapacity >> 1);

(oldCapacity >> 1)就是右移运算表示除以2

假设现在oldCapacity为10，其原码为1010，向右移动一位就是0101，也是5。

所以扩容后的新容量newCapacity就是15。

接着判断扩容后的容量newCapacity和新数组的容量minCapacity进行比较。

  1. 如果小于，也就是扩容后的容量newCapacity还不够，那么将新数组的长度minCapacity赋值给newCapacity。

然后将扩容容量newCapacity和数组最大容量MAX_ARRAY_SIZE对比

  1. 如果大于，则执行hugeCapacity(minCapacity)方法
//数组最大容量，-8是因为有些VM会在数组中保留一些词
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

hugeCapacity(minCapacity)方法判断如果最小扩展要求值小于0则抛出异常，否则进行判断最小扩展要求值minCapacity是否大于MAX_ARRAY_SIZE，如果大于则返回最大int值，如果不大于则返回MAX_ARRAY_SIZE值。

最后通过Arrays.copyOf(elementData, newCapacity);扩容就完成了。

4. ArrayList.addAll()源码分析

先准备一段测试代码。

public class TestArrayList {public static void main(String[] args) {ArrayList list = new ArrayList();list.addAll(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11));}
}

下面是addAll的源码

public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;
}

addAll主要的逻辑就是将传进来的集合转化为数组，拿到这个数组的长度。

接着对当前ArrayList执行检查扩容操作，然后System.arraycopy方法将System.arraycopy数组附加到elementData数组的size下标后，然后设置size的大小，最后根据传入的容器长度来返回添加状态。

5. 总结

  1. ArrayList扩容通常为原数组大小的1.5倍，并且ArrayList最大容量为int最大值。
  2. addAll(Collection c)没有元素时候，扩容为Math.max(10, 实际元素个数)，有元素时为Math.max(原来容量的1.5倍，实际元素个数)
  3. add(Object o)首次扩容为10，再次扩容为上次容量的1.5倍。
  4. ArrayList(int initialCapacity)会使用指定容量的数组
  5. ArrayList(Collection<? extends E> c)会使用c的大小作为数组容量

http://www.ppmy.cn/news/21436.html

相关文章

C++入门：变量类型

C++入门：变量类型

变量其实只不过是程序可操作的存储区的名称。C 中每个变量都有指定的类型&#xff0c;类型决定了变量存储的大小和布局&#xff0c;该范围内的值都可以存储在内存中&#xff0c;运算符可应用于变量上。变量的类型间是可以互相转换的&#xff0c;转换又分为自动转换和强制转换。…
阅读更多...
C++基础知识点整理笔记（五）

C++基础知识点整理笔记（五）

14. 类中 private&#xff0c;protect&#xff0c;public 三种访问限制类型的区别 (一) private 是私有类型&#xff0c;只有本类中的成员函数访问;(二) protect 是保护型的&#xff0c;本类和继承类可以访问;(三) public 是公有类型&#xff0c;任何类都可以访问. 15. struct…
阅读更多...
消息队列简介

消息队列简介

提高系统性能首先考虑的是数据库的优化&#xff0c;之前一篇文章《数据库的使用你可能忽略了这些》中有提到过开发中&#xff0c;针对数据库需要注意的事项。但是数据库因为历史原因&#xff0c;横向扩展是一件非常复杂的工程&#xff0c;所有我们一般会尽量把流量都挡在数据库…
阅读更多...
spring中的JSR-303统一校验

spring中的JSR-303统一校验

1.在前后端的传输参数的过程中数据在何处校验? 在前后端都需要进行校验,只是分工不同. 2.各个层的校验内容: 1.Controller层主要负责校验残水的合法性,包括: 必填的参数字段,数据格式的校验 2.Service层的业务校验是审核业务中的规则的相关内容,比如:课程已经审核通过所以提…
阅读更多...
SpringCloud_Alibaba Sentinel实现熔断与限流

SpringCloud_Alibaba Sentinel实现熔断与限流

目录一、Sentinel介绍1.官网2.是什么3.能干嘛4.去哪下5.怎么玩二、安装Sentinel控制台1.sentinel组件由2部分组成2.安装步骤三、初始化演示工程1.启动Nacos8848成功2.案例3.启动Sentinel80804.启动微服务84015.启动8401微服务后查看sentienl控制台四、流控规则1.基本介绍2.流控…
阅读更多...
195136-58-4，2‘,7‘-Difluorofluorescein，2，7-二氟荧光素

195136-58-4，2‘,7‘-Difluorofluorescein，2，7-二氟荧光素

产品描述&#xff1a;2&#xff0c;7-二氟荧光素中Fluorescein (Uranine) 生物应用中的荧光示踪剂&#xff0c;Fluorescein (Uranine) 是一种具有代表性的绿色荧光团&#xff0c;已被广泛用作实用绿色荧光探针的支架。结构式&#xff1a;理论分析&#xff1a;中文名&#xff1a…
阅读更多...
【批处理脚本】-1.6-列文件名命令dir

【批处理脚本】-1.6-列文件名命令dir

点击返回「批处理BAT从入门到精通」总目录 在从事“嵌入式软件开发”和“Autosar工具开发软件”过程中，经常会在其集成开发环境IDE（CodeWarrior，S32K DS，Davinci，EB Tresos，ETAS…）中，使用“批处理（bat）”和“Python”制作脚本，从而实现编译功能（GreenHills…）的…
阅读更多...
spark读取数据写入hive数据表

spark读取数据写入hive数据表

目录 一个模板 概述&#xff1a; create_tabel建表函数&#xff0c;定义日期分区 删除原有分区drop_partition函数 generate_data 数据处理函数&#xff0c;将相关数据写入定义的表中 添加分区函数add_partition 一个模板 概述&#xff1a; table_name name # 要写入…
阅读更多...
最新文章

Copyright @ 2022~2023