Java ArrayList使用总结

提起ArrayList,相信很多小伙伴都用过,而且还不少用。但在几年之前,我在一场面试中,面试官要求说出ArrayList的扩容机制。很显然,那个时候的我并没有关注这些,从而错过了一次机会。不过好在我还算比较喜欢搞事情的,所以今天这篇文章也算是填坑吧。
看完这边文章你将了解到:

  • ArrayList底层实现
  • ArrayList为什么允许null值
  • ArrayList为什么可重复
  • ArrayList查询效率和插入效率对比

类图

下图是ArrayList的类图结构

ArrayList继承于 AbstractList,实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
这里逐个分析一下这里接口的意义:

  • RandomAccess是一个标志接口,表明实现这个这个接口的 List集合是支持快速随机访问的。有兴趣可以看看Collections类中哪个方法用到了这个标志性接口。
  • 实现 Cloneable接口并覆盖了方法clone(),能被克隆。
  • 实现了java.io.Serializable 接口,这意味着ArrayList支持序列化,能通过序列化去传输(请注意,ArrayList的序列化是有点小特殊的,后面会讲解)。

源码解析

成员变量
在正式进入源码分析之前,我们有必要先看看它的成员变量都有哪些,这里列举比较重要的成员变量:

private int size; // 实际元素个数
transient Object[] elementData; //真正保存元素的数组
private static final int DEFAULT_CAPACITY = 10;//默认的初始容量大小

构造方法
我们有三种初始化办法:无参数直接初始化、指定大小初始化、指定初始数据初始化,源码如下:

//1、无参数直接初始化,数组大小为空
public ArrayList() {
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//2、指定初始数据初始化
public ArrayList(Collection<? extends E> c){
 //elementData是保存数组的容器,默认为null
 elementData=c.toArray();
 //如果给定的集合(c)数据有值
 if((size=elementData.length)!=0){
  	//c.toArray might(incorrectly)not return Object[](see 6260652)
  	//如果集合元素类型不是Object类型,我们会转成Object
	 if(elementData.getClass()!=Object[].class){
	  elementData=Arrays.copyOf(elementData,size,Object].class);
	 }
 	}else{
 	//给定集合(c)无值,则默认空数组
 	this.elementData=EMPTY_ELEMENTDATA
 	}
}
//3、指定初始容量
public ArrayList(int initialCapacity) {
	//指定的初始容量大于0,将elementData初始化为指定大小的数组
 if (initialCapacity > 0) {
  this.elementData = new Object[initialCapacity];
 } else if (initialCapacity == 0) {
 	//否则初始化成一个空数组
  this.elementData = EMPTY_ELEMENTDATA;
 }
}

除过源码中注释外,补充几点:

  1. ArrayList无参构造器初始化时,默认大小是空数组,并不是大家常说的10,10是在第一次add的时候扩容的数组值。
  2. 使用方式二进行创建对象时,如果入参容器保存的对象不是Object,则转换为Object。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA又是什么鬼?它其实是定义在成员变量的两个空数组,

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};

很明显问题来了,既然都是空数组,为什么要声明两个?一个不行吗?读者请先思考一下,带着疑问往下看。

新增和扩容实现

通过构造方法可以很清楚的看到,ArrayList的确是基于数组的,但动态又从何说起?
新增时就是给数组中添加元素,主要分为两步走:

  1. 判断是否需要扩容,如果需要扩容执行扩容操作;
  2. 直接赋值。

对应源码如下:

public boolean add(E e) {
	//确保数组大小是否足够,不够执行扩容,size为当前数组元素个数,判断size+1是因为后面还要size++
 ensureCapacityInternal(size + 1); //1
 elementData[size++] = e;//2
 return true;
}

我们先来看一下扩容部分的源码:

private void ensureCapacityInternal(int minCapacity) {
	//先调用calculateCapacity计算容量
 	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
 //如果当前数组还是个空数组,也就是他用过无参构造去初始化的
 //那么直接返回DEFAULT_CAPACITY,即10
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  return Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
 modCount++;

 // 如果当前容量已经大于当前数组的长度了,说明需要去扩容了
 if (minCapacity - elementData.length > 0)
  //扩容
  grow(minCapacity);
}

