返回顶部类开头对HashMap作了详细的描述
可变数组实现了
List接口，实现所有可选的List操作，并允许存储所有元素，包括null。除了实现了List接口，这个类提供了一些方法来操作内部用于存储列表的数组的大小。（这个类跟Vector差不多， 但它不是同步的）其中
size,isEmpty,get,set,iterator和listIterator的时间复杂度恒定，add的时间复杂度是线性递增的， 也就是说增加n个元素需要O(n)的时间，所有其他操作都在线性时间内运行（大致来说）， 与LinkedList相比，ArrayList有更低的常量因子。第一个
ArrayList实例都有一个容量，这个容量是列表中存储元素的数组的大小， 它总是与列表大小一样。 随着元素被存储到列表， 容量也会自动增长。 除了时间复杂度， 容量自增的策略也并没有明确说明。在应用中如果需要向
ArrayList中添加大量的元素，可以通过ensureCapacity来增加容量， 这样可以减少自动扩容的次数。注意，ArrayList不是同步的， 如果多个线程同时访问同一个
ArrayList实例， 而其中至少有一个线程修改了列表的结构， 那么它必须通过外部来进行同步。（列表结构修改是指增加或者删除了至少一个元素， 或显式的变更了数组大小，仅设置了元素的值并不算结构修改）， 这通常中通过对一些对象的封装来实现同步。如果没有这个的对象， 那列表就需要被
Collections.synchronizedList包裹起来，最好是在创建的时候就这么做，这可以防止意外的非同步访问：
List list = Collections.synchronizedList(new ArrayList(...));
迭代器是通过
iterator()和listIterator(int)返回的， 如果在迭代器创建之后，列表结构发生了变化，除非是迭代器自身调用了remove()或者add(Object)方法，否则就会抛出异常ConcurrentModificationException, 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在将来某个不确定的时间冒着任意的、不确定的行为风险。请注意，快速失败的行为是不能被保证的，通常情况下，在存在异步并发修改的时候，不能得到完全保证。 快速失败迭代器在尽最大努力的基础上抛出
ConcurrentModificationException异常。因此，编写依赖于此异常的程序以确保其正确性是错误的行为： 迭代器的快速失败行为应仅用于检测错误。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 在容量为零时的空数组.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 在默认容量时的空数组。
* 用于和`EMPTY_ELEMENTDATA`作区分，这样才会知道在第一个元素加入时的扩容方式。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 列表中存储元素的数组. 列表的容量就是数组的大小。
* 对于`elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA`的列表，
* 将在第一个元素插入时扩容到`DEFAULT_CAPACITY`.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 列表的大小 (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* 构造一个指定初始容量的列表.
*
* @param initialCapacity 初始容量
* @throws IllegalArgumentException 如果指定容量是负值
*/
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);
}
}
/**
* 使用初始容量`10`构造一个空列表.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 构造一个包含指定集合的列表， 顺序是以集合的`iterator`返回结果为准.
*
* @param c 将要放入列表中的集合
* @throws NullPointerException 如果指定集合是空的
*/
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中有很多地方都是使用的Arrays.copyOf对数组进行操作， 同样的操作还有System.arraycopy, 但如果点开Arrays.copyOf会发现，其实它就是调用的System.arraycopy.
在ArrayList中只使用到了一个重载的方法：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
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;
}
也就是创建一个新数组，把旧数据拷进去，再把新数据返回出去。
/**
* 调整当前`ArrayList`实例的容量为其实际元素数量，
* 在应用中可以通过这个操作来最小化占用的存储空间。
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* 增加当前`ArrayList`实例的容量。
* 在必要的情况下，也判断当前传入的最小容量是否能装下列表中的元素.
*
* @param minCapacity 期望的最小容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 数组能分配的最大容量.
* 一些虚拟机会有一些头部信息.
* 尝试以最大值来设置容量可能会导致错误：
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 增加列表容量以确保至少可以以指定的最小容量存储所有元素
*
* @param 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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
相比于HashMap复杂的扩容机制， ArrayList要简单得多， 只要还有容量可以扩， 扩容之后，也没有达到容量上限，则扩容之后的容量就是oldCapacity + (oldCapacity >> 1).
例如初始容量为10, 扩大的容量为10的二进制1010加上右移一位101得到15。
再继续扩容的话， 则为1111加上111得到22.
10110加上1011得到33.
0 -> 10 -> 15 -> 22 -> 33 -> 49 …
当扩到超过最大值了，那就把那8个留给头部字符使用的空位也用上。
其它居然就没啥重点可言了，都是非常简单的操作。