聊聊 Java 集合框架中的 ArrayList

其实 Java 集合框架也叫做容器,主要由两大接口派生而来,一个是 collection,主要存放对象的集合。另外一个是Map, 存储着键值对(两个对象)的映射表。

下面就来说说 List接口,List存储的元素是有序、可重复的。其下有三个子接口,ArrayList、LinkedList 和 vector。

一、 ArrayList概述

ArrayList 底层数据结构是基于 Object 数组来实现的,我们看看它的底层接口源码:

1. ArrayList 实现的接口

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

其中继承的接口中的 RandomAccessCloneableSerializable 只是标记接口,他们的接口内部没有具体的方法和参数:

public interface RandomAccess {} 
public interface Cloneable {}    //覆盖clone(),能被克隆
public interface Serializable {} //支持序列化,能通过序列化传输

标记接口是计算机科学中的一种设计思路。编程语言本身不支持为类维护元数据。而标记接口则弥补了这个功能上的缺失——一个类实现某个没有任何方法的标记接口,实际上标记接口从某种意义上说就成为了这个类的元数据之一。运行时,通过编程语言的反射机制,我们就可以在代码里拿到这种元数据。

以Serializable接口为例。一个类实现了这个接口,说明它可以被序列化。因此,我们实际上通过Serializable这个接口,给该类标记了“可被序列化”的元数据,打上了“可被序列化”的标签。这也是标记/标签接口名字的由来。

此外AbstractList 继承AbstractCollection 抽象类,实现List接口。它实现了 List 的一些基本操作如(get,set,add,remove),是第一实现随机访问方法的集合类,但是不支持添加和替换。

2.ArrayList 的成员属性

private static final int DEFAULT_CAPACITY = 10; //默认初始容量为10 
private static final Object[] EMPTY_ELEMENTDATA = {}; //空数组,用于空实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//用于默认大小空实例的共享空数组实例。
transient Object[] elementData; //保存ArrayList数据的数组,transient修饰表示数组默认不会被序列化
private int size; //ArrayList中数组的个数

二、ArrayList 中的方法

Java ArrayList 中常用的方法:

方法描述
add()将元素插入到指定位置的 arraylist 中
addAll()添加集合中的所有元素到 arraylist 中
clear()删除 arraylist 中的所有元素
clone()复制一份 arraylist
contains()判断元素是否在 arraylist
get()通过索引值获取 arraylist 中的元素
indexOf()返回 arraylist 中元素的索引值
removeAll()删除存在于指定集合中的 arraylist 里的所有元素
remove()删除 arraylist 里的单个元素
size()返回 arraylist 里元素数量
isEmpty()判断 arraylist 是否为空
subList()截取部分 arraylist 的元素
set()替换 arraylist 中指定索引的元素
sort()对 arraylist 元素进行排序
toArray()将 arraylist 转换为数组
toString()将 arraylist 转换为字符串
ensureCapacity()设置指定容量大小的 arraylist
lastIndexOf()返回指定元素在 arraylist 中最后一次出现的位置
retainAll()保留 arraylist 中在指定集合中也存在的那些元素
containsAll()查看 arraylist 是否包含指定集合中的所有元素
trimToSize()将 arraylist 中的容量调整为数组中的元素个数
removeRange()删除 arraylist 中指定索引之间存在的元素
replaceAll()将给定的操作内容替换掉数组中每一个元素
removeIf()删除所有满足特定条件的 arraylist 元素
forEach()遍历 arraylist 中每一个元素并执行特定操作

具体的方法细节可以看这里

三、ArrayList 中的扩容机制

在初始化时,ArrayList 有三种方式来进行初始化,以无参构造方法创建 ArrayList 时,实际上赋值的是一个空数组。当真正对数组进行添加元素时,才真正的给 ArrayList 分配容量,即数组容量扩为10。


