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

一文了解 ArrayList 的扩容机制

了解 ArrayList

在 Java 中常用集合类之间的关系如下图所示:

在这里插入图片描述

从图中可以看出 ArrayList 是实现了 List 接口,并是一个可扩容数组(动态数组),它的内部是基于数组实现的。它的源码定义如下:

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
  • ArrayList 可以实现所有可选择的列表操作,允许所有的元素,包括空值。ArrayList 还提供了内部存储 List 的方法,它能够完全替代Vector,只有一点例外,ArrayList 不是线程安全的容器。

  • ArrayList 有一个容量的概念,这个数组的容量(size)就是 List 用来存储元素的容量。

  • ArrayList 不是线程安全的容器,如果多个线程中至少有两个线程修改了 ArrayList 的结构的话就会导致线程安全问题,作为替代条件可以使用线程安全的 List,应使用 Collections.synchronizedList

    List list = Collections.synchronizedList(new ArrayList<>());
    
  • ArrayList 具有 fail-fast 快速失败机制,能够对 ArrayList 作出失败检测。当在迭代集合的过程中该集合在结构上发生改变的时候,就有可能会发生 fail-fast,即抛出ConcurrentModificationException异常。

通过源码分析 ArrayList 的扩容机制

当使用空参构造器进行创建 ArrayList 的时候,实际上给 elementData 初始化赋值的是一个空数组 {}

//数组列表的大小(包含的元素数),初始化为 0
private int size;
//存储数组列表元素的数组缓冲区。
transient Object[] elementData;
//默认初始化容量为10
private static final int DEFAULT_CAPACITY = 10;
//默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//使用空参构造器创建 ArrayList 时,实际上初始化赋值的是一个空数组
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

当首次调用 add(E e) 方法进行添加第一个元素时,会首先调用 ensureCapacityInternal 方法,传入参数 1

//将指定的元素追加到此列表的末尾
public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}

ensureCapacityInternal 方法中,会调用 calculateCapacity 方法,传入参数为 elementData,1

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

calculateCapacity 方法中,判断 elementData 是否为空数组,由于是初始化赋值的是一个空数组 {},所以符合 if 条件,返回 (DEFAULT_CAPACITY, minCapacity)【10,1】 中大的那个,此时返回 10

private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}

接着返回到 ensureCapacityInternal 方法中,继续调用 ensureExplicitCapacity 方法验证是否需要扩容,传入参数 10 ,此时 minCapacity=10,elementData.length=0 ,相减小于0,执行 grow 方法扩容,传入参数 10,当添加第2-10个元素时,不会执行 grow 方法,一直到数组已经满元素时才执行 grow 方法扩容:

private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);
}

grow 方法中,此时 minCapacity=10,oldCapacity=0,newCapacity=0 ,符合 newCapacity - minCapacity < 0 条件,执行 newCapacity = minCapacity; 不满足 newCapacity - MAX_ARRAY_SIZE > 0 ,执行 Arrays.copyOf() 方法将 elementData 指向的数组中的元素复制到新的数组中,新的数组长度为 10,并让 elementData 指向新的数组,int newCapacity = oldCapacity + (oldCapacity >> 1) 完成1.5倍扩容。

private void grow(int minCapacity) {// overflow-conscious codeint 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);
}
http://www.lryc.cn/news/4958.html

相关文章:

  • 牛态已成选股源码
  • Python基础
  • 浅显易懂的说清楚小游戏与H5游戏的技术区别
  • 【Python入门第七天】Python 数字
  • Python自动化测试 软件测试最全教程(附笔记),看完可就业
  • Windows 安装Tomcat
  • 知识图谱业务落地技术推荐之图数据库汇总
  • 2023新华为OD机试题 - 最小传递延迟(JavaScript) | 刷完必过
  • SpringMVC基础入门(一)之理论基础概念
  • 前端知识点
  • 【docker知识】从容器中如何访问到宿主机
  • MySQL入门篇-MySQL常用流程控制函数小结
  • 大数据技术架构(组件)35——Spark:Spark Streaming(1)
  • 实现超大文件上传逻辑
  • JavaScript HTML DOM EventListener
  • 构建RFID系统的重要组成部分
  • PID控制算法简介
  • 【王道数据结构】第八章 | 排序
  • 95后外贸SOHO,年入7位数,他究竟是怎么做的?
  • 2023年全国最新消防设施操作员精选真题及答案
  • mysql 无需修改配置文件,即可改变表数据存储位置
  • 轻松解决Session-Cookie 鉴权(含坑)附代码
  • pyinstaller使用详细
  • java -数据结构,List相关基础知识,ArrayList的基本使用,泛型的简单、包装类介绍
  • RabbitMQ学习总结(10)—— RabbitMQ如何保证消息的可靠性
  • 购物车案例【版本为vue3】
  • Multisim14 安装包及安装教程
  • Java实现简单的图书管理系统源码+论文
  • 前端调试2
  • AlphaFold 2 处理蛋白质折叠问题