ArrayList源码解读（jdk1.8）

概要

上一章，我们学习了Collection的架构。这一章开始，我们对Collection的具体实现类进行讲解；首先，讲解List，而List中ArrayList又最为常用。因此，本章我们讲解ArrayList。先对ArrayList有个整体认识，再学习它的源码，最后再通过例子来学习如何使用它。内容包括：
第1部分 ArrayList简介
第2部分 ArrayList数据结构
第3部分 ArrayList源码解析(基于JDK1.8)
第4部分 ArrayList遍历方式

第1部分 ArrayList介绍

ArrayList简介

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList _实现了RandmoAccess接口，即提供了随机访问功能。_RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。

ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

ArrayList构造函数

1/**
2     * 当指明初始化数组的大小时，直接将数组初始化为指定容量的数组。
3     */
4    public ArrayList(int initialCapacity) {
5        if (initialCapacity > 0) {
6            this.elementData = new Object[initialCapacity];
7        } else if (initialCapacity == 0) {
8            this.elementData = EMPTY_ELEMENTDATA;
9        } else {
10            throw new IllegalArgumentException("Illegal Capacity: "+
11                    initialCapacity);
12        }
13    }
14
15    /**
16     * 当没有指明数组容量时，初始化为空数组。当第一次添加元素时，会扩容为DEFAULT_CAPACITY，也就是容量为10.
17     */
18    public ArrayList() {
19        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
20    }

第2部分 ArrayList数据结构

ArrayList的继承关系

1java.lang.Object
2   ↳     java.util.AbstractCollection<E>
3         ↳     java.util.AbstractList<E>
4               ↳     java.util.ArrayList<E>
5
6public class ArrayList<E> extends AbstractList<E>
7        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

ArrayList与Collection关系如下图：

ArrayList包含了两个重要的对象：elementData 和 size。

(01) elementData 是"Object[]类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建ArrayList，则elementData会初始化为空数组（上面构造函数源码），当第一次添加元素时，会扩容至默认容量10。

(02) size 则是动态数组的实际大小。

第3部分 ArrayList源码解析(基于JDK1.8)

为了更了解ArrayList的原理，下面对ArrayList源码代码作出分析。ArrayList是通过数组实现的，源码比较容易理解。 

