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

面试突击:ArrayList源码详解

本文已收录于:https://github.com/danmuking/all-in-one(持续更新)

前言

哈喽,大家好,我是 DanMu。ArrayList 是我们日常开发中不可避免要使用到的一个类,并且在面试过程中也是一个非常高频的知识点,这篇文章将深入分析 ArrayList 的底层原理,助你彻底掌握 ArrayList相关的知识点。
ceeb653ely8gszdwumcnyj20u00u0q4v.jpg

数据结构

ArrayList 的底层是数组,与 Java 中的数组不同的是它的容量能动态增长,当空间不足时,ArrayList 将在底层自动增加数组空间,因此相对数组来说使用起来更加方便。

类图

arraylist-class-diagram.png从继承关系上看 ArrayList 继承于 AbstractList,实现了 List, RandomAccess , Cloneable , java.io.Serializable 等接口。

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
  • List : 表明它是一个列表,支持添加、删除、查找等操作,并且可以通过下标进行访问。
  • RandomAccess :这个接口表示这个类具有随机访问的能力。
  • Cloneable :表明它具有拷贝能力,可以进行深拷贝或浅拷贝操作。
  • Serializable : 表明它可以进行序列化操作,也就是可以将对象转换为字节流进行持久化存储或网络传输。

什么是随机访问?
简单来说,就是可以在 O(1) 的时间复杂度内根据下标找到对应元素。典型的具有随机访问的数据结构就是数组,而链表查询下标对应元素需要从头结点开始遍历所有节点,需要 O(N) 的时间复杂度,因此链表就不具有随机访问能力。

核心源码解读

成员变量

每个 ArrayList 都维护了一些重要的成员变量,用于 ArrayList 的管理,其中比较重要的变量有:

// 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;// 空数组,所有初始化长度为0的Arraylist共用这个数组,减少内存
private static final Object[] EMPTY_ELEMENTDATA = {};// 用于默认构造函数,创建 ArrayList 时不分配空间,将空间分配推迟到第一次添加元素时
// 需要区分和 EMPTY_ELEMENTDATA 的区别
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 实际保存 ArrayList 数据的数组
// transient关键字表示这部分内容不会被序列化
transient Object[] elementData; // non-private to simplify nested class access// ArrayList 所包含的元素个数
private int size;

初始化

ArrayList 中主要有三种构造方法:

// 带初始容量参数的构造函数
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//如果传入的参数大于0,创建 initialCapacity 大小的数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//如果传入的参数等于0,创建空数组this.elementData = EMPTY_ELEMENTDATA;} else {//其他情况,抛出异常throw new IllegalArgumentException("Illegal Capacity: " +initialCapacity);}
}// 默认无参构造函数
// 先用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 初始化, 当插入第一个数据时才扩容为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类型数据(c.toArray可能返回的不是Object类型的数组所以加上下面的语句用于判断)if (elementData.getClass() != Object[].class)//将原来不是Object类型的elementData数组的内容,赋值给新的Object类型的elementData数组elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// 其他情况,用空数组代替this.elementData = EMPTY_ELEMENTDATA;}
}

扩容机制

add 方法
/**
* 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {// 加元素之前,先调用 ensureCapacityInternal 方法,保证数组有足够的空间ensureCapacityInternal(size + 1);  // Increments modCount!!// 这里看到ArrayList添加元素的实质就相当于为数组赋值elementData[size++] = e;return true;
}
ensureCapacityInternal 方法
// 确保内部容量达到指定的最小容量。
private void ensureCapacityInternal(int 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;
}// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {// 这是ArrayList中维护的一个用来统计结构变化次数的变量,可以忽略modCount++;// 判断当前数组容量是否足以存储 minCapacity 个元素if (minCapacity - elementData.length > 0)// 存不下,调用 grow 方法进行扩容grow(minCapacity);
}
grow 方法

grow 方法是实现扩容的核心方法:

/*** 能分配的最大数组大小*/
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倍// 使用位运算,速度更快int newCapacity = oldCapacity + (oldCapacity >> 1);// 然后检查扩容后容量是否大于需要的容量,若还是小于需要的容量,直接扩容到需要的容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量超过最大值,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE,// 处理边界条件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);
}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();// 对minCapacity和MAX_ARRAY_SIZE进行比较// 若minCapacity大,将Integer.MAX_VALUE作为新数组的大小// 若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}
流程图

集合.drawio.png

删除元素

ArryList提供了两个删除List元素的方法,分别通过下标和元素进行元素的删除。

通过下标删除元素
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);// 将原来的最后一个index设为nullelementData[--size] = null; // clear to let GC do its work// 返回被删除元素return oldValue;
}