private void grow(int minCapacity){
 int oldCapacity = elementData.length;
 //oldCapacity>>1是把oldCapacity除以2的意思
 int newCapacity=oldCapacity+(oldCapacity>>1);
 //如果扩容后的值<我们的期望值,扩容后的值就等于我们的期望值
 if(newCapacity-minCapacity<0)
 newCapacity = minCapacity;
 //如果扩容后的值>jvm所能分配的数组的最大值,那么就用Integer的最大值
 if(newCapacity-MAX_ARRAY_SIZE>0)
 elementData=Arrays.copyOf(elementData,newCapacity);
}

注释相对来说已经比较详细了,这里需要注意以下几点:

  1. 上面有个问题是为什么需要声明两个空数组。我们在看到上面源码的时候有一个方法为calculateCapacity,这个方法内部逻辑只有在通过无参构造初始化ArrayList的时候才会改变将要返回的minCapacity。而返回的这个值将会决定下面的数组是否需要扩容。如果我们通过指定大小的方式初始化ArrayList并指定大小为0,这说明我们需要的就是一个空的ArrayList,不需要去扩容,你细品;
  2. 新增时,没有对值进行校验,所以新增值可以为null,且没有做重复值判断,所以元素可以重复;
  3. ArrayList中的数组的最大值是Integer.MAX_VALUE,超过这个值,JVM就不会给数组分配内存空间了;
  4. 扩容是原来容量大小+容量大小的一半,简单说就是扩容后的大小是原来容量的1.5倍。

扩容完成之后,就是简单的赋值了,赋值时并没有加锁,所以是线程不安全的。

扩容的本质

在grow方法的最后,扩容是通过Arrays.copyOf(elementData,newCapacity);这行代码实现的。这个方法实际上调用的方法是我们经常使用的System.arraycopy:

/**
*@param src 被拷贝的数组
*@param srcPos 从数组那里开始
*@param dest 目标数组
*@param destPos从目标数组那个索引位置开始拷贝
*@param length 拷贝的长度
*此方法是没有返回值的,通过dest的引用进行传值
*/
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

这个方法是一个native方法,虽然不能看到方法内部的具体实现,但通过参数也可以管中窥豹。这个方法会移动元素。所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以保持连续,时间复杂度 O(N)。由于数组又是一块连续的内存空间,能够根据索引快速访问元素。
上面也就解释了一开始那个问题:ArrayList为什么插入慢,查询快。

删除

ArrayList有多种删除方法,这里以根据值删除的方式进行说明(其他原理类似):

