关于 ArrayList

包括之前的 HashMapLinkedList, 都是基于 JDK 7的(应该全面拥抱JDK 8了)。

ArrayList 的 DOC 注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
* <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
* <tt>Vector</tt>, except that it is unsynchronized.)
* (ArrayList) 通过 List 接口实现的容量可变数组。实现了 list 的所有可选操作(方法),并且允许添加所有元素,包括 null。除了实现了 List 的接口,ArrayList 还提供了修改用来容纳 list 的数组的 size 的方法(ArrayList 是非线程安全的,除此以外大致上与 Vector 相同)。
* <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
* <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
* time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
* that is, adding n elements requires O(n) time. All of the other operations
* run in linear time (roughly speaking). The constant factor is low compared
* to that for the <tt>LinkedList</tt> implementation.
* size,isEmpty,get,set,iterator 方法和 listIterator 操作的时间复杂度是O(1)的(常数级)。add() 方法的时间复杂度是O(1)+的(amortized constant time)(因为涉及到list 扩容,扩容也需要时间,需要把这部分时间平均分摊到每次 add 操作中。),也就是说,添加元素的时间复杂度为O(n)。其他操作的时间复杂度大致为O(n),常量值 n 通常要比 LinkedList 的时间复杂度中常量值要小(即,其他操作要比 LinkedList 的其他操作要快一点)。
* <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
* the size of the array used to store the elements in the list. It is always
* at least as large as the list size. As elements are added to an ArrayList,
* its capacity grows automatically. The details of the growth policy are not
* specified beyond the fact that adding an element has constant amortized
* time cost.
* 每一个 ArrayList 实例都有一个 capacity(容量)属性,该属性不小于 list 的 size。当向 ArrayList 中添加元素时,它的 capacity 会自动增长。除了添加一个元素具有固定的摊余时间成本之外,增长规则的细节没有被指定。
* <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
* before adding a large number of elements using the <tt>ensureCapacity</tt>
* operation. This may reduce the amount of incremental reallocation.
* 在程序中添加大量元素之前,可以调用 ensureCapacity() 方法来对 ArrayList 进行扩容。这样可以减少多次扩容所花费的时间(可以减少扩容的次数)
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access an <tt>ArrayList</tt> instance concurrently,
* and at least one of the threads modifies the list structurally, it
* <i>must</i> be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
* resizes the backing array; merely setting the value of an element is not
* a structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the list.
* 需要注意的是,ArrayList 对 List 的实现是非同步的。如果多线程同时请求对 ArrayList 的访问,并且至少会有一个线程对 ArrayList 进行结构性修改(结构性修改是指添加或删除一个以上的元素,或者显式的修改了其数组的大小。仅仅修改元素值并非结构性修改),那么务必在 ArrayList 外部进行 synchronized 修饰。这通常是通过 synchronized 修饰 封装了 list 的某个对象来实现的。
* If no such object exists, the list should be "wrapped" using the
* {@link Collections#synchronizedList Collections.synchronizedList}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the list:<pre>
* List list = Collections.synchronizedList(new ArrayList(...));</pre>
* 如果(手头儿)没有这样的对象,那么应该用 Collections.synchronizedList 包裹 list。该操作最好在创建 list 时进行,以防意外的非同步访问 list。
* <p><a name="fail-fast"/>
* The iterators returned by this class's {@link #iterator() iterator} and
* {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
* if the list is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own
* {@link ListIterator#remove() remove} or
* {@link ListIterator#add(Object) add} methods, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of
* concurrent modification, the iterator fails quickly and cleanly, rather
* than risking arbitrary, non-deterministic behavior at an undetermined
* time in the future.
* 通过 ArrayList 的 iterator() 方法,或者 listIterator(int) 方法返回的 iterator 都是 fail-fast(快速失效)的:如果在创建 iterator 之后,任何对 list 的结构性修改,都会抛出 ConcurrentModificationException,除了 iterator 本身的 remove() 和 add() 方法。因此,在面临并发对 list 的修改时,iterator 会快速而干净的失效,而不是在未来不确定的时间冒着任意的、不确定的风险。
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
* 另外,需要注意的是,,iterator 的 fail-fast 行为是不能被保证的,,通常来说,在并发非同步对 list 的修改时,任何硬性的保证都是不可能的。fail-fast 会让 iterator 尽可能抛出 ConcurrentModificationException。因此,在程序中通过依赖抛出 ConcurrentModificationException 异常来保证自身的正常运行是错误的:fail-fast 行为只应该用来 debug。
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @since 1.2
*/

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 的类属性及构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
* Default initial capacity.
* 默认初始 capacity, 10
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* Shared empty array instance used for empty instances.
* 对所有由无参构造函数创建的空实例共享的空数组对象
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
* 临时用来存储 ArrayList 中元素的数组。 ArrayList 对象的长度就是这个缓存数组的长度。任何空 ArrayList ,且 elementData == EMPTY_ELEMENTDATA,在添加第一个元素时,数组将被扩展到默认大小(DEFAULT_CAPACITY, 10)。
* (因为是临时的,所以用 transient 修饰,不会被序列化)
*/
private transient Object[] elementData;

/**
* The size of the ArrayList (the number of elements it contains).
* ArrayList 的 size(包含的元素的数量)。
* @serial
*/
private int size;

/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
* 允许分配给数组的最大的容量。
* 一些虚拟机实现会在数组预留一些 header words。
* 视图分配更大的数组可能会造成 OOM:所需数组大小超出虚拟机限制。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
* Constructs an empty list with the specified initial capacity.
* 通过指定初始 capacity 大小来构造一个空 list
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
super();
// 初始容量小于零时,会抛出 IllegalArgumentException
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 初始化指定大小的临时对象数组
this.elementData = new Object[initialCapacity];
}

/**
* Constructs an empty list with an initial capacity of ten.
* 构造一个空 list,当向该 list 添加元素时,需先扩展数组到默认初始容量大小,即 10.
*/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}

/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 按照 collection 迭代器返回元素的顺序构造包含指定 collection 的元素的 list。
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
// 如果 c 为 null,此处会抛 NPE
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 如果 elementData 不是对象数组,还需要将其复制到新的对象数组中。
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}

add()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/**
* Appends the specified element to the end of this list.
* 添加指定元素到 list 末尾元素后边。
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 确保内部数组容量足够大,初始状态下 size 为 0。
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
// 如果 ArrayList 由无参构造方法构造,则 minCapacity 为 1。
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 确保扩容到指定大小的容量
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// 结构修改次数 +1
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* 扩容,以容纳指定长度的最小数量的元素
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
// 原容量
int oldCapacity = elementData.length;
// 新容量 = oldCapacity * 1.5
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:
// 通常 minCapacity = size + 1,所以大部分情况都是执行到这里
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 带符号二进制溢出,符号位为 1,小于零,,即 OOM。
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
* 添加指定元素到指定位置。将当前索引位置的元素(如果有的话)及其后边的元素统一右移。
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 检查 index 是否不小于零,且小于 size
rangeCheckForAdd(index);
// list 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 调用 native 方法复制 插入索引位置之后部分的数组 到原数组中
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* A version of rangeCheck used by add and addAll.
* 为 add() 和 addAll() 方法准备的另一个版本的 rangeCheck 方法。
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);

get()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Returns the element at the specified position in this list.
* 返回 list 中指定位置的元素
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
// 如果索引合规,则至今返回数组相应索引位置的元素。
return elementData(index);
}

/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
* 检查指定的索引是否在范围内。如果不在,将抛出合适的运行时异常。该方法不会检查索引是否为负:索引总是在访问数组之前立即使用,,如果在索引为负,会抛出 ArrayIndexOutOfBoundsException 异常。
*/
private void rangeCheck(int index) {
// 如果索引大于数组的实际大小,会抛出数组越界异常。
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
* 构建数组越界异常的详情信息。在很多错误处理代码可能的重构中,这个详情大纲一直在服务器模式和客户端模式中表现的一直很好。
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}

set()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Replaces the element at the specified position in this list with
* the specified element.
* 用指定的元素替换 list 中指定位置的元素
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
// 是否大于数组的 size
rangeCheck(index);
// 记录数组中当前位置的元素
E oldValue = elementData(index);
// 替换指定索引位置为新元素
elementData[index] = element;
// 返回原索引位置的元素
return oldValue;
}