/***默认构造函数,使用初始容量10构造一个空列表(无参数构造)*/
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/*** 带初始容量参数的构造函数。(用户自己指定容量)*/
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {//初始容量大于0//创建initialCapacity大小的数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//初始容量等于0//创建空数组this.elementData = EMPTY_ELEMENTDATA;} else {//初始容量小于0,抛出异常throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}
}/***构造包含指定collection元素的列表,这些元素利用该集合的迭代器按顺序返回*如果指定的集合为null,throws NullPointerException。*/
public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}
}
/*** 将指定的元素追加到此数组的末尾。*/
public boolean add(E e) {//在增加元素前,先调用ensureCapacityInternal方法ensureCapacityInternal(size + 1);  elementData[size++] = e;return true;
}private void ensureCapacityInternal(int minCapacity) {//比较当前元素个数和默认元素个数,如果小于10,则将最小容量设为默认值10if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}//继续调用 ensureExplicitCapacity()方法ensureExplicitCapacity(minCapacity);
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious code//如果大于当前数组默认长度,则进行扩容,调用grow()方法if (minCapacity - elementData.length > 0)grow(minCapacity);
}
/*** 要分配的最大数组大小*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//在以前的容量基础上增加旧容量的1/2int newCapacity = oldCapacity + (oldCapacity >> 1);//检查比较新容量与最小容量的大小,取大值if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//更新完新容量后,比较是否大于最大数组大小 Integer.MAX_VALUE - 8if (newCapacity - MAX_ARRAY_SIZE > 0)//若大于最大数组大小,则调用hugeCapacity()方法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;
}

四、ArrayList 相关面试题

1. System.arraycopy() 和 Arrays.copyOf() 的区别

联系:

看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法

区别:

arraycopy() 需要目标数组,将原数组拷贝到你自己定义的数组里或者原数组,而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组,并返回该数组。

2. ArrayList 和 LinkedList 的区别

  1. 是否保证线程安全: ArrayListLinkedList 都是不同步的,也就是不保证线程安全;
  2. 底层数据结构: Arraylist 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)
  3. 插入和删除是否受元素位置的影响:ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以对于add(E e)方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
  4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

3. ArrayList 和 Vector 的区别

  1. ArrayListList 的主要实现类,底层使用 Object[ ]存储,适用于频繁的查找工作,线程不安全 ;
  2. VectorList 的古老实现类,底层使用 Object[ ]存储,线程安全的。如下代码带有 synchronized 同步锁,能够保证线程安全。
public synchronized void ensureCapacity(int minCapacity) {if (minCapacity > 0) {modCount++;ensureCapacityHelper(minCapacity);}
}

4. ArrayList 和 CopyOnWriteArrayList 的区别

CopyOnWriteArrayList 和 Vector 一样也是线程安全的 List 。它在 java.util.concurrent 的包下。它的线程安全主要是通过读写分离来实现的。写操作在一个复制的数组上实现(加锁),读操作还是在原数组中进行。

public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;Object[] newElements = Arrays.copyOf(elements, len + 1);newElements[len] = e;setArray(newElements);return true;} finally {lock.unlock();}
}final void setArray(Object[] a) {array = a;
}

特点:适合读多写少的应用场景

缺点

  • 内存占用:在写操作时需要复制一个新的数组,使得内存占用为原来的两倍左右;
  • 数据不一致:读操作不能读取实时性的数据,因为部分写操作的数据还未同步到读数组中;

五、参考资料

ArrayList 扩容机制分析

Java ArrayList

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/234761.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JAVA实现文件上传至阿里云

注册阿里云账号后,开通好对象存储服务&#xff08;OSS&#xff09;&#xff0c;三个月试用 阿里云登录页 (aliyun.com) 目录 一.创建Bucket 二.获取AccessKey&#xff08;密钥&#xff09; 三.参考官方SDK文件&#xff0c;编写入门程序 1.复制阿里云OSS依赖&#xff0c;粘贴…

Swift单元测试Quick+Nimble

文章目录 使用QuickNimble1、苹果官方测试框架XCTest的优缺点2、选择QuickNimble的原因&#xff1a;3、QuickNimble使用介绍集成&#xff1a;Quick关键字说明&#xff1a;Nimble中的匹配函数等值判断&#xff1a;使用equal函数是否是同一个对象&#xff1a;使用beIdenticalTo函…

【Verilog】期末复习——分别画出下面两个程序综合后的电路图/reg型数据和wire型数据的区别

系列文章 数值&#xff08;整数&#xff0c;实数&#xff0c;字符串&#xff09;与数据类型&#xff08;wire、reg、mem、parameter&#xff09; 运算符 数据流建模 行为级建模 结构化建模 组合电路的设计和时序电路的设计 有限状态机的定义和分类 期末复习——数字逻辑电路分…

基于ssm基于协同过滤技术的网上书城的开发与研究+jsp论文

摘 要 社会发展日新月异&#xff0c;用计算机应用实现数据管理功能已经算是很完善的了&#xff0c;但是随着移动互联网的到来&#xff0c;处理信息不再受制于地理位置的限制&#xff0c;处理信息及时高效&#xff0c;备受人们的喜爱。本次开发一套基于协同过滤技术的网上书城有…

大数据毕业设计:图书推荐系统+可视化+Django框架 图书管理系统 (附源码+论文)✅

毕业设计&#xff1a;2023-2024年计算机专业毕业设计选题汇总&#xff08;建议收藏&#xff09; 毕业设计&#xff1a;2023-2024年最新最全计算机专业毕设选题推荐汇总 &#x1f345;感兴趣的可以先收藏起来&#xff0c;点赞、关注不迷路&#xff0c;大家在毕设选题&#xff…

外汇天眼:CQG 与 TradeStation Securities 的经纪服务集成

TradeStation Securities, Inc.&#xff0c;一家自营的在线股票、ETF、期权和期货交易经纪公司&#xff0c;宣布与CQG合作&#xff0c;CQG是一家为交易员、经纪商、商业套保者和交易所提供高性能技术解决方案的全球供应商&#xff0c;已与TradeStation Securities的经纪服务集成…

idea右上角浏览器图标没有idea内部浏览器怎么显示

idea右上角浏览器图标没有idea内部浏览器怎么显示 file -> settings -> tools -> web brosers 选择需要的浏览器&#xff0c;勾选上展示到编辑器中 打开上图的Built-in Preview&#xff0c;就会显示idea标志的内部显示了&#xff01;&#xff01;&#xff01;

python 和shell 变量互相传递

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 主要介绍python和shell变量互相传递方法&#xff0c;使用了环境变量、管道等方法。 python -> shell&#xff1a; 1.环境变量 import os var123或var123 o…

《C++语言程序设计(第5版)》(清华大学出版社,郑莉 董渊编著)习题——第2章 C++语言简单程序设计

2-15 编写一个程序&#xff0c;运行时提示输入一个数字&#xff0c;再把这个数字显示出来。 #include <iostream>using namespace std;int main() {// 提示用户输入数字cout << "请输入一个数字: ";// 用于存储用户输入的数字的变量double number;// 从…

源码|redis7.2.2|sds

文章目录 前言Type && EncodingsdsencodingcreateStringObjectcreateEmbeddedStringObject总结 createRawStringObject总结 createStringObjectFromLongDouble总结 createStringObjectFromLongLongWithOptions总结 相关操作sdscatlen总结 阈值44sds VS C字符串 前言 从…

docker镜像的生成过程

镜像的生成过程 Docker镜像的构建过程&#xff0c;大量应用了镜像间的父子关系。即下层镜像是作为上层镜像的父镜像出现的&#xff0c;下层镜像是作为上层镜像的输入出现。上层镜像是在下层镜像的基础之上变化而来。 FROM centos:7 FROM指令是Dockerfile中唯一不可缺少的命令&a…

Web APIs知识点讲解

学习目标: 能获取DOM元素并修改元素属性具备利用定时器间歇函数制作焦点图切换的能力 一.Web API 基本认知 1.作用和分类 作用: 就是使用 JS 去操作 html 和浏览器分类&#xff1a;DOM (文档对象模型)、BOM&#xff08;浏览器对象模型&#xff09; 2.DOM DOM(Document Ob…

吉林大学19、21级计算机学院《计算机网络》期末真题试题

一、21级&#xff08;考后回忆&#xff09; 一、不定项选择&#xff08;一共10个选择题&#xff0c;一个两分&#xff0c;选全得满分&#xff09; 不定项&#xff1a;可以选择1~4个 考点有&#xff1a; ①协议、服务 ②码分多路复用通过接受码片序列&#xff0c;求哪个站点发送…

vue3项目中axios的常见用法和封装拦截(详细解释)

1、axios的简单介绍 Axios是一个基于Promise的HTTP客户端库&#xff0c;用于浏览器和Node.js环境中发送HTTP请求。它提供了一种简单、易用且功能丰富的方式来与后端服务器进行通信。能够发送常见的HTTP请求&#xff0c;并获得服务端返回的数据。 此外&#xff0c;Axios还提供…

C++ queue

目录 一、介绍 二、queue使用 三、模拟实现 四、优先级队列 五、priority_queue使用 OJ题&#xff1a;215. 数组中的第K个最大元素 快速排序 优先级队列 TOPK 六、模拟实现priority_queue 1、仿函数 2、优先级队列类 3、测试函数 一、介绍 1、队列是一种容器适配器…

【手搓深度学习算法】用线性回归预测波士顿房价

线性回归 线性回归是一种监督学习方法&#xff0c;用于建立因变量与一个或多个自变量之间的关系。线性回归的目标是找到一条直线&#xff0c;使得所有数据点到这条直线的距离之和最小。 线性回归的基本形式如下&#xff1a; y β 0 β 1 x 1 β 2 x 2 . . . β n x n ϵ…

mysql基础-常用函数汇总

目录 1. 查询技巧 2. 时间函数 2.1 now() 2.2 current_date() 2.3 时间差timestampdiff&#xff08;&#xff09;与datediff&#xff08;&#xff09; 2.4 其他时间函数 3. 字符函数 3.1 截取函数 3.2 分割函数 3.3 left与right函数 3.4 其他函数 4. 数字函数 5. …

自定义HBase负载均衡器MyCustomBalancer实现步骤与代码解析

目录 1.HBase默认负载均衡策略 1.1 负载均衡总体流程 1.2 不能触发负载均衡的情况 1.3 负载均衡算法 2.自定义的 HBase 负载均衡器的步骤 3.MyCustomBalancer的代码细节 3.1 balanceCluster 方法的作用 3.2balanceCluster 对数据的影响 3.3监控HBase的性能指标 3.3.…

在国内 PMP 有多少含金量?

在我国大陆&#xff0c;有好多证书被商业化得太重了&#xff0c;甚至演变成了个人或一些公司摇钱的工具。所以有些证书受人吹捧它崛起的快&#xff0c;但是活不长&#xff0c;甚至“夭折”&#xff0c;比如以前微软系列的证书&#xff1b; 而PMP认证从国外引进大陆这么多年了&…

PMP认证考试详细备考攻略,全是干货!

要明白&#xff0c;虽然PMP备考考试只是一时的过程&#xff0c;但通过PMP获得的证书和能力是永久的。 这不仅仅是因为我拿到了PMP培训结业证书和PMP认证证书这两个证明&#xff0c;更重要的是在参加PMP认证考试的整个过程中&#xff0c;我学到了很多关于项目管理的知识&#x…