未命名绘图-第 2 页.drawio.png

通过元素删除元素
public boolean remove(Object o) {// 如果 o 为null,就删除 ArrayList中第一个值为 null 的元素if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {//  遍历 ArrayList,如果存在则删除第一个等于 o 的元素for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;
}
// 这边的逻辑和通过下标删除元素的逻辑一样
private void fastRemove(int index) {modCount++;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
}

点关注,不迷路

好了,以上就是这篇文章的全部内容了,如果你能看到这里,非常感谢你的支持!
如果你觉得这篇文章写的还不错, 求点赞👍 求关注❤️ 求分享👥 对暖男我来说真的 非常有用!!!
白嫖不好,创作不易,各位的支持和认可,就是我创作的最大动力,我们下篇文章见!
如果本篇博客有任何错误,请批评指教,不胜感激 !

最后推荐我的IM项目DiTing(https://github.com/danmuking/DiTing-Go),致力于成为一个初学者友好、易于上手的 IM 解决方案,希望能给你的学习、面试带来一点帮助,如果人才你喜欢,给个Star⭐叭!

相关文章:

面试突击:ArrayList源码详解

本文已收录于&#xff1a;https://github.com/danmuking/all-in-one&#xff08;持续更新&#xff09; 前言 哈喽&#xff0c;大家好&#xff0c;我是 DanMu。ArrayList 是我们日常开发中不可避免要使用到的一个类&#xff0c;并且在面试过程中也是一个非常高频的知识点&#…...

力扣每日一题:2734. 执行子串操作后的字典序最小字符串

题目链接 脑子比较笨&#xff0c;分三种情况考虑&#xff1a; 以a开头。xxa&#xff0c;a在中间。 对于情况2还有两种可能&#xff1a; 1. 全是a&#xff0c;最后一个元素需要替换成z&#xff0c;因为必须执行一次操作。 2. aaaxxa&#xff0c;中间有一段非a&#xff0c;将这…...

C++11中std::thread的使用

C11 引入了 std::thread&#xff0c;它是用于创建和管理线程的标准库类。以下是详细的讲解&#xff0c;包括如何使用 std::thread 进行线程创建、管理和参数传递等操作。 1. 包含必要的头文件 在使用 std::thread 前&#xff0c;需要包含 <thread> 头文件&#xff1a; …...

酷瓜云课堂(内网版)v1.1.5 发布,局域网在线学习+考试系统

更新内容 更新layui-v2.9.10更新docker国内镜像地址增加导入镜像构建容器的方式教师不批阅非首次考试试卷轮播图增加专栏类型目标链接增加课程能否发布检查去除初始化kindeditor语言文件去除选择题EF选项优化富文本内容显示样式优化内容图片点击放大监听优化试题题干答案等图片…...

大数据之Hadoop部署

文章目录 服务器规划服务器环境准备1. 网络测试2. 安装额外软件包3. 安装基础工具4. 关闭防火墙5. 创建用户并配置权限6. 创建目录并设置权限7. 卸载JDK8. 修改主机名9. 配置hosts文件10. 重启服务器 配置免密登录安装Java安装Hadoop1. Hadoop部署2. 配置Hadoop3. 格式化Hadoop…...

Java异常处理中的“throw”与“throws”的区别

在Java中&#xff0c;throw 和 throws 是两个用于处理异常的关键词&#xff0c;它们的使用场景和目的有所不同 1. throw throw 关键字用于在Java程序中显式地抛出一个异常。当你检测到某些条件&#xff08;通常是错误条件&#xff09;时&#xff0c;你可以使用 throw 来抛出一…...

英语智汇学习系统

目 录 1 软件概述 1.1 项目研究背景及意义 2 系统相关技术 2.1 HTML、WXSS、JAVASCRIPT技术 2.2 Vanilla框架 2.3 uni-app框架 2.4 MYSQL数据库 3 需求分析 3.1 可行性分析 3.2 功能需求分析 3.3 系统用户及用例分析 3.4 非功能需求分析 3.5 数据流图…...

ExtractAItoTEXT 提取Adobe illustrator AI文件中的文字到文本文件翻译并写回到Adobe illustrator AI文件

Extract Text from Adobe illustrator to text for translate and write back to Adobe illustrator after translate in text file. Originally script from marceloliaohotmail.com during his work in SDL. Updated by me. 从Adobe illustrator中提取文本以进行翻译&#x…...

ms17-010 ms12-020 ms-08-067

MS17-010是一个由微软发布的安全公告编号&#xff0c;它指代了一个严重级别的安全漏洞&#xff0c;该漏洞存在于Microsoft Windows的Server Message Block 1.0 (SMBv1)协议处理中。这个漏洞被命名为“永恒之蓝”&#xff08;EternalBlue&#xff09;&#xff0c;因为它最初是由…...

【海思Hi3403V100】多目拼接相机套板硬件规划方案

海思Hi3403V100 是专业超高清智能网络摄像头 SoC。该芯片最高支持四路 sensor 输入&#xff0c;支持最高 4K60fps 的 ISP 图像处理能力&#xff0c;支持 3F 、WDR、多级降噪、六轴防抖、硬件拼接、多光谱融合等多种传统图像增强和处理算法&#xff0c;支持通过AI 算法对输入图像…...

AI的赚钱风向,彻底变了!

从2023年3月起&#xff0c;生成式AI技术的浪潮席卷全球&#xff0c;让不少人开始焦虑中国AI技术与美国的差距。然而&#xff0c;最近的趋势显示&#xff0c;AI创业的盈利模式已经发生了根本性的变化。今年&#xff0c;我们见证了AIGC&#xff08;人工智能生成内容&#xff09;企…...

服务器重启后jenkins任务内容不见了,并且新建任务也不见了

服务器centos7.4 背景&#xff1a;服务器异常重启后&#xff0c;jenkins上面的任务只剩下一些前端项目&#xff0c;后端的任务都不展示了&#xff0c;jenkins版本是Jenkins 2.346.3 解决方案&#xff1a;根据显示&#xff0c;jenkins很多的插件引用失败&#xff0c;显示需要升…...

如何选择合适的WordPress主机?

选择合适的WordPress主机需要考虑多个因素&#xff0c;包括性能、速度、存储空间、带宽、硬件配置、操作系统、支持的软件版本以及安全性等。以下是一些详细的建议&#xff1a; 性能和速度&#xff1a;选择一个能够提供快速加载速度和稳定性能的主机至关重要。快速加载的网站不…...

面试突击:Java 集合知识体系梳理

本文已收录于&#xff1a;https://github.com/danmuking/all-in-one&#xff08;持续更新&#xff09; 前言 哈喽&#xff0c;大家好&#xff0c;我是 DanMu。在 Java 开发中&#xff0c;集合类对象绝对是被使用最频繁的对象之一。因此&#xff0c;深入了解集合类对象的底层数…...

AI智能管理系统设计文档

AI智能管理系统设计文档 1. 引言 本设计文档旨在开发一套全面的AI智能管理系统&#xff0c;以优化生产运营效率和决策质量。该系统将利用先进的AI技术和数据分析能力&#xff0c;提供自动化流程控制、预测性维护、智能决策支持等功能。 2. 需求分析与目标设定 2.1 业务需求…...

干涉阵型成图参数记录【robust】

robust 这个玩意经常忘记&#xff0c;就是取2的时候是更加显示大尺度的结构&#xff0c;取-2更加显示小尺度结果&#xff0c;一般取0就是正常就好了...

React Native工程运行时下载gradle超时问题

React Native工程在运行Android的时候会下载gradle&#xff0c;但是由于众所周知的问题&#xff0c;总是下载失败&#xff0c;这时可以通过修改 <APP_ROOT>/android/wrapper/gradle-wrapper.properties 文件中 distributionUrl 参数使用国内 gradle 镜像来提高下载速度。…...

本地离线模型搭建指南-LLaMA-Factory训练框架及工具

搭建一个本地中文大语言模型&#xff08;LLM&#xff09;涉及多个关键步骤&#xff0c;从选择模型底座&#xff0c;到运行机器和框架&#xff0c;再到具体的架构实现和训练方式。以下是一个详细的指南&#xff0c;帮助你从零开始构建和运行一个中文大语言模型。 本地离线模型搭…...

数智化金融采购系统特点

数智化金融采购系统是郑州信源公司结合众多金融行业采购特点&#xff0c;采用流程优化再造的理念&#xff0c;为银行、保险、证券、交易所等金额机构打造的细分行业产品&#xff0c;助力金融行业采购合规管理、风险防范、成本管理和效率提升。 系统特点 1、全业务覆盖&#x…...

使用 SwiftUI 为 macOS 创建类似于 App Store Connect 的选择器

文章目录 前言创建选择器组件使用选择器组件总结前言 最近,我一直在为我的应用开发一个全新的界面,它可以让你查看 TestFlight 上所有可用的构建,并允许你将它们添加到测试群组中。 作为这项工作的一部分,我需要创建一个组件,允许用户从特定构建中添加和删除测试群组。我…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...