ArrayList源码分析
测试一下typecho发布文章，文章主要是分析一下ArrayList的常见方法和主要逻辑
属性说明
/**
* 默认的初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 一个空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默认容量的空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 集合真正存储数组元素的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 集合大小
*/
private int size;
/**
* 记录list的修改次数
*/
protected transient int modCount = 0;构造方法
- 无参构造方法
public ArrayList() {
//初始化底层数组 elementData，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA来初始化一个空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}- 初始化list大小的构造方法
//initialCapacity为初始化集合大小
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}- 指定集合的构造方法
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
//这里的copyOf属于浅拷贝
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}add分析
- add(E e)
public boolean add(E e) {
//判断是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//尾插法
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//如果size+1之后超过当前数组的长度，则需要进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//确认minCapacity即size+1之后与初始容量谁大，返回大的值
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//将数据复制到一个新的数组里面
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
- add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
src 源数组。
srcPos 在源数组中的起始位置。
dest 目标数组。
destPos 目标数据中的起始位置。
length 要复制的数组元素的数量。
数组复制方法向后挪动一个位置,为将要插入的数据空出一个空位置来,等待数据插入.
所以如果在ArrayList集合中在已经存在数据的索引位置插入新数据,不会覆盖原数据,而是在该位置"挤一个空隙"插进去.
addAll的逻辑差不多，就不在描述
remove分析
- remove(int index)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}可以看到不管是新增还是删除，都是对数组的复制
- remove(Object o)
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
//遍历数组找到对象，然后根据下标删除，fastRemove还是remove(int index)的逻辑foreach和iterator
之前一直记得一个概念，说foreach不能用来删除，如果要删除请使用iterator，但是一直没有理解为什么
看一下foreach编译之后的代码，如下：
原始代码：
public static void forEachDel(){
ArrayList<String> list = new ArrayList<String>();
// 增加元素到list对象中
list.add("Item1");
list.add("Item2");
list.add("Item3");
list.add("Item4");
for (String val:list) {
if(val.equals("Item2")){
list.remove(val);
}
}
}
编译代码：
public static void forEachDel() {
ArrayList<String> list = new ArrayList();
list.add("Item1");
list.add("Item2");
list.add("Item3");
list.add("Item4");
Iterator var1 = list.iterator();
while(var1.hasNext()) {
String val = (String)var1.next();
if (val.equals("Item2")) {
list.remove(val);
}
}
}
可以看到foreach编译之后还是使用的Iterator ，但是元素的删除用的是原来的删除，前面分析的remove方法。我们来分析一下编译之后的foreach
//1、这里其实是创建了一个Iterator 对象，这个里面初始化了一个数据
Iterator var1 = list.iterator();
//初始化过程如下
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // 指向当前值的下标
int lastRet = -1; // index of last element returned; -1 if no such
//**expectedModCount 初始化成了一开始的modCount，这一行很重要**
int expectedModCount = modCount;
Itr() {}
…………
}
//2、var1.hasNext()判断当前下标值cursor是否等于size，如果不等于则可以往下取值
while(var1.hasNext()) {
String val = (String)var1.next();
if (val.equals("Item2")) {
list.remove(val);
}
}
//3、报错的位置就是这里 var1.next()
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)
at java.util.ArrayList$Itr.next(ArrayList.java:861)
at collection.ArrayList_test.forEachDel(ArrayList_test.java:108)
at collection.ArrayList_test.main(ArrayList_test.java:119)
//代码的第一次删除没有问题，确实把值删除了，但是在第一次的删除中，有一个值变化了：modCount，这个在list.remove方法里面可以看到。然后我们看下next方法：
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
//这里校验了这两个值是否相等，expectedModCount为迭代器初始化时候的值，而modCount 在第一次remove之后变化了，所以这里会抛出异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
所以使用foreach不能进行删除操作，如果需要删除，请使用迭代器，我们可以看下迭代器的删除代码，关键代码就一行：expectedModCount = modCount;，每次的删除都会修改expectedModCount ，所以在next方法取值时不会报错
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}