Java集合详述

1.1 JAVA集合关系图

1.2 ArrayList源码分析

1、简介

ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList，实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速访问、复制、序列化的。

2、重要属性

默认初始容量 10

1/**2*Defaultinitialcapacity.3*/4privatestaticfinalintDEFAULT_CAPACITY=10;

EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA这两个变量使用在构造函数中

这两个空的数组有什么区别？We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.区分第一次添加元素的时候知道elementData从空的构造函数还是有参构造函数初始化的。以便于确认如何扩容。

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};

存储数组列表元素的数组缓冲区

1/**2*ThearraybufferintowhichtheelementsoftheArrayListarestored.3*ThecapacityoftheArrayLististhelengthofthisarraybuffer.Any4*emptyArrayListwithelementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA5*willbeexpandedtoDEFAULT_CAPACITYwhenthefirstelementisadded.6*/7transientObject[]elementData;//non-privatetosimplifynestedclassaccess

数组中元素的大小，size是指elementData中实际有多少个元素，elementData.length为集合容量，表示集合当前最多可以容纳多少个元素

1/**2*ThesizeoftheArrayList(thenumberofelementsitcontains).3*/4privateintsize;

modCount定义在父类AbstractList中。记录List的操作次数。主要使用在Iterator中，防止在迭代的过程中集合被修改

1/**2*Thenumberoftimesthislisthasbeen<i>structurallymodified</i>\3*/4protectedtransientintmodCount=0;

3、构造函数

3.1 无参构造函数

需要注意的是无参构造函数，给elementData赋值的是一个空的数组，在第一次添加元素的时候才把容量扩大为10，不要被注释给误导了。此处可见无参构造器是将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData

1/**2*Constructsanemptylistwithaninitialcapacityoften.3*/4publicArrayList(){5this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;6}

3.2 构造一个初始容量为initialCapacity的ArrayList

当initialCapacity>0，初始化一个大小为initialCapacity的Object数组，赋值给elementData；当initialCapacity==0，将EMPTY_ELEMENTDATA赋值给elementData；否则，抛出异常。

1/**2*Constructsanemptylistwiththespecifiedinitialcapacity.3*/4publicArrayList(intinitialCapacity){5if(initialCapacity>0){6this.elementData=newObject[initialCapacity];7}elseif(initialCapacity==0){8this.elementData=EMPTY_ELEMENTDATA;9}else{10thrownewIllegalArgumentException("IllegalCapacity:"+initialCapacity);11}12}

3.3 通过指定的Collection来初始化一个ArrayList

将Collection转为数组并且赋值给elementData，elementData.length赋值给size；如果size != 0，则判断elementData类型是否为Object[]类型，不是则做一次转换（注意此处其实是一个官方bug解决方案）；如果size == 0则将EMPTY_ELEMENTDATA赋值给elementData，相当于new ArrayList(0)

1publicArrayList(Collection<?extendsE>c){2elementData=c.toArray();3if((size=elementData.length)!=0){4//c.toArraymight(incorrectly)notreturnObject[](see6260652)5if(elementData.getClass()!=Object[].class)6elementData=Arrays.copyOf(elementData,size,Object[].class);7}else{8//replacewithemptyarray.9this.elementData=EMPTY_ELEMENTDATA;10}11}

4、核心方法

4.1 add 操作

ensureCapacityInternal();

每次添加元素到集合中都会先确认集合容量的大小；

1publicbooleanadd(Ee){2ensureCapacityInternal(size+1);//IncrementsmodCount!!3elementData[size++]=e;4returntrue;5}

calculateCapacity();

判断elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA则取DEFAULT_CAPACITY和minCapacity的最大值，也就是10；此处验证了在第一次插入的时候才会给数组初始容量10；

1privatevoidensureCapacityInternal(intminCapacity){2ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));3}45privatestaticintcalculateCapacity(Object[]elementData,intminCapacity){6if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){7returnMath.max(DEFAULT_CAPACITY,minCapacity);8}9returnminCapacity;10}

modCount++;

记录操作次数；

minCapacity - elementData.length > 0；

数组长度不够时对数组进行扩容，执行grow()函数的逻辑

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};0

oldCapacity + (oldCapacity >> 1)

默认将数组的大小扩容到原来的1.5倍

newCapacity - minCapacity < 0

如果扩容后的容量不足，则将所需容量minCapacity赋值给newCapacity，扩容后数组大小就是申请的容量

newCapacity - MAX_ARRAY_SIZE > 0

如果扩容后的数组容量太大，超过了Integer.MAX_VALUE - 8的大小，则数组的大小为hugeCapacity(),(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};1

其余add()方法大同小异

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};2

4.2 remove 操作

rangeCheck(index);

检查index是否合法，当index >= size时，抛出IndexOutOfBoundsException异常；

modCount++;

记录集合的操作次数；

E oldValue = elementData(index);

取出移除元素，用于放回给方法调用者；

if (numMoved > 0)

