ArrayList基本介绍
ArrayList是一个可变的数组，相当于动态数组。与Java中的数组相比，它提供了动态的增加和减少元素。
源码分析
成员变量
private static final long serialVersionUID = 8683452581122892189L;//用于序列化的Id
private static final int DEFAULT_CAPACITY = 10;//默认初始化的大小
private static final Object[] EMPTY_ELEMENTDATA = {};//空的数据
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空的数据
transient Object[] elementData; //存储数据的数组
private int size;//数组的大小
构造方法
ArrayList提供了三种构造方法
//指定初始化数组大小
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() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//传入一个集合
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
对于不传参数的构造方法，我们初始化的时候只会赋值一个空的数组，只有当我们第一次add的时候才会初始化elementData为默认的初始化大小(10)。对于c.toArray might (incorrectly) not return Object[] (see 6260652)可以看这篇文章主要是解决toArray返回的不是object[]的问题的一个规避方案。
Arrays#copyOf的参数说明
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
return copy;
}
| 参数 | 说明 |
|---|---|
| original | 原始数组 |
| newLength | 新数据的长度 |
| newType | 新数组的类型 |
Arrays#copyOf调用的是System#arraycopy
| 参数 | 说明 |
|---|---|
| src | 原始数组 |
| srcPos | 原始数组的起始位置 |
| dest | 目标数组 |
| destPos | 目标数组的起始位置 |
| length | 要复制的数组元素的数目 |
add方法
在数组的最后添加一个
public boolean add(E e) {
ensureCapacityInternal(size + 1); //检测数据是否需要扩容
elementData[size++] = e;//给数组最后的一位
return true;
}
扩容机制
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//第一次add的时候会走进这个if语句中，此时minCapacity是1，所以这个时候会创建的数据默认长度是10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)//数组满了，需要扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容的大小是原来的1.5倍
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);//创建新大小的数组，并将数来的值赋值给新的数组
}
在指定位置添加
public void add(int index, E element) {
rangeCheckForAdd(index);//验证 index的合法性
ensureCapacityInternal(size + 1); //检测数据是否需要扩容
System.arraycopy(elementData, index, elementData, index + 1, size - index);//将index及其以后的数据往数组后面移一位
elementData[index] = element;//将index的位置赋值为element
size++;
}
set方法
public E set(int index, E element) {
rangeCheck(index);//index合法性判断
E oldValue = elementData(index);//找到原始的值
elementData[index] = element;//将数组index替换为新值
return oldValue;//返回旧的值
}
E elementData(int index) {
return (E) elementData[index];
}
remove方法
指定元素删除
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {//如果remove的为元素空，找到为空的index
fastRemove(index);//删除
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {//找到object对应的index
fastRemove(index);//删除
return true;
}
}
return false;
}
fastRemove
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;//需要移动的数据大小
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);//将index之后的数据往前移一位
elementData[--size] = null; //最后一位清空
}
根据索引删除
public E remove(int index) {
rangeCheck(index);//index合法性检查
modCount++;
E oldValue = elementData(index);//index地方的值
int numMoved = size - index - 1;//需要移动的数据大小
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);//将index之后的数据往前移一位
elementData[--size] = null; //最后一位清空
return oldValue;
}
public E remove(int index)
public boolean remove(Object o)
当remove的是Integer的时候，remove(5)会调用public E remove(int index)，如果想调用public boolean remove(Object o)可以remove((Integer)5)
indexOf方法
如果有这个值则返回索引，否则返回-1。代码很简单，先遍历再判断。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
contains方法
contains本质是调用indexOf进行判断
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
iterator
ArrayList的遍历都是通过迭代器，我们可以通过iterator得到。通过调用hasNext和next来 不断获取下一个元素，直到遍历结束。高级for底层对于ArrayList也是转化为迭代器来实现的。
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
//数组中下一个元素
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];
}
//删除
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;//修改expectedModCount的值
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//省略一些代码
//验证expectedModCount和modCount
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
我们知道在遍历集合的时候不能调用集合的remove，否则会抛出ConcurrentModificationException。调用迭代器的remove则不会，我们通过对比可以看到，迭代器的remove也是通过集合remove去删除，但是还做了expectedModCount = modCount操作，这样保证了expectedModCount和modCount相等，checkForComodification不会抛出异常。抛出ConcurrentModificationException是由于触发了fast-fail机制引起的。
fail-fast和fail-safe
