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使用的资料请关注其它相关文章！