从源码角度彻底搞懂ArrayList

天天使用的ArrayList，今天咱们从深层次的源码角度来分析分析。...

https://blog.csdn.net/xfhy_

• 快速随机访问
• 允许存放多个null元素
• 底层是Object数组
• 增加元素个数可能很慢(可能需要扩容),删除元素可能很慢(可能需要移动很多元素),改对应索引元素比较快

来看下源码中的定义

public class ArrayList extends AbstractList



implements List, RandomAccess, Cloneable, java.io.Serializable

• 可以看到继承了AbstractList,此类提供 List 接口的骨干实现，以最大限度地减少实现”随机访问”数据存储（如数组）支持的该接口所需的工作.对于连续的访问数据（如链表），应优先使用 AbstractSequentialList，而不是此类.
• 实现了List接口,意味着ArrayList元素是有序的,可以重复的,可以有null元素的集合.
• 实现了RandomAccess接口标识着其支持随机快速访问,实际上,我们查看RandomAccess源码可以看到,其实里面什么都没有定义.因为ArrayList底层是数组,那么随机快速访问是理所当然的,访问速度O(1).
• 实现了Cloneable接口,标识着可以它可以被复制.注意,ArrayList里面的clone()复制其实是浅复制(不知道此概念的赶快去查资料,这知识点非常重要).
• 实现了Serializable 标识着集合可被序列化。

/**



* ArrayList 默认的数组容量



*/



private static final int DEFAULT_CAPACITY = 10;



/**



* 用于空实例的共享空数组实例



*/



private static final Object[] EMPTY_ELEMENTDATA = {};



/**



* 另一个共享空数组实例，用的不多,用于区别上面的EMPTY_ELEMENTDATA



*/



private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};



/**



* ArrayList底层的容器



*/

transient Object[] elementData; // non-private to simplify nested class access



//当前存放了多少个元素   并非数组大小

private int size;

无参构造方法

/**



* 构造一个初始容量为10的空列表。



*/

public ArrayList() {



this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

指定初始容量的构造方法

public ArrayList(int initialCapacity) {



//容量>0 -> 构建数组



if (initialCapacity > 0) {



this.elementData = new Object[initialCapacity];



} else if (initialCapacity == 0) {



//容量==0  指向空数组



this.elementData = EMPTY_ELEMENTDATA;



} else {



//容量 c) {



//判空



Objects.requireNonNull(c);



return batchRemove(c, false);

}



//complement是true 则移除elementData中除了c以外的其他元素

//complement是false 则移除c和elementData(当前列表的数组)都含有的元素

private boolean batchRemove(Collection c, boolean complement) {



//1. 引用不可变



final Object[] elementData = this.elementData;



//r 是记录整个数组下标的, w是记录有效元素索引的



int r = 0, w = 0;



boolean modified = false;



try {



//2. 循环遍历数组



for (; r < size; r++)



//3. 如果complement为false  相当于是取c在elementData中的补集,c包含则不记录,c不包含则记录



//如果complement为true  相当于是取c和elementData的交集,c包含则记录,c不包含则不记录



if (c.contains(elementData[r]) == complement)



elementData[w++] = elementData[r];   //r是正在遍历的位置  w是用于记录有效元素的   在w之前的全是有效元素,w之后的会被"删除"



} finally {



// Preserve behavioral compatibility with AbstractCollection,



// even if c.contains() throws.



//4. 如果上面在遍历的过程中出错了,那么r肯定不等于size,于是源码就将出错位置r后面的元素全部放到w后面



if (r != size) {



System.arraycopy(elementData, r,



elementData, w,



size - r);



w += size - r;



}



//5. 如果w是不等于size,那么说明是需要删除元素的    否则不需要删除任何元素



if (w != size) {



// clear to let GC do its work



//6. 将w之后的元素全部置空  因为这些已经没用了,置空方便GC回收



for (int i = w; i < size; i++)



elementData = null;



modCount += size - w;



//7. 记录当前有效元素



size = w;



//8. 标记已修改



modified = true;



}



}



return modified;

}

public void clear() {



modCount++;



// clear to let GC do its work



for (int i = 0; i < size; i++)



elementData = null;



size = 0;

}

//这是protected方法    移除相应区间内的所有元素

protected void removeRange(int fromIndex, int toIndex) {



modCount++;



//1. toIndex后面的元素需要保留下来,记录一下toIndex后面的元素个数



int numMoved = size - toIndex;



//2. 将toIndex后面的元素复制到fromIndex处



System.arraycopy(elementData, toIndex, elementData, fromIndex,



numMoved);



// clear to let GC do its work



//3. 将有效元素后面的元素置空



int newSize = size - (toIndex-fromIndex);



for (int i = newSize; i < size; i++) {



elementData = null;



}



//4. 记录当前有效元素个数为size - (toIndex-fromIndex)  ,即减去那个区间内的元素个数



size = newSize;

}

public E set(int index, E element) {



//1. 入参检测



rangeCheck(index);



//2. 记录原来该index处的值



E oldValue = elementData(index);



//3. 替换



elementData[index] = element;



return oldValue;

}

E elementData(int index) {



return (E) elementData[index];

}



/**

* 返回指定位置处元素

*/

public E get(int index) {



rangeCheck(index);



return elementData(index);

}

/**

* Returns an iterator over the elements in this list in proper sequence.

* The returned iterator is fail-fast.

* @return an iterator over the elements in this list in proper sequence



以适当的顺序返回此列表中元素的迭代器。  fail-fast:快速失败?

*/

public Iterator iterator() {



return new Itr();

}