判断当前删除的集合元素是否时数组的最后一个元素，如果不是最后一个元素，则调用System.arraycopy()方法做一次数组拷贝；如果移除的元素是最后一个元素或者在数组复制结束之后，将数组的最后一个元素置为null，等待GC垃圾回收；--size数组的大小减一；

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};3

4.3 get 操作

rangeCheck(index);

检查index是否合法，当index >= size时，抛出IndexOutOfBoundsException异常；

elementData(index);

由于ArrayList的底层是由数组实现的，所有获取元素直接调用数组的随机访问即可；

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};4

5、Iterator

5.1 前言

Java开发初级工程师在使用for遍历集合的时候，由于使用不正确的API方法对集合进行remove()操作，经常会抛出java.util.ConcurrentModificationException，因此我们来从源码的层面仔细的探究一下为什么会产生ConcurrentModificationException以及如何解决这个异常！foreach循环又称增强for循环，是jdk1.5为了简化数组或者和容器遍历而产生，foreach循环的适用范围：对于任何实现了Iterable接口的容器都可以使用foreach循环。foreach语法的冒号后面可以有两种类型，一种是数组类型；一种是实现了Iterable接口的类，因此在使用foreach循环遍历ArrayList的时候，可以看作就是在使用List的迭代器进行遍历

如下代码，foreach遍历list集合时，调用list.remove(s)方法，控制台输出了预期ConcurrentModificationException异常

5.2 ArrayList中Iterator

本质上返回的是一个Itr实例化对象

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};5

ArrayList定义了一个Itr内部类实现了Iterator接口，Itr内部有三个属性。

cursor：代表的是下一个访问的元素下标；

lastRet：代表的是上一个访问元素的下标，默认值为-1；

expectedModCount：代表的是对ArrayList修改的次数，初始值等于modCount

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};6

hasNext();

判断是否存在下一个元素，返回值只要cursor下一个元素的下标不等于集合的元素个数size就返回true，其他情况返回false

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};7

next() ;

获取集合中的下一个元素

checkForComodification();

判断modCount与expectedModCount是否相等，不相等抛出ConcurrentModificationException异常

i = cursor；i >= size；i >= elementData.length

判断cursor的大小，如果cursor的值大于集合中元素的个数，抛出NoSuchElementException异常；如果cursor大于了数组的长度抛出ConcurrentModificationException异常。

cursor = i + 1；lastRet = i

如果上述情况均满足，则正常获取下一个元素，cursor和lastRet都自增1

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};8

lastRet < 0；

如果lastRet 小于0，则抛出IllegalStateException异常，由此可以看出，调用remove()之前，必须先调用next()方法重置lastRet的值，否则在lastRet默认值为-1的情况下，对集合中的元素进行移除会直接抛出异常；

checkForComodification()；

判断modCount与expectedModCount是否相等，不相等抛出ConcurrentModificationException异常

ArrayList.this.remove(lastRet);

调用ArrayList的remove方法，移除元素

cursor = lastRet;lastRet = -1;expectedModCount = modCount;

将lastRet的值赋值给cursor，相当于-1；将lastRet 重置为-1；将modCount赋值给expectedModCount

1/**2*Sharedemptyarrayinstanceusedforemptyinstances.3*/4privatestaticfinalObject[]EMPTY_ELEMENTDATA={};56/**7*Sharedemptyarrayinstanceusedfordefaultsizedemptyinstances8*/9privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};9

5.3 图解

初始化时Itr中的cursor=0；lastRet=-1；modCount = 4；expectedModCount=4；注意modCount 的值是在调用ArrayList方法的add()方法时进行modCount++;而expectedModCount的值Itr初始化时，默认等于modCount。

当foreach循环到D元素的时候，cursor=2；lastRet=1；modCount = 4；expectedModCount=4；

当调用list.remove(s)移除了元素“D”之后，cursor=2；lastRet=1；modCount = 5；expectedModCount=4；注意此处调用的时ArrayList的remove()方法

由于ArrayList的foreach遍历实质上相当于ArrayList中的Itr迭代，所以在Itr内部类中的next()方法被调用时，checkForComodification()方法中比较modCount 和 expectedModCount的值，发现二者不相等，则抛出ConcurrentModificationException异常！

1/**2*ThearraybufferintowhichtheelementsoftheArrayListarestored.3*ThecapacityoftheArrayLististhelengthofthisarraybuffer.Any4*emptyArrayListwithelementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA5*willbeexpandedtoDEFAULT_CAPACITYwhenthefirstelementisadded.6*/7transientObject[]elementData;//non-privatetosimplifynestedclassaccess0

5.4 异常解决

调用Iterator的remove()方法即可

1/**2*ThearraybufferintowhichtheelementsoftheArrayListarestored.3*ThecapacityoftheArrayLististhelengthofthisarraybuffer.Any4*emptyArrayListwithelementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA5*willbeexpandedtoDEFAULT_CAPACITYwhenthefirstelementisadded.6*/7transientObject[]elementData;//non-privatetosimplifynestedclassaccess1