他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
点击阅读原文
源码阅读-ArrayList
1月2日 发布，来源：
以下源码基于 Android SDK 23， 与JDK中略有差别，但基本相同；整体源码由 构造、添加(add)、设置(set)、获取(get)、移除(remove)、迭代器(iterator) 和序列化(Serializable)组成，最后我还会把里边一些不常用的方法举例说明下作用，下面我们就一一探究其实现原理。
ArrayList 存储的实质是操作一个数组，这个数组可以根据内容自动扩容，所以让 ArrayList看起来像一个无限大小的容器一样。
* The minimum amount by which the capacity of an ArrayList will increase.
* This tuning parameter controls a time-space tradeoff. This value (12)
* gives empirically good results and is arguably consistent with the
* RI's specified default initial capacity of 10: instead of 10, we start
* with 0 (sans allocation) and jump to 12.
private static final int MIN_CAPACITY_INCREMENT = 12;
* The number of elements in this list.
* The elements in this list, followed by nulls.
transient Object[]
既然ArrayList可以自动扩容，那么就要有一个描述每次扩容的基准，MIN_CAPACITY_INCREMENT就是这个基准，默认值是12。
array 是 ArrayList的核心，所有数据均存储在array这个数组中，发生自动扩容时， array 会指向新的数组首地址，但注意了，transient
表示它不会参与序列化过程。
size 始终描述 ArrayList 中实际的大小。
* Constructs a new instance of {@code ArrayList} with the specified
* initial capacity.
* @param capacity
the initial capacity of this {@code ArrayList}.
public ArrayList(int capacity) {
if (capacity & 0) {
throw new IllegalArgumentException(&capacity & 0: & + capacity);
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
* Constructs a new {@code ArrayList} instance with zero initial capacity.
public ArrayList() {
array = EmptyArray.OBJECT;
* Constructs a new instance of {@code ArrayList} containing the elements of
* the specified collection.
* @param collection
the collection of elements to add.
public ArrayList(Collection&? extends E& collection) {
if (collection == null) {
throw new NullPointerException(&collection == null&);
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
ArrayList共含有3个构造方法，EmptyArray.OBJECT是一个length为0的空数组new Object[0]，new ArrayList() 则会创建一个大小为0的数组；你也可以去指定初始的容量capacity ，new ArrayList(int capacity) ，避免ArrayList 第一次add 或者其他操作就进行扩容；第三个构造可以传入一个集合，这里要提一下Collection，你可以认为它是 List 、Queue、Set的始祖，这里只要在它们内部实现了 toArray 方法，并且返回一个Object[]类型的数据，就可以成功初始化到 ArrayList中。
添加(add / addAll)
* Adds the specified object at the end of this {@code ArrayList}.
* @param object
the object to add.
* @return always true
@Override public boolean add(E object) {
Object[] a =
if (s == a.length) {
Object[] newArray = new Object[s +
(s & (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s && 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newA
size = s + 1;
modCount++;
* Inserts the specified object into this {@code ArrayList} at the specified
* location. The object is inserted before any previous element at the
* specified location. If the location is equal to the size of this
* {@code ArrayList}, the object is added at the end.
* @param index
the index at which to insert the object.
* @param object
the object to add.
* @throws IndexOutOfBoundsException
when {@code location & 0 || location & size()}
@Override public void add(int index, E object) {
Object[] a =
if (index & s || index & 0) {
throwIndexOutOfBoundsException(index, s);
if (s & a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
// assert s == a.
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newA
a[index] =
size = s + 1;
modCount++;
* This method controls the growth of ArrayList capacities.
It represents
* a time-space tradeoff: we don't want to grow lists too frequently
* (which wastes time and fragments storage), but we don't want to waste
* too much space in unused excess capacity.
* NOTE: This method is inlined into {@link #add(Object)} for performance.
* If you change the method, change it there too!
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity & (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity && 1);
return currentCapacity +
* Adds the objects in the specified collection to this {@code ArrayList}.
* @param collection
the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
otherwise.
@Override public boolean addAll(Collection&? extends E& collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.
if (newPartSize == 0) {
Object[] a =
int newSize = s + newPartS // If add overflows, arraycopy will fail
if (newSize & a.length) {
int newCapacity = newCapacity(newSize - 1);
// ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newA
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newS
modCount++;
* Inserts the objects in the specified collection at the specified location
* in this List. The objects are added in the order they are returned from
* the collection's iterator.
* @param index
the index at which to insert.
* @param collection
the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
otherwise.
* @throws IndexOutOfBoundsException
when {@code location & 0 || location & size()}
public boolean addAll(int index, Collection&? extends E& collection) {
if (index & s || index & 0) {
throwIndexOutOfBoundsException(index, s);
Object[] newPart = collection.toArray();
int newPartSize = newPart.
if (newPartSize == 0) {
Object[] a =
int newSize = s + newPartS // If add overflows, arraycopy will fail
if (newSize &= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
int newCapacity = newCapacity(newSize - 1);
// ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newA
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newS
modCount++;
这里有必要先看一个方法，System.arraycopy()
public static native void arraycopy(Object src, int srcPos,
Object dst, int dstPos, int length);
这是一个 native方法，负责数组拷贝，从 src 的
srcPos 开始，将 length长度的数据拷贝到 dst 中，dstPos中的数据是srcPos位置的数据。
public boolean add(E object)
这是最简单的一个add操作，里边会进行扩容判断，如果当前ArrayList.size与array.length相同，则进行扩容，扩容的策略是`s & (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s && 1`，即 s & 6 ? 6 : s * 2， 最终扩容的大小为
(s + s & 6 ? 6 : s * 2)；`newCapacity(int currentCapacity) ` 方法也是这个作用，返回最终扩容后的大小。
public void add(int index, E object)
这个方法的作用是将 object 插入至 index位置，这里也会有扩容判断，既然是插入一个值，那么size就会 +1，所以 ArrayList.size
小于 array.length是一种情况，数组可以直接从 index处 后移一位，再将 object 放入 index的位置；若是大于等于，则原array需要扩容，扩容后现将old array 数据 复制到 new array中，再进行后移，最终把object插入到index位置。
public boolean addAll(Collection&? extends E& collection)
public boolean addAll(int index, Collection&? extends E& collection)
这两个方法只是批量操作，内部逻辑与add 是一样的，都要先判断 ArrayList.size与array.length的大小关系进行扩容，之后通过 System.arraycopy去操作array。
注：这里你有可能会发现有个变量 modCount，它用来表达ArrayList的修改次数（add、remove），是它导致ArrayList不是线程安全的，等讲到迭代器iterator的时候再来说说这个变量。
* Replaces the element at the specified location in this {@code ArrayList}
* with the specified object.
* @param index
the index at which to put the specified object.
* @param object
the object to add.
* @return the previous element at the index.
* @throws IndexOutOfBoundsException
when {@code location & 0 || location &= size()}
@Override public E set(int index, E object) {
Object[] a =
if (index &= size) {
throwIndexOutOfBoundsException(index, size);
@SuppressWarnings(&unchecked&) E result = (E) a[index];
a[index] =
这个方法没什么，就是把array[index] 替换，并且把原来的数据返回。
@SuppressWarnings(&unchecked&)
public E get(int index) {
if (index &= size) {
throwIndexOutOfBoundsException(index, size);
return (E) array[index];
这个方法也不多说，将array[index]返回。
* Removes the object at the specified location from this list.
* @param index
the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException
when {@code location & 0 || location &= size()}
@Override public E remove(int index) {
Object[] a =
if (index &= s) {
throwIndexOutOfBoundsException(index, s);
@SuppressWarnings(&unchecked&) E result = (E) a[index];
System.arraycopy(a, index + 1, a, index, --s - index);
// Prevent memory leak
modCount++;
@Override public boolean remove(Object object) {
Object[] a =
if (object != null) {
for (int i = 0; i & i++) {
if (object.equals(a[i])) {
System.arraycopy(a, i + 1, a, i, --s - i);
// Prevent memory leak
modCount++;
for (int i = 0; i & i++) {
if (a[i] == null) {
System.arraycopy(a, i + 1, a, i, --s - i);
// Prevent memory leak
modCount++;
@Override protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex == toIndex) {
Object[] a =
if (fromIndex &= s) {
throw new IndexOutOfBoundsException(&fromIndex & + fromIndex
+ & &= size & + size);
if (toIndex & s) {
throw new IndexOutOfBoundsException(&toIndex & + toIndex
+ & & size & + size);
if (fromIndex & toIndex) {
throw new IndexOutOfBoundsException(&fromIndex & + fromIndex
+ & & toIndex & + toIndex);
System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromI
Arrays.fill(a, s - rangeSize, s, null);
size = s - rangeS
modCount++;
add方法已经进行了详细的讲解，想必大家都能猜到，remove操作就是讲 index 或者 range的一段数据从array中移除，然后再通过System.arraycopy拷贝之后的数据前移补充空位，下图以移除单个为例，将步骤分解：
@Override public Iterator&E& iterator() {
return new ArrayListIterator();
private class ArrayListIterator implements Iterator&E& {
/** Number of elements remaining in this iteration */
private int remaining =
/** Index of element that remove() would remove, or -1 if no such elt */
private int removalIndex = -1;
/** The expected modCount value */
private int expectedModCount = modC
public boolean hasNext() {
return remaining != 0;
@SuppressWarnings(&unchecked&) public E next() {
ArrayList&E& ourList = ArrayList.
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
if (rem == 0) {
throw new NoSuchElementException();
remaining = rem - 1;
return (E) ourList.array[removalIndex = ourList.size - rem];
public void remove() {
Object[] a =
int removalIdx = removalI
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
if (removalIdx & 0) {
throw new IllegalStateException();
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] =
// Prevent memory leak
removalIndex = -1;
expectedModCount = ++modC
迭代器，一个很重要的概念，它的作用就是便利整个ArrayList， for each 的原理其实就是迭代器的使用，上文说到了modCount与迭代器相关，
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
expectedModCount是iterator初始化时赋予的值，值为modCount，而modCount会根据add或者remove进行++操作，这就表明，当iterator创建好后，只要使用这个iterator实例去进行遍历，就不能使用ArrayList.add或者ArrayList.remove操作，因为如果使用了，modCount会发生变化，这样在next()的时候就会抛出异常ConcurrentModificationException ，这也进一步说明ArrayList不是线程安全的。那么在遍历中如何移除元素呢，就是下边实现的remove方法了，remove过程与之前类似，关键在于expectedModCount = ++modC，remove需要使modCount 递增，那么我让expectedModCount重新赋值，即可完成删除操作。
private static final long serialVersionUID = 2892189L;
private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeInt(array.length);
for (int i = 0; i & i++) {
stream.writeObject(array[i]);
private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
stream.defaultReadObject();
int cap = stream.readInt();
if (cap & size) {
throw new InvalidObjectException(
&Capacity: & + cap + & & size: & + size);
array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]);
for (int i = 0; i & i++) {
array[i] = stream.readObject();
这是在代码末尾了，ArrayList是通过stream.writeObject 连续写入 array的内容。
public boolean contains(Object object)
利用 object 的 equals方法判断ArrayList中是否包含object对象。
public int indexOf(Object object)
public int lastIndexOf(Object object)
这两个方法都是获取 object 在 ArrayList中的位置，第一个是正序遍历，找到的第一个返回的index；第二个是倒序遍历，找到第一个返回的index。
* Sets the capacity of this {@code ArrayList} to be the same as the current
* @see #size
public void trimToSize() {
if (s == array.length) {
if (s == 0) {
array = EmptyArray.OBJECT;
Object[] newArray = new Object[s];
System.arraycopy(array, 0, newArray, 0, s);
array = newA
modCount++;
这个方法是将当前的array “精简”一下，比如 array.length 是10，但里边的size是 5个，那么就将 array.length变为 5，把数据通过
System.arraycopy 拷贝到新的 array中。
@Override public boolean equals(Object o) {
if (o == this) {
if (!(o instanceof List)) {
List&?& that = (List&?&)
if (that.size() != s) {
Object[] a =
if (that instanceof RandomAccess) {
for (int i = 0; i & i++) {
Object eThis = a[i];
Object ethat = that.get(i);
if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
// Argument list
use its iterator
Iterator&?& it = that.iterator();
for (int i = 0; i & i++) {
Object eThis = a[i];
Object eThat = it.next();
if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
再来看下这个长长的equals方法，非常好懂，但是乍眼一看有个 RandomAccess ，这是什么？寻找了一下它的实现类，发现ArrayList就是它的实现类，再看下这个if(...){}else{}，如果是RandomAccess的实现类，那么直接使用get(index)获取元素，否则需要使用迭代器iterator。以下是对于RandomAccess的一段摘录：
jdk中有个RandomAccess接口，这是一个标记接口(Marker)，它没有任何方法，这个接口被List的实现类（子类）使用。如果List子类实现了RandomAccess接口，那就表示它能够快速随机访问存储的元素。RandomAccess接口的意义在于：在对列表进行随机或顺序访问的时候，访问算法能够选择性能最佳方式。一般的列表访问算法在访问列表元素之前，都被建议先使用instanceof关键字检查一下列表是否是一个RandomAccess子类，然后再决定采用随机还是顺序方式访问列表中的元素，这样可以保证访问算法拥有最佳的性能。对于List的子类，如果：
for (int i=0, n=list.size(); i & i++)
list.get(i);
的访问方式比for (Iterator i=list.iterator(); i.hasNext(); )
快，那么它应该实现RandomAccess接口。
我要该，理由是：
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）应用程序的main方法中有以下语句，则输出的结果是 ( )。-百谷歌百度拇指医生
&&&普通咨询
您的网络环境存在异常，
请输入验证码
验证码输入错误，请重新输入}