1public class ArrayList<E> extends AbstractList<E>
2        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
3{
4    private static final long serialVersionUID = 8683452581122892189L;
5
6    /**
7     * Default initial capacity.
8     */
9    private static final int DEFAULT_CAPACITY = 10;
10
11    /**
12     * Shared empty array instance used for empty instances.
13     */
14    private static final Object[] EMPTY_ELEMENTDATA = {};
15
16    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
17
18    /**
19     * 数组用来存储元素。当new ArrayList时没有指明大小，那么就会使用默认的空数组。
20     * 当第一次add元素的时候，会将数组容量设为默认值DEFAULT_CAPACITY 10.
21     */
22    transient Object[] elementData; // non-private to simplify nested class access
23
24    /**
25     * 数组所包含的元素个数，注意和elementData.length区别开。
26     *size<=length
27     * @serial
28     */
29    private int size;
30
31    /**
32     * 当指明初始化数组的大小时，直接将数组初始化为指定容量的数组。
33     */
34    public ArrayList(int initialCapacity) {
35        if (initialCapacity > 0) {
36            this.elementData = new Object[initialCapacity];
37        } else if (initialCapacity == 0) {
38            this.elementData = EMPTY_ELEMENTDATA;
39        } else {
40            throw new IllegalArgumentException("Illegal Capacity: "+
41                    initialCapacity);
42        }
43    }
44
45    /**
46     * 当没有指明数组容量时，初始化为空数组。当第一次添加元素时，会扩容为DEFAULT_CAPACITY，也就是容量为10.
47     */
48    public ArrayList() {
49        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
50    }
51
52
53    public ArrayList(Collection<? extends E> c) {
54        elementData = c.toArray();
55        if ((size = elementData.length) != 0) {
56            // c.toArray might (incorrectly) not return Object[] (see 6260652)
57            if (elementData.getClass() != Object[].class)
58                elementData = Arrays.copyOf(elementData, size, Object[].class);
59        } else {
60            // replace with empty array.
61            this.elementData = EMPTY_ELEMENTDATA;
62        }
63    }
64
65    /**
66     * 将当前数组截成size大小的数组，也就是有元素部分留下，剩下的长度不要了。
67     */
68    public void trimToSize() {
69        modCount++;
70        if (size < elementData.length) {
71            elementData = (size == 0)
72                    ? EMPTY_ELEMENTDATA
73                    : Arrays.copyOf(elementData, size);
74        }
75    }
76
77    /**
78     * 调整容量。首先判断，如果有必要，则将容量扩大至至少能放下minCapacity个元素。
79     */
80    public void ensureCapacity(int minCapacity) {
81        /**
82         * 这里主要确保：如果数组为空，则至少需要扩容到DEFAULT_CAPACITY。
83         * 如果不为空，扩大至至少能放下minCapacity个元素。
84         */
85        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
86                ? 0
87                : DEFAULT_CAPACITY;
88
89        if (minCapacity > minExpand) {
90            ensureExplicitCapacity(minCapacity);
91        }
92    }
93
94    private void ensureCapacityInternal(int minCapacity) {
95        /**
96         * 如果数组为空，则要扩大至Math.max(DEFAULT_CAPACITY, minCapacity)
97         */
98        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
99            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
100        }
101
102        ensureExplicitCapacity(minCapacity);
103    }
104
105    private void ensureExplicitCapacity(int minCapacity) {
106        modCount++;
107
108        // 当前要求的个数比当前数组的length要大，则扩容。
109        if (minCapacity - elementData.length > 0)
110            grow(minCapacity);
111    }
112
113    /**
114     * The maximum size of array to allocate.
115     * Some VMs reserve some header words in an array.
116     * Attempts to allocate larger arrays may result in
117     * OutOfMemoryError: Requested array size exceeds VM limit
118     */
119    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
120
121    /**
122     * 扩容，保证最少可以存放minCapacity个元素。基本原则是扩容至数组长度的1.5倍
123     */
124    private void grow(int minCapacity) {
125        // overflow-conscious code
126        //当前数组长度（容量）
127        int oldCapacity = elementData.length;
128        //新容量是当前数组容量的1.5倍。
129        int newCapacity = oldCapacity + (oldCapacity >> 1);
130        //如果1.5倍的新容量都比minCapacity小，那么新容量就为minCapacity
131        if (newCapacity - minCapacity < 0)
132            newCapacity = minCapacity;
133        /**
134         * 新容量比最大数组容量还要大的时候，就要重新赋值新容量了。不能超过最大值。
135         */
136        if (newCapacity - MAX_ARRAY_SIZE > 0)
137            newCapacity = hugeCapacity(minCapacity);
138        // minCapacity is usually close to size, so this is a win:
139        elementData = Arrays.copyOf(elementData, newCapacity);
140    }
141
142    private static int hugeCapacity(int minCapacity) {
143        if (minCapacity < 0) // overflow
144            throw new OutOfMemoryError();
145        return (minCapacity > MAX_ARRAY_SIZE) ?
146                Integer.MAX_VALUE :
147                MAX_ARRAY_SIZE;
148    }
149
150
151    public int size() {
152        return size;
153    }
154
155
156    public boolean isEmpty() {
157        return size == 0;
158    }
159
160
161    public boolean contains(Object o) {
162        return indexOf(o) >= 0;
163    }
164
165    /**
166     * 找出元素的位置，可以看出ArrayList可以存放null
167     */
168    public int indexOf(Object o) {
169        if (o == null) {
170            for (int i = 0; i < size; i++)
171                if (elementData[i]==null)
172                    return i;
173        } else {
174            for (int i = 0; i < size; i++)
175                if (o.equals(elementData[i]))
176                    return i;
177        }
178        return -1;
179    }
180
181
182    public int lastIndexOf(Object o) {
183        if (o == null) {
184            for (int i = size-1; i >= 0; i--)
185                if (elementData[i]==null)
186                    return i;
187        } else {
188            for (int i = size-1; i >= 0; i--)
189                if (o.equals(elementData[i]))
190                    return i;
191        }
192        return -1;
193    }
194
195    /**
196     * 克隆的时候，数组得单独克隆
197     */
198    public Object clone() {
199        try {
200            ArrayList<?> v = (ArrayList<?>) super.clone();
201            v.elementData = Arrays.copyOf(elementData, size);
202            v.modCount = 0;
203            return v;
204        } catch (CloneNotSupportedException e) {
205            // this shouldn't happen, since we are Cloneable
206            throw new InternalError(e);
207        }
208    }
209
210
211    public Object[] toArray() {
212        return Arrays.copyOf(elementData, size);
213    }
214
215
216    @SuppressWarnings("unchecked")
217    public <T> T[] toArray(T[] a) {
218        if (a.length < size)
219            // Make a new array of a's runtime type, but my contents:
220            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
221        System.arraycopy(elementData, 0, a, 0, size);
222        if (a.length > size)
223            a[size] = null;
224        return a;
225    }
226
227    // Positional Access Operations
228
229    @SuppressWarnings("unchecked")
230    E elementData(int index) {
231        return (E) elementData[index];
232    }
233
234    /**
235     * 按索引得到元素只要判断索引没有越界，就直接返回数组对应元素
236     */
237    public E get(int index) {
238        rangeCheck(index);
239
240        return elementData(index);
241    }
242
243    /**
244     * 将指定位置的元素换成新元素
245     */
246    public E set(int index, E element) {
247        rangeCheck(index);
248
249        E oldValue = elementData(index);
250        elementData[index] = element;
251        return oldValue;
252    }
253
254    /**
255     * 添加元素，如果是第一次添加，就会扩容到DEFAULT_CAPACITY大小；
256     * 不是第一次添加也会判断是否需要扩容，基本规则是扩容到当前数组容量的1.5倍。
257     * modCount会增加
258     */
259    public boolean add(E e) {
260        ensureCapacityInternal(size + 1);  // Increments modCount!!
261        elementData[size++] = e;
262        return true;
263    }
264
265    /**
266     *每次添加都要判断是否需要扩容
267     * 先将index后的元素后移一个，再插入
268     * modCount++
269     */
270    public void add(int index, E element) {
271        rangeCheckForAdd(index);
272
273        ensureCapacityInternal(size + 1);  // Increments modCount!!
274        System.arraycopy(elementData, index, elementData, index + 1,
275                size - index);
276        elementData[index] = element;
277        size++;
278    }
279
280    /**
281     * 删除元素，modCount++
282     * 将index后的元素往前移，并将最后一个元素置为Null
283     */
284    public E remove(int index) {
285        rangeCheck(index);
286
287        modCount++;
288        E oldValue = elementData(index);
289
290        int numMoved = size - index - 1;
291        if (numMoved > 0)
292            System.arraycopy(elementData, index+1, elementData, index,
293                    numMoved);
294        elementData[--size] = null; // clear to let GC do its work
295
296        return oldValue;
297    }
298
299    /**
300     * 删除指定的元素。该元素可以为null。
301     */
302    public boolean remove(Object o) {
303        if (o == null) {
304            for (int index = 0; index < size; index++)
305                if (elementData[index] == null) {
306                    fastRemove(index);
307                    return true;
308                }
309        } else {
310            for (int index = 0; index < size; index++)
311                if (o.equals(elementData[index])) {
312                    fastRemove(index);
313                    return true;
314                }
315        }
316        return false;
317    }
318
319    /*
320     * Private remove method that skips bounds checking and does not
321     * return the value removed.
322     */
323    private void fastRemove(int index) {
324        modCount++;
325        int numMoved = size - index - 1;
326        if (numMoved > 0)
327            System.arraycopy(elementData, index+1, elementData, index,
328                    numMoved);
329        elementData[--size] = null; // clear to let GC do its work
330    }
331
332    /**
333     * 将所有元素置为Null
334     */
335    public void clear() {
336        modCount++;
337
338        // clear to let GC do its work
339        for (int i = 0; i < size; i++)
340            elementData[i] = null;
341
342        size = 0;
343    }
344
345    /**
346     * Appends all of the elements in the specified collection to the end of
347     * this list, in the order that they are returned by the
348     * specified collection's Iterator.  The behavior of this operation is
349     * undefined if the specified collection is modified while the operation
350     * is in progress.  (This implies that the behavior of this call is
351     * undefined if the specified collection is this list, and this
352     * list is nonempty.)
353     *
354     * @param c collection containing elements to be added to this list
355     * @return <tt>true</tt> if this list changed as a result of the call
356     * @throws NullPointerException if the specified collection is null
357     */
358    public boolean addAll(Collection<? extends E> c) {
359        Object[] a = c.toArray();
360        int numNew = a.length;
361        ensureCapacityInternal(size + numNew);  // Increments modCount
362        System.arraycopy(a, 0, elementData, size, numNew);
363        size += numNew;
364        return numNew != 0;
365    }
366
367    /**
368     * Inserts all of the elements in the specified collection into this
369     * list, starting at the specified position.  Shifts the element
370     * currently at that position (if any) and any subsequent elements to
371     * the right (increases their indices).  The new elements will appear
372     * in the list in the order that they are returned by the
373     * specified collection's iterator.
374     *
375     * @param index index at which to insert the first element from the
376     *              specified collection
377     * @param c collection containing elements to be added to this list
378     * @return <tt>true</tt> if this list changed as a result of the call
379     * @throws IndexOutOfBoundsException {@inheritDoc}
380     * @throws NullPointerException if the specified collection is null
381     */
382    public boolean addAll(int index, Collection<? extends E> c) {
383        rangeCheckForAdd(index);
384
385        Object[] a = c.toArray();
386        int numNew = a.length;
387        ensureCapacityInternal(size + numNew);  // Increments modCount
388
389        int numMoved = size - index;
390        if (numMoved > 0)
391            System.arraycopy(elementData, index, elementData, index + numNew,
392                    numMoved);
393
394        System.arraycopy(a, 0, elementData, index, numNew);
395        size += numNew;
396        return numNew != 0;
397    }
398
399    /**
400     * Removes from this list all of the elements whose index is between
401     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
402     * Shifts any succeeding elements to the left (reduces their index).
403     * This call shortens the list by {@code (toIndex - fromIndex)} elements.
404     * (If {@code toIndex==fromIndex}, this operation has no effect.)
405     *
406     * @throws IndexOutOfBoundsException if {@code fromIndex} or
407     *         {@code toIndex} is out of range
408     *         ({@code fromIndex < 0 ||
409     *          fromIndex >= size() ||
410     *          toIndex > size() ||
411     *          toIndex < fromIndex})
412     */
413    protected void removeRange(int fromIndex, int toIndex) {
414        modCount++;
415        int numMoved = size - toIndex;
416        System.arraycopy(elementData, toIndex, elementData, fromIndex,
417                numMoved);
418
419        // clear to let GC do its work
420        int newSize = size - (toIndex-fromIndex);
421        for (int i = newSize; i < size; i++) {
422            elementData[i] = null;
423        }
424        size = newSize;
425    }
426
427    /**
428     * Checks if the given index is in range.  If not, throws an appropriate
429     * runtime exception.  This method does *not* check if the index is
430     * negative: It is always used immediately prior to an array access,
431     * which throws an ArrayIndexOutOfBoundsException if index is negative.
432     */
433    private void rangeCheck(int index) {
434        if (index >= size)
435            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
436    }
437
438    /**
439     * A version of rangeCheck used by add and addAll.
440     */
441    private void rangeCheckForAdd(int index) {
442        if (index > size || index < 0)
443            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
444    }
445
446    /**
447     * Constructs an IndexOutOfBoundsException detail message.
448     * Of the many possible refactorings of the error handling code,
449     * this "outlining" performs best with both server and client VMs.
450     */
451    private String outOfBoundsMsg(int index) {
452        return "Index: "+index+", Size: "+size;
453    }
454
455    /**
456     * Removes from this list all of its elements that are contained in the
457     * specified collection.
458     *
459     * @param c collection containing elements to be removed from this list
460     * @return {@code true} if this list changed as a result of the call
461     * @throws ClassCastException if the class of an element of this list
462     *         is incompatible with the specified collection
463     * (<a href="Collection.html#optional-restrictions">optional</a>)
464     * @throws NullPointerException if this list contains a null element and the
465     *         specified collection does not permit null elements
466     * (<a href="Collection.html#optional-restrictions">optional</a>),
467     *         or if the specified collection is null
468     * @see Collection#contains(Object)
469     */
470    public boolean removeAll(Collection<?> c) {
471        Objects.requireNonNull(c);
472        return batchRemove(c, false);
473    }
474
475    /**
476     * Retains only the elements in this list that are contained in the
477     * specified collection.  In other words, removes from this list all
478     * of its elements that are not contained in the specified collection.
479     *
480     * @param c collection containing elements to be retained in this list
481     * @return {@code true} if this list changed as a result of the call
482     * @throws ClassCastException if the class of an element of this list
483     *         is incompatible with the specified collection
484     * (<a href="Collection.html#optional-restrictions">optional</a>)
485     * @throws NullPointerException if this list contains a null element and the
486     *         specified collection does not permit null elements
487     * (<a href="Collection.html#optional-restrictions">optional</a>),
488     *         or if the specified collection is null
489     * @see Collection#contains(Object)
490     */
491    public boolean retainAll(Collection<?> c) {
492        Objects.requireNonNull(c);
493        return batchRemove(c, true);
494    }
495
496    private boolean batchRemove(Collection<?> c, boolean complement) {
497        final Object[] elementData = this.elementData;
498        int r = 0, w = 0;
499        boolean modified = false;
500        try {
501            for (; r < size; r++)
502                if (c.contains(elementData[r]) == complement)
503                    elementData[w++] = elementData[r];
504        } finally {
505            // Preserve behavioral compatibility with AbstractCollection,
506            // even if c.contains() throws.
507            if (r != size) {
508                System.arraycopy(elementData, r,
509                        elementData, w,
510                        size - r);
511                w += size - r;
512            }
513            if (w != size) {
514                // clear to let GC do its work
515                for (int i = w; i < size; i++)
516                    elementData[i] = null;
517                modCount += size - w;
518                size = w;
519                modified = true;
520            }
521        }
522        return modified;
523    }
524
525    /**
526     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
527     * is, serialize it).
528     *
529     * @serialData The length of the array backing the <tt>ArrayList</tt>
530     *             instance is emitted (int), followed by all of its elements
531     *             (each an <tt>Object</tt>) in the proper order.
532     */
533    private void writeObject(java.io.ObjectOutputStream s)
534            throws java.io.IOException{
535        // Write out element count, and any hidden stuff
536        int expectedModCount = modCount;
537        s.defaultWriteObject();
538
539        // Write out size as capacity for behavioural compatibility with clone()
540        s.writeInt(size);
541
542        // Write out all elements in the proper order.
543        for (int i=0; i<size; i++) {
544            s.writeObject(elementData[i]);
545        }
546
547        if (modCount != expectedModCount) {
548            throw new ConcurrentModificationException();
549        }
550    }
551
552    /**
553     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
554     * deserialize it).
555     */
556    private void readObject(java.io.ObjectInputStream s)
557            throws java.io.IOException, ClassNotFoundException {
558        elementData = EMPTY_ELEMENTDATA;
559
560        // Read in size, and any hidden stuff
561        s.defaultReadObject();
562
563        // Read in capacity
564        s.readInt(); // ignored
565
566        if (size > 0) {
567            // be like clone(), allocate array based upon size not capacity
568            ensureCapacityInternal(size);
569
570            Object[] a = elementData;
571            // Read in all elements in the proper order.
572            for (int i=0; i<size; i++) {
573                a[i] = s.readObject();
574            }
575        }
576    }
577
578    /**
579     * Returns a list iterator over the elements in this list (in proper
580     * sequence), starting at the specified position in the list.
581     * The specified index indicates the first element that would be
582     * returned by an initial call to {@link ListIterator#next next}.
583     * An initial call to {@link ListIterator#previous previous} would
584     * return the element with the specified index minus one.
585     *
586     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
587     *
588     * @throws IndexOutOfBoundsException {@inheritDoc}
589     */
590    public ListIterator<E> listIterator(int index) {
591        if (index < 0 || index > size)
592            throw new IndexOutOfBoundsException("Index: "+index);
593        return new ListItr(index);
594    }
595
596    /**
597     * Returns a list iterator over the elements in this list (in proper
598     * sequence).
599     *
600     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
601     *
602     * @see #listIterator(int)
603     */
604    public ListIterator<E> listIterator() {
605        return new ListItr(0);
606    }
607
608    /**
609     * Returns an iterator over the elements in this list in proper sequence.
610     *
611     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
612     *
613     * @return an iterator over the elements in this list in proper sequence
614     */
615    public Iterator<E> iterator() {
616        return new Itr();
617    }
618
619    /**
620     * 迭代器中有expectedModCount
621     */
622    private class Itr implements Iterator<E> {
623        int cursor;       // 下一个返回元素的下标，默认是0
624        int lastRet = -1; // 上一个返回元素的下标。-1表示还没有返回
625        int expectedModCount = modCount;
626
627        public boolean hasNext() {
628            return cursor != size;
629        }
630
631        @SuppressWarnings("unchecked")
632        public E next() {
633            /**
634             * 检查expectedModCount与modCount是否相等，不相等表示已经被修改过，抛出异常
635             */
636            checkForComodification();
637            int i = cursor;
638            if (i >= size)
639                throw new NoSuchElementException();
640            Object[] elementData = ArrayList.this.elementData;
641            if (i >= elementData.length)
642                throw new ConcurrentModificationException();
643            cursor = i + 1;
644            return (E) elementData[lastRet = i];
645        }

View Code

总结：
(01) ArrayList 实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，会先分配一个空数组，当第一次添加时，则扩容为默认容量大小10。
(02) 当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：newCapacity = oldCapacity + (oldCapacity >> 1)。也就是为原数组容量的1.5倍。（如果超过最大容量，就设为最大容量）

(03) ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
(04) ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

 (05)源码中有个modCount变量，每做一次修改，都会增加一个。在迭代器中有expectedModCount变量，变量时会判断这两个变量是否相同。如果不相同，表示在遍历过程中，数组被修改过，抛出异常。fail-fast

第4部分 ArrayList遍历方式

ArrayList支持3种遍历方式

(01) 第一种，通过迭代器遍历。即通过Iterator去遍历。

1Integer value = null;
2Iterator iter = list.iterator();
3while (iter.hasNext()) {
4    value = (Integer)iter.next();
5}

(02) 第二种，随机访问，通过索引值去遍历。
由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。

1Integer value = null;
2int size = list.size();
3for (int i=0; i<size; i++) {
4    value = (Integer)list.get(i);        
5}

(03) 第三种，for循环遍历。如下：

1Integer value = null;
2for (Integer integ:list) {
3    value = integ;
4}

下面通过一个实例，比较这3种方式的效率，实例代码(ArrayListRandomAccessTest.java)如下：

  View Code

运行结果：

iteratorThroughRandomAccess：3 ms
iteratorThroughIterator：8 ms
iteratorThroughFor2：5 ms

由此可见，遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！

参考：http://www.cnblogs.com/skywang12345/p/3308556.html，这篇文章是1.6，本文1.8