remove()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
* 移除当前 list 中指定位置上的元素。将该位置后边的元素左移(当前索引减一)
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
// 检查索引是否超出数组的 size
rangeCheck(index);
// list 结构性更改次数 +1
modCount++;
// 记录数组当前索引原元素
E oldValue = elementData(index);
// 计算要移动的数组的长度。
int numMoved = size - index - 1;
// 如果删除的不是 list 的末尾元素,则将要删除的索引位之后的元素向左移动一位。
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 数组长度-1,并将更新后的数组末尾元素置空
// 此处留坑,,在我的印象中,假如数组长度为10,那么即使是只有零索引处有值,其他位置的元素皆为空,其他对象还持有该数组对象的引用,那么GC时也不会将该数组对象回收。
elementData[--size] = null; // clear to let GC do its work
// 返回索引位置原元素
return oldValue;
}

/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
* 从当前 list 中删除指定元素的第一个匹配项,如果 list 中存在指定元素的话。严谨来说是删除索引值最小的匹配项,像是满足这样的条件:(o==null?get(i)==null:o.equals(get(i))),如果 list 中存在 o 的话。如果 list 中存在 o,则返回 true(或者说,本次调用导致了 list 改变)
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
// 遍历删除找到的第一个 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 remove method that skips bounds checking and does not
* return the value removed.
* 私有删除方法,该方法跳过了索引是否越界的检查,且不返回删除的元素。精简版的 remove()
*/
private void fastRemove(int index) {
// 结构性更改次数 +1
// ...
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
}

iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
* Returns an iterator over the elements in this list in proper sequence.
* 以正确的顺序返回该 list 中元素的迭代器
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
* 返回的 iterator 是 fail-fast 的
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr
* AbstractList.Itr 的优化版本
*/
private class Itr implements Iterator<E> {
// index of next element to return 要返回的下一个元素的索引
int cursor;
// index of last element returned; -1 if no such 上一个返回元素的索引,如果该元素不复存在(调用iterator.remove()删除当前元素),则赋值为 -1
int lastRet = -1;
// 记录当前 list 结构性修改次数
int expectedModCount = modCount;

// 是否还有未迭代过的元素
public boolean hasNext() {
// 如果下一个要返回的元素的索引值不等于(即,小于)数组长度,则说明未迭代完成
return cursor != size;
}

// 返回下一个要迭代的元素
@SuppressWarnings("unchecked")
public E next() {
// 检查记录 list 结构性更改次数后(即,私有内部类 Itr 初始化完成后),是否有其他操作对 list 进行过结构性修改。如果有,则抛出 ConcurrentModificationException。
checkForComodification();
int i = cursor;
// 如果要迭代的下一个元素的索引值不小于数组的长度,则抛出 NoSuchElementException
if (i >= size)
throw new NoSuchElementException();
// 复制当前 list 的内部实现数组 elementData
Object[] elementData = ArrayList.this.elementData;
// 如果要迭代的下一个元素的索引不小于 elementData 的长度,则抛出 ConcurrentModificationException。
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 将 cursor 指向要迭代的下一个(本次 next 方法调用完成之后)元素的索引
cursor = i + 1;
// 更新返回的最后一个元素的索引值,同时返回本次要迭代的元素
return (E) elementData[lastRet = i];
}

public void remove() {
// 如果当前元素(next 方法中,int i = cursor;lastRet = i;)索引小于零,抛出 IllegalStateException,此时 list 处于非法状态。
if (lastRet < 0)
throw new IllegalStateException();
// 检查 iterator 初始化之后,是否有其他线程对 list 进行了结构性修改。
checkForComodification();

try {
// 调用 ArrayList 的 remove() 移除迭代器当前指向的元素
ArrayList.this.remove(lastRet);
// 进行 remove 操作后,目标索引后边的元素左移,即目标索引指向新的(尚未迭代过)元素。将迭代器下次要返回的元素指向目标索引的元素
cursor = lastRet;
// 本次迭代的元素已被删除,所以为 lastRet 赋值 -1
lastRet = -1;
// 更新 list 结构性更改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

总结

ArrayList 是容量可以改变的非线程安全集合。内部实现使用数组进行存储,集合扩容时会创建更大的数组空间,把原有数据复制到新数组中。ArrayList 支持对元素的快速随机访问,但是插入与删除时速度通常很慢,因为这个过程很有可能需要移动其他元素。

– 码出高效 Java 开发手册 P155