public boolean remove(Object o) {
 //如果要删除的值是null,删除第一个是null的值
 if(o==null){
 for(int index=0;index<size;index++)
  if(elementData[index]==null){
  fastRemove(index)
  return true;
  }
 }else{
 //如果要删除的值不为null,找到第一个和要删除的值相等的删除
 for(int index=0;index<size;index++)
  //这里是根据 equals来判断值相等的,相等后再根据索引位置进行删除
  //所以根据对象删除时,一般来说,如果你确定要删除的是某一类的业务对象,则需要重写equals
  if(o.equals(elementData[index]){
  fastRemove(index)
  return true;
  }
 }
 return false
}

核心其实是fastRemove方法:

private void fastRemove(int index){
 //记录数组的结构要发生变动了
 nodCount++;
 //numMoved表示删除index位置的元素后,需要从index后移动多少个元素到前面去
 //减1的原因,是因为size从1开始算起,index从0开始算起
 int numMoved=size-index-1;
 if(numMoved>0)
 //从index+1位置开始被拷贝,拷贝的起始位置是index,长度是numMoved
 System.arraycopy(elementData, index+1, elementData, index, numMoved);
 //数组最后一个位置赋值null,帮助GC(没有引用则自动回收了)
 elementData[--size] = null;
}

从源码中,我们可以看出,某一个元素被删除后,为了维护数组结构,我们都会把数组后面的元素往前移动,同时释放最后一个引用,便于回收。

总结

本文主要从ArrayList的源码入手,分别从初始化、新增、扩容、删除四个方面展开学习。我们发现ArrayList内部其实就是围绕了一个数组,在数组容量不足时将数组扩容至更大,所以也就自然被称作基于动态数组。
微信搜索Java成神之路或扫描下方二维码,发现更多Java有趣知识,让我们一起成长!

以上就是Java ArrayList使用总结的详细内容,更多关于Java ArrayList使用的资料请关注我们其它相关文章!

时间: 2021-03-27

Java并发包之CopyOnWriteArrayList类的深入讲解

前言 大家在学习Java的过程中,或者工作中,始终都绕不开集合.在单线程环境下,ArrayList就可以满足要求.多线程时,我们可以使用CopyOnWriteArrayList来保证数据安全.下面我们一起来看看CopyOnWriteArrayList类中的一些值得学习的方法. CopyOnWriteArrayList是一个线程安全的ArrayList,对其进行的修改操作都是在底层的一个复制的数组(快照)上进行的,也就是使用了写时复制策略实现的. 说明:代码部分,均基于JDK1.8 一.添加元素

Java如何把数组转换为ArrayList

这篇文章主要介绍了Java如何把数组转换为ArrayList,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 翻译自:How to Convert Array to ArrayList in Java? 本文分析了Stack Overflow上最热门的的一个问题的答案,提问者获得了很多声望点,使得他得到了在Stack Overflow上做很多事情的权限.这跟我没什么关系,我们还是先看看这个问题吧. 这个问题是"在Java中怎样把数组转换为Arra

Java ArrayList如何实现生成不重复随机数

在此之前我使用Java的数组实现了产生N-M之间的不重复的随机数,下面是使用数列ArrayList实现同样的功能,代码如下: /** * 随机生成 N--M,N个不重复随机数 使用ArrayList * * @param startRange 起始数字 * @param endRange 终止数字 * @param count 个数 */ public static ArrayList<Integer> getRandom(int startRange, int endRange, int c

java使用ArrayList实现斗地主(无序版)

本文实例为大家分享了java使用ArrayList实现斗地主的具体代码,供大家参考,具体内容如下 案例介绍 按照斗地主的规则,完成洗牌发牌的动作. 具体规则: 使用54张牌打乱顺序,三个玩家参与游戏,三人交替摸牌,每人17张牌,最后三张留作底牌. 案例分析 1. 准备牌 每张扑克牌牌由花色和数字两部分组成.可以使用花色集合与数字集合嵌套迭代完成扑克牌的组装. 2. 发牌 扑克牌组转完毕后由Collections类的shuffle方法打乱重排,最后3张当作底牌,剩余牌通过对3取模依次发牌. 3.

Java Vector和ArrayList的异同分析及实例讲解

在线程中有两种常用的方法,能够通过数组实现相应的功能,但除此之外在区别上也是很明显的.本篇就其中的代表方法ArrayList和Vector进行比较分析,一个是非线程安全,另一个是线程安全.在进行相同和不同点的分析之后,带来二者的实例代码对比,帮助大家体会它们的异同. 1.相同点 (1)都是有序集合. (2)数据不允许重复. (3)都实现了list接口. (4)都是通过数组实现的. (5)数组进行复制.移动.代价比较高,因此,适合随机查询和遍历,不适合插入和删除. 2.不同点 (1)ArrayLi

java中ArrayList和LinkedList的区别详解

ArrayList和LinkedList都实现了List接口,有以下的不同点: 1.ArrayList是基于索引的数据接口,它的底层是数组.它可以以O(1)时间复杂度对元素进行随机访问.与此对应,LinkedList是以元素列表的形式存储它的数据,每一个元素都和它的前一个和后一个元素链接在一起,在这种情况下,查找某个元素的时间复杂度是O(n). 2.相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者

Java中ArrayList集合的常用方法大全

ArrayList集合的创建 非泛型 创建ArrayList集合对象,可以添加任意Object子类元素至集合 //非泛型创建的ArrayList集合对象可以保存任何类型的值 ArrayList list = new ArrayList(); list.add("str");//存入String类型数据 list.add(23);//存入int类型数据 list.add(2.5);//存入double类型数据 list.add('c');//存入char类型数据 泛型 采用泛型创建Arr

java ArrayList.remove()的三种错误用法以及六种正确用法详解

java集合中,list列表应该是我们最常使用的,它有两种常见的实现类:ArrayList和LinkedList.ArrayList底层是数组,查找比较方便:LinkedList底层是链表,更适合做新增和删除.但实际开发中,我们也会遇到使用ArrayList需要删除列表元素的时候.虽然ArrayList类已经提供了remove方法,不过其中有潜在的坑,下面将介绍remove方法的三种错误用法以及六种正确用法. 1.错误用法 1.1.for循环中使用remove(int index),列表从前往后

java中为什么要谨慎使用Arrays.asList、ArrayList的subList

1. 使用Arrays.asList的注意事项 1.1 可能会踩的坑 先来看下Arrays.asList的使用: List<Integer> statusList = Arrays.asList(1, 2); System.out.println(statusList); System.out.println(statusList.contains(1)); System.out.println(statusList.contains(3)); 输出结果如下图所示: 然后,往statusLis

Java二维数组与动态数组ArrayList类详解

Java二维数组 Java 语言中提供的数组是用来存储固定大小的同类型元素. 1.二维数组初始化和声明 数组变量的声明,和创建数组可以用一条语句完成,如下所示: int a[][] = new int[2][3]; int[][] arr = {{1,2,3},{4,5,6},{7,8,9}}; 2.二维数组遍历 //遍历二维数组 public class Traverse_a_two_dimensional_array { public static void main(String[] ar

java中String,数组,ArrayList三者之间的转换

ArrayList转为String和数组 造一个元素为Integer的ArrayList 为list_int 造一个元素为String 的 ArrayList 为list_str ArrayList list_int = new ArrayList<Integer>(); //Integer的List list_int.add(1); list_int.add(3); list_int.add(5); list_int.add(9); ArrayList<String> list_

Java ArrayList遍历修改代码实例解析

用for-each 边遍历ArrayList 边修改时: public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add("aa"); list.add("bb"); list.add("cc"); list.add("dd"); System.out.println(list);

Java递归遍历文件目录代码实例

这篇文章主要介绍了Java递归遍历文件目录代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 在读取文件降序输出单词及其个数的基础上,将txt文件存入文件夹中,开始递归遍历文件目录,之后输出txt文件中的单词及其个数,仍然是降序排列. 代码如下 import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.Map

Java多线程CAS操作原理代码实例解析

CAS操作号称无锁优化,也叫作自旋:对于一些常见的操作需要加锁,然后jdk就提供了一些以Atomic开头的类,这些类内部自动带了锁,当然这里的锁并非是用synchronized来实现的,而是通过CAS操作来实现的: 一.下面是 AtomicInteger 的使用: package com.designmodal.design.juc01; import java.util.ArrayList; import java.util.List; import java.util.concurrent.

JAVA对象clone方法代码实例解析

1.Cloneable接口 这个接口一个方法都没有,但是要使用clone方法,就必须实现这个接口,否则抛出CloneNotSupportedException异常 2.clone方法的返回值 先附上两个类代码 package pojo; /** * @Author : ZGQ * @Date : 2020/3/11 22:12 * @Version : 1.0 */ public class Person implements Cloneable{ String name; int age; p

Java Session验证码案例代码实例解析

案例 用户输入用户名,密码以及验证码. 如果用户名和密码输入有误,跳转登录页面,提示:用户名或密码错误 如果验证码输入有误,跳转登录页面,提示:验证码错误 如果全部输入正确,则跳转到主页success.jsp,显示:用户名,欢迎您思路 在生成验证码的时候将它的值存入到session中,在比对的时候再取出来进行对比 代码index.jsp <%-- Created by IntelliJ IDEA. User: tanglei Date: 2020/6/26 Time: 下午12:48 To ch

java arrayList遍历的四种方法及Java中ArrayList类的用法

java arrayList遍历的四种方法及Java中ArrayList类的用法 package com.test; import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class ArrayListDemo { public static void main(String args[]){ List<String> list = new ArrayList<String

Java递归算法遍历部门代码示例

递归是一个非常有用的知识点.写点实例帮助自己记忆 中间有过程代码 首先一个javapojo类 package com.qcf.po; import java.util.HashSet; import java.util.Set; public class Depart { private long id; private String name; private String destion; //用户 Set<User> users=new HashSet<User>(); //

微信小程序 wx:for遍历循环使用实例解析

这篇文章主要介绍了微信小程序 wx:for遍历循环使用实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 效果图如下: 实现代码如下: type.js: // pages/type/type.js Page({ /** * 页面的初始数据 */ data: { types: "" }, editType: function (e) { var typeId = e.currentTarget.dataset['id']; cons

Java编程时间日期API实例解析

本文实例主要是关于Java8中的新特性,时间日期api的相关实例,具体如下: package com.effective.common.base.date; import java.time.Instant; import java.time.LocalDate; import java.time.LocalDateTime; import java.time.LocalTime; import java.time.Period; import java.time.ZoneId; import

Java数据封装树形结构代码实例

这篇文章主要介绍了Java数据封装树形结构代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.实体类 @data public class PublishServiceType implements Comparable<PublishServiceType>{ /** * */ private static final long serialVersionUID = -3572108154932898825L; /* * @see