ArrayList 概述
ArrayList 是实现List接口的动态数组，每个ArrayList实例都有一个默认初始容量10，每次添加数据时，都会检测是否应该扩容，扩容时会使用拷贝数组的方式， 这样会造成一定的性能问题，所以应该在初始化的时候指定容量大小。在添加大量元素前，也可以使用ensureCapacity进行扩容，防止减少扩容的次数。
ArrayList 是非线程安全的，可以使用Collections.synchronizedList(new ArrayList(...) 生成一个线程安全的ArrayList，或者使用CopyOnWriteList代替。
ArrayList 源码分析(基于JDK 1.8)
- 底层使用数组
transient Object[] elementData;
private static final int DEFAULT_CAPACITY = 10;
底层使用数组，数组的默认初始容量为10.
- 构造函数
ArrayList 有三个构造函数
- ArrayList(int initialCapacity):可以设置初始容量的大小
- ArrayList()：生成一个默认大小容量的数组
- ArrayList(Collection<? extends E> c):生成一个包含指定collection的列表
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 {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
- 新增
ArrayList 提供多个add方法，这里只列出其中一个，基本上所有的 add 方法都是先进行扩容、然后进行数组拷贝，是集合中的元素呆在自己应该在的位置。
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++;
}
- 删除
ArrayList 提供多个remove犯法，这里只列出其中一个，基本所有的remove方法都会是modCount改变，然后进行数组拷贝。
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;
}
- 查找
ArrayList 通过数组下表直接获取对应索引的元素，速度表较快。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
- 扩容
ArrayList 扩容为先扩容原来容量的1.5倍，如果仍然小于需要扩容的数量，则扩容为需要的数量，扩容时，会进行数组拷贝
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
当然，ArrayList 中还存在减少容量的方法，减少对内存的占用
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
- 迭代
迭代器中有多个方法，但只介绍几个重要的地方，因为不同的线程中进行迭代和对集合结构的修改会触发fail-fast，在生成迭代器时，会使用list的modCount作为自己的expectedModCount,再调用一些方式时，会检测modCount与expectedModCount的值，如果相同，继续执行，如果不同，则会触发fail-fast.
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;
@SuppressWarnings("unchecked")
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() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
- 子集合
子集合的大部分操作是调用父集合的方法进行的，所以对子集合的更改也会反映到父集合上，但不同的线程中对父集合的结构修改则可能会出发fail-fast.
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
rangeCheck(index);
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public int size() {
checkForComodification();
return this.size;
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
}
ArrayList 优缺点
- 优点
- 访问速度快
- 缺点
- 插入、删除速度较慢
- 线程不安全
