ArrayList源码解析
最近刚刚来到掘金,感觉是个很不错的技术交流平台,准备以后常驻.把自己以前写的一些东西都发出来.目前的计划是写mysql的整个系列,目前也写完索引部分.List这两篇博文是很早之前就写好的,现在发表出来.希望大家通过阅读我的博文有一定的收获.
在工作中集合list集合用的相对来说比较多,而ArrayList可以说是业务端的同学天天都在用.对于ArrayList内部的机制我也是一知半解,所以决定好好看看源码.我是用IEDA去查看源码,复制一份JDK源码,然后用IDEA打开,找到对应的类,设置一个IDEA,这样可以方便你直接在代码内部添加注释.还有一点,千万别直接把你环境配置的JDK直接打开,避免在你查看源码的过程修改了某个地方,影响到你的正常项目运行.
1.1 ArrayList的体系
Iterable : iterable接口里定义了返回iterator的方法，相当于对iterator的封装，同时实现了iterable接口的类可以支持for each循环;
Collction : 集合框架中的根接口,下面有三大子接口.List Set Queue;
AbstractCollection: 实现了Collection的一些接口,同时也定义了一些抽象方法交给子类实现.
List : List接口定义了一些公用的接口,比如 toArray() size() add()等接口;
AbstractList :AbstractList 是一个抽象类，实现了List接口，是隶属于Java集合框架中的根接口 Collection 的分支
1.2 ArrayList原理
我们先看一下ArrayList的构造方法.
/**
* 有参构造 int类型 集合的大小
*/
publicArrayList(intinitialCapacity) {
//如果参数大于0,缓冲数组的大小就为该参数
if(initialCapacity>0) {
this.elementData=newObject[initialCapacity];
//如果参数等于0,创建一个空的实例数组
}elseif(initialCapacity==0) {
this.elementData=EMPTY_ELEMENTDATA;
}else{
//异常为非法容量 + 参数
thrownewIllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
* 无参构造
*/
publicArrayList() {
//缓冲数组为空的默认大小的共享实例
this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//有参构造 参数为任意类或者E的子类
//任意类或者E的子类,孙子类等collection都可以构造一个ArrayList出来
publicArrayList(Collection<?extendsE>c) {
//转为缓存数组
elementData=c.toArray();
//将数组的长度赋值给size,如果数组长度不等于0
if((size=elementData.length)!=0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//缓存数组的class不等于object类型数组的class
if(elementData.getClass()!=Object[].class)
//copyOf方法:返回一个数组
elementData=Arrays.copyOf(elementData,size,Object[].class);
}else{
// replace with empty array.
//替换为一个空的数组
this.elementData=EMPTY_ELEMENTDATA;
}
}
以上就是ArrayList的构造方法,注释是我自己一行一行写出来的,可能会有所误解,欢迎批评指正.
1.3 arrayList常用的方法
add() : 向集合内部添加元素,这个方法其实是Collection接口中定义的,AbstractCollection抽象类中实现这个方法,ArrayList中重写了这个方法.如果直接调用AbstractCollection中的add方法,那么只会抛出一个不支持操作的异常.需要注意一点就是add()一共有两个,但是其中一个是有boolean的返回值,另一个是void并没有返回值.
boolean返回值add(),元素添加是为最后一位.
publicbooleanadd(Ee) {
ensureCapacityInternal(size+1);// Increments modCount!!
elementData[size++]=e;
returntrue;
}
首先看一下 ensureCapacityInternal(size + 1)这个方法
privatevoidensureCapacityInternal(intminCapacity) {
if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//max方法为一个三元运算,参数类型为int类型,(a >= b) ? a : b;
//size+1 大于等于 初始值 返回初始值10
minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
又调用了ensureExplicitCapacity()方法
privatevoidensureExplicitCapacity(intminCapacity) {
modCount++;
//需要的大小大于底层数组的大小
if(minCapacity-elementData.length>0)
grow(minCapacity);
}
继续调用了grow()方法,这个方法很关键,先看源码
privatevoidgrow(intminCapacity) {
//数组长度赋值给oldCapacity
intoldCapacity=elementData.length;
//oldCapacity >> 1 相当于 oldCapacity / 2
//newCapacity 为数组长度的1.5倍
intnewCapacity=oldCapacity+(oldCapacity>>1);
//newCapacity小于minCapacity
if(newCapacity-minCapacity<0)
//minCapacity赋值于newCapacity
newCapacity=minCapacity;
//newCapacity大于MAX_ARRAY_SIZE
if(newCapacity-MAX_ARRAY_SIZE>0)
newCapacity=hugeCapacity(minCapacity);
//通过copyOf方法返回一个数组
elementData=Arrays.copyOf(elementData,newCapacity);
}
整体来说 如果size+1小于10,那么minCapacity就是10,10就是默认大小.如果大于10,那么minCapacity则为size+1.
minCapacity-lementData.length 如果size+1比底层数组小,那么可以继续向默认数组中添加元素.如果size+1大于底层数组,就调用grow()进行扩容.
grow()这个方法就是arrayList自动扩容的方法.newCapacity为数组的1.5倍,先判断newCapacity是否小于minCapacity,也就是size+1如果小于那么将minCapacity赋值于newCapacity.
再判断newCapacity是否大于MAX_ARRAY_SIZE,关于MAX_ARRAY_SIZE下面有代码.
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
如果大于就调用hugeCapacity()方法
privatestaticinthugeCapacity(intminCapacity) {
//minCapacity 小于 0 报错
if(minCapacity<0)// overflow
thrownewOutOfMemoryError();
//minCapacity大于MAX_ARRAY_SIZE吗?
//大于返回Integer.MAX_VALUE
//小于返回MAX_ARRAY_SIZE
return(minCapacity>MAX_ARRAY_SIZE)?
Integer.MAX_VALUE:
MAX_ARRAY_SIZE;
}
最后将elementData,也就是底层数组.lenth变为newCapacity.总结起来说,arrayList的扩容机制其实就修改底层数组的大小.继续回头add()方法往下看:
elementData[size++] = e;
这个其实很好理解了,e就是你要添加的那个新的元素,size++就是新元素在底层数组中的位置.
return true;最后返回一个 true 添加成功
void add(),
publicvoidadd(intindex,Eelement) {
//校验index
rangeCheckForAdd(index);
ensureCapacityInternal(size+1);// Increments modCount!!
System.arraycopy(elementData,index,elementData,index+1,
size-index);
elementData[index]=element;
size++;
}
rangeCheckForAdd(index);
privatevoidrangeCheckForAdd(intindex) {
//如果index大于size或者index小于0 就抛出异常
if(index>size||index<0)
thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
}
ensureCapacityInternal(size + 1);
这个在前面有说过,就不在细说,可以去看一下前面add()带返回值的那个解析.
System.arraycopy(elementData, index, elementData, index + 1,size - index);
调用System提供的arraycopy(),这是一个静态native方法,native这里不进行说明,可以百度进行查看.这个方法就是现数组之间的复制。
elementData:底层数组.
index:数组要复制的起始位置.
elementData:复制后的数组.
index + 1:数组放置的起始位置.
size - index:复制的长度
elementData[index] = element;
将要添加的元素放入指定的位置.
size++
将集合的长度+1.
