close

Mr.Muzi

一只很安静的monkey

Java Collection 03 - ArrayList

字数统计: 8.6k 阅读时长: 38 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 java.util.ArrayList<E> 的部分笔记，ArrayList是一个数组实现的可变长度的集合类。由于其实现了RandomAccess接口，所以可以通过随机访问的方式以常量时间获取到集合内的每个元素。本文演示代码段的执行环境基于JDK版本1.7。

概述

  ArrayList是一个可变长度的实现了List接口的、可以通过随机访问获取集合内元素的List集合实现。所有的操作和实现都建立在数组的基础之上，它实现了List接口声明的所有方法，且对要保存在ArrayList中的元素的类型没有任何限制，甚至可以存储null元素。ArrayList实现的size，isEmpty，get，set，iterator和listIterator的时间复杂度都是常量时间，add操作可以达到可摊还的常量时间（PS：在加入元素的过程中有可能出现因空间不足而需要执行扩容的操作），所以向集合内加入n个元素需要O(n)时间。除此之外的其他操作可以大致被视为线性时间复杂度。

  每个ArrayList在初始化时都会初始化其集合容量大小。在每次加入新元素到集合中时，容量值就会自动增加。

  ArrayList的实现思想类似于Vector，但是ArrayList是非线程安全的，而Vector则是线程安全的版本。如果需要在多线程环境中使用ArrayList，那么需要在使用ArrayList执行结构修改操作（结构修改包括加入或者删除一个/多个元素、显示修改底层数组的大小等）前完成多线程同步处理。一种推荐的处理方式是通过调用方法Collections.synchronizedList将ArrayList封装成一个用于多线程环境的集合实例。为了防止在未完成同步处理前就访问ArrayList，需要在初始化ArrayList就完成相关操作。具体可通过

1
List list = Collections.synchronizedList(new ArrayList(...));

完成初始化操作。还有一种思路是使用ArrayList的线程安全变本CopyOnWriteArrayList 。

  ArrayList实现的iterator和listIterator是包含快速失败属性的。意味着如果当前ArrayList不是被某个特定的迭代器自身作出了结构修改，那么会直接抛出ConcurrentModificationException异常。

 

继承关系

1
2
3
4
5
// ArrayList<E>
--java.lang.Object
  --java.util.AbstractCollection<E>
    --java.util.AbstractList<E>
      --java.util.ArrayList<E>

 

实现接口

类名 实现接口
ArrayList<E> Iterable<E>, Collection<E>, List<E>, RandomAccess, Serializable, Cloneable

 

ArrayList

Constructor Summary

public ArrayList(int initialCapacity)

1
2
3
4
5
6
7
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

  根据入参initialCapacity指定的长度初始化一个ArrayList空集合实例。

public ArrayList()

1
2
3
4
public ArrayList() {
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

  初始化一个ArrayList空集合实例，集合长度默认为0。

public ArrayList(Collection<? extends E> c)

1
2
3
4
5
6
7
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
}

  根据集合c初始化一个集合实例，并将c中的内容复制到实例化后的集合实例中。初始化的实例集合中元素的位置和c一致。

  size是ArrayList当前已经容纳的元素数，非ArrayList可以容纳的元素总数，ArrayList可以容纳的元素总数可以从elementData.length中得到。

部分方法

public void trimToSize()

1
2
3
4
5
6
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = Arrays.copyOf(elementData, size);
    }
}

  缩小ArrayList集合的容量。这是一个结构化操作，在操作之后会更新modCount的值以标记当前集合经历过结构化修改。方法调用后，list集合中的空闲位置全都会被释放回收掉，最后得到的集合会是一个装满元素、没有空闲空间的新集合实例。

public void ensureCapacity(int minCapacity)

1
2
3
4
5
6
7
8
9
10
11
12
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != EMPTY_ELEMENTDATA)
        // any size if real element table
        ? 0
        // larger than default for empty table. It's already supposed to be
        // at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

  检查当前集合是否有足够的空间容纳元素，且在空间不足的情况下执行扩容操作。这个方法被ArrayList内部没有调用，是一个暴露的方法API。在初始化ArrayList集合后，如果可以确定即将保存的元素数量，可以事先调用当前方法完成存储空间的分配，这样可以避免在加入元素的过程出现的空间再分配处理，从而提高了加入大量元素时的性能和效率。

  第2 ~ 7行代码计算了一个不需要执行扩容的下界，如果当前集合已经存储了元素，那么不论minCapacity为多少，都会扩容list集合的空间大小。如果当前list集合是个空集合，那么只有在minCapacity超过了list集合的默认大小后才会执行扩容处理，否则认为当前默认空间大小可以满足元素存储要求而不会执行扩容操作。具体的扩容操作直接调用ensureExplicitCapacity(int minCapacity)方法完成。

private void ensureCapacityInternal(int minCapacity)

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
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == 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);
}

   
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在加入元素时判断容量并执行扩容处理，方法被声明为私有方法，因此只会内部调用，不会对外暴露。第2 ~4行代码计算list实际需要的最小容量大小。之后调用ensureExplicitCapacity(int minCapacity)方法完成扩容操作。

  因为扩容操作属于结构化修改，所以第10行代码更新了modCount的值标记ArrayList集合的更新。如果实际计算得到的最小容量大小大于当前底层存储数据的大小，那么就调用grow(int minCapacity)完成真正的扩容处理。

  在执行扩容操作时，扩容标准是按照当前存储容量大小的 1.5 倍进行扩容（即第21行代码的计算过程）。如果1.5倍计算结果仍然小于minCapacity，那么直接按照minCapacity指定的大小进行扩容操纵。理论上扩容操作可以达到的最大容量为Integer.MAX_VALUE。MAX_ARRAY_SIZE的值为Integer.MAX_VALUE - 8，之所以这么做是因为一些特定的虚拟机会占用一些空间存储额外的信息，所以如果大于Integer.MAX_VALUE - 8的话可能会导致OutOfMemoryError的发生。

public int size()

1
2
3
4
5
6
7
public int size() {
    return size;
}

public boolean isEmpty() {
    return size == 0;
}

  返回当前ArrayList集合中存储的元素数量。如果当前集合中尚未存储任何元素（包括null），那么就返回true表示当前集合是个空集合。

public boolean contains(Object o)

1
2
3
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

  判断当前ArrayList集合中是否含有元素o。实际调用indexOf(Object o)完成判断。

public int indexOf(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

  返回元素o在当前ArrayList集合中第一次出现的位置，位置值从0开始计数。如果当前集合中没有存储一个及以上元素o，那么返回-1。

public int lastIndexOf(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

  返回元素o在当前ArrayList集合中最后一次出现的位置，位置值以0结束。如果当前集合中没有存储一个及以上元素o，那么返回-1。

public Object clone()

1
2
3
4
5
6
7
8
9
10
11
12
public Object clone() {
    try {
        @SuppressWarnings("unchecked")
        ArrayList<E> v = (ArrayList<E>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError();
    }
}

  克隆复制当前ArrayList集合自身并返回一份复制对象。执行的浅复制，通过Object类的native方法clone()完成具体的复制操作。

public Object[] toArray()

1
2
3
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

  将当前ArrayList集合的数据元素以数组形式全部返回。复制得到的结果和当前ArrayList集合的结果集分别操作时互不影响。

public <T> T[] toArray(T[] a)

1
2
3
4
5
6
7
8
9
10
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

  将当前ArrayList集合的数据元素以数组形式全部保存到数组a中。如果a的长度不足以容纳集合的所有元素，那么就新分配一个空间，存储集合中所有元素并返回。如果a的长度大于集合中存储的元素总数，那么a数组中最后一个元素的下一个存储位置会被置为null，如果集合中没有存储任何null元素，那么这个操作执行完成后便可以非常方便的得到集合中存储的元素总数。

E elementData(int index)

1
2
3
4
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

  返回下标index处的元素。

public E get(int index)

1
2
3
4
5
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

  返回ArrayList集合中index位置指定的数据元素。rangeCheck(int index)方法负责执行index是否到达集合尾部的边界检查。

public E set(int index, E element)

1
2
3
4
5
6
7
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

  将ArrayList集合中index位置指定的数据元素替换element，并返回替换之前index位置处的元素。

private void rangeCheck(int index)

1
2
3
4
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

  边界检查。检查下标索引值index是否越过了集合尾部。

public boolean add(E e)

1
2
3
4
5
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

  向ArrayList集合中加入数据元素e。首先通过ensureCapacityInternal(int minCapacity)完成扩容检查。之后在集合尾部保存元素e，同时更新维护size的值。最后返回true表示加入操作执行成功。由于该方法改变了集合的长度，所以会修改modCount的长度标识集合被执行了结构化修改。

public void add(int index, E element)

1
2
3
4
5
6
7
8
9
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集合中index指定的位置加入数据元素element。首先通过rangeCheckForAdd(int index)完成边界检查。接着通过ensureCapacityInternal(int minCapacity)完成扩容检查。由于该方法改变了集合的长度，所以会修改modCount的长度标识集合被执行了结构化修改。之后通过复制的方式将index位置及之后的元素向后移动释放index的存储空间，将element保存到index位置上。最后更新维护size的值。

private void rangeCheckForAdd(int index)

1
2
3
4
5
6
7
8
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

  对index执行边界检查。这个方法会同时检查index与首边界和尾边界的大小关系，如果大小关系异常则向上抛出越界异常。

public E remove(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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集合中index指定位置的元素，并返回被移除的元素。由于remove(int index)方法会修改ArrayList集合的数据容量，所以在方法执行过程中会修改modCount的值。由于index右侧的元素在方法执行过程中会统一向左移动，所以集合尾部最后一个位置的资源会被释放掉。

public boolean remove(Object o)

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
public boolean remove(Object 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 void fastRemove(int index) {
    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
}

  移除元素o。如果ArrayList集合中含有元素o，那么在移除完成后返回true表示确实执行过移除操作，否则返回false表示当前ArrayList集合中不存在元素o。该方法只能移除集合中存储位置最靠前的元素，如果想要移除集合中存储的所有o，那么需要循环调用当前方法以完成操作。

  remove方法的底层是通过调用fastRemove(int index)方法完成操作的。第20行代码计算当前index位置之后的元素数目，如果index不是指向最后一个位置的话，那么就将index位置之后的元素整体向前移动以覆盖index位置处存储的元素。由于fastRemove(int index)方法会导致size-1位置处的元素会左移一个空间位置，所以需要释放size-1位置处占用的资源。

public void clear()

1
2
3
4
5
6
7
8
9
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

  清空整个ArrayList集合中含有的元素。直接通过赋值为null的方式借助GC操作完成集合中元素占用资源的释放和回收。

public boolean addAll(Collection<? extends E> c)

1
2
3
4
5
6
7
8
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

  将集合c中的元素全部加入到当前ArrayList集合中。第2 ~ 3行代码获取c中的元素数据和元素个数。第4行代码完成扩容操作（如果需要的话）。之后则将c中含有的数据复制到当前的ArrayList集合中，同时更新集合的size信息。最后返回实际的操作结果，true表示确实执行了插入操作，false表示c为空集合，没有需要加入的元素。

public boolean addAll(int index, Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

  将集合c中的元素全部加入到当前ArrayList集合中自index起的位置上。第2行代码对index指定的范围做了边界校验。第4 ~ 5行代码获取c中的元素数据和元素个数。第5行代码完成扩容操作（如果需要的话）。

  相关校验和扩容操作处理完成后，如果index指定的位置不在ArrayList集合的尾部，则需要通过数组复制的方式释放自index位置起，长度为集合c中元素总数的空间以此来容纳集合c中的所有元素。之后则将c中含有的数据复制到当前的ArrayList集合中，同时更新集合的size信息。最后返回实际的操作结果，true表示确实执行了插入操作，false表示c为空集合，没有需要加入的元素。

protected void removeRange(int fromIndex, int toIndex)

1
2
3
4
5
6
7
8
9
10
11
12
13
protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

  移除ArrayList集合中自fromIndex位置起（包含fromIndex）到toIndex位置（不包括toIndex）的所有元素。由于removeRange(int fromIndex, int toIndex)属于结构化修改，所以操作过程中需要更新modCount的值。第3行代码需要计算出toIndex位置之后剩余的元素个数，第4 ~ 5行代码则将toIndex及之后的元素向左移动到了自fromIndex起始的位置上，这样就可以通过数据覆盖的方式将fromIndex和toIndex之间的元素清除掉。整个过程执行情况如图1所示：

图 - 1
 

  图1中toIndex及之后的元素会通过第4 ~ 5行代码的执行而移动到粉色区域。第8行代码的计算公式实际上可以拆分成

1
int newSize = size - toIndex + fromIndex;

即

1
int newSize = （size - toIndex）+ fromIndex;

  所以图1中红色花括号部分元素就是需要被释放空间的部分。也就是第9 ~ 11行代码执行的操作。操作流的最后会更新size的值。

public boolean removeAll(Collection<?> c)

1
2
3
public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false);
}

  移除ArrayList集合中含有的集合c中的元素。实际调用batchRemove(Collection<?> c, boolean complement)方法完成操作。

public boolean retainAll(Collection<?> c)

1
2
3
public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true);
    }

  保留同时存在于ArrayList集合和c集合中的元素，除此之外ArrayList集合中的其他元素都会被移除掉，该方法计算的实质等同于数学领域中的两个不同集合求交集运算。实际调用batchRemove(Collection<?> c, boolean complement)方法完成操作。

private boolean batchRemove(Collection<?> c, boolean complement)

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
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

  批量移除或保留同时存在于ArrayList集合和c中的元素。参数complement指明了操作类型，如果值为true，那么就保留同时存在于ArrayList集合和c中的元素，反之则执行删除操作。具体执行流程如图2所示：

图 - 2
 

  第5 ~ 8行代码执行的是图2中(1)的操作，当前ArrayList集合中的每个元素都会检查是否存在c中，如果complement的值为true，那么数组alpha中matched ele部分存储的是同时存在于ArrayList集合和c集合中的元素，而这些元素是需要保留下来的，中间的灰色区域的元素是已经比较过的元素，这部分元素存在于ArrayList集合但不存在c集合中，最后的unchecked elements的元素则是尚未比较的元素。如果complement的值为false，那么alpha中matched ele部分存储的则是存在于ArrayList集合中但是c集合中不含有的元素。

  如果在5 ~ 8行代码执行过程出现了异常，则会出现图2中(2)的场景。数组bravo中matched ele部分存储的是满足条件的元素，中间的灰色区域的元素是已经比较过的元素，最后的unchecked element的元素则是尚未比较的元素。第12 ~ 15行代码则将r位置及之后的元素左移到自w起始位置的空间中，同时更新w的值，即图2中(3)的场景。在数组chalie中，左侧matched ele部分和中间的粉色部分构成了需要保留的元素集合，而右侧的to be null部分则是需要移除的元素用来释放占用空间。

  如果第5 ~ 8行代码成功执行完毕，那么就会出现图2中(4)的场景。此时数组delta中左侧的matched ele部分存储的满足条件需要被保留下来的元素集合，右侧的to be null部分则是需要移除的元素。

  不管是场景(3)还是(4)，第18 ~ 25行代码都会将右侧的to be null部分的元素释放掉。同时更新modCount和size的值。

  如果w = size，那么则会出现图2中场景(5)的情况。此时集合c和ArrayList集合拥有数量一致且内容相同的元素，那么ArrayList集合则不会做出任何修改。

private void writeObject(java.io.ObjectOutputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

  

private void readObject(java.io.ObjectInputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

  

public ListIterator<E> listIterator(int index)

1
2
3
4
5
6
7
8
9
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

  返回一个可以从index位置开始遍历的迭代器。index指定了可以通过next()方法返回的第一个元素。该迭代器可以向前遍历，提供的previous()方法会返回index - 1位置的元素。如果未指定index，那么默认从0开始遍历。ListItr的相关实现如下：

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
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

  

public Iterator<E> iterator()

1
2
3
public Iterator<E> iterator() {
    return new Itr();
}

  返回一个基于整个ArrayList集合进行遍历的一个迭代器。Itr的相关代码实现如下：

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
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;

    public boolean hasNext() {
        return cursor != size;
    }

    @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];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

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

  

public List<E> subList(int fromIndex, int toIndex)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}

  返回ArrayList集合中自fromIndex起（包含fromIndex），到toIndex（不包含toIndex）之间的子集合。ArrayList中提供的方法均可适用于subList中。同ArrayList一样，subList也是通过随机访问的方式来获取元素的。SubList的相关实现如下：

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
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;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        parent.removeRange(parentOffset + fromIndex,
                           parentOffset + toIndex);
        this.modCount = parent.modCount;
        this.size -= toIndex - fromIndex;
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(this.size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;

        checkForComodification();
        parent.addAll(parentOffset + index, c);
        this.modCount = parent.modCount;
        this.size += cSize;
        return true;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);
        final int offset = this.offset;

        return new ListIterator<E>() {
            int cursor = index;
            int lastRet = -1;
            int expectedModCount = ArrayList.this.modCount;

            public boolean hasNext() {
                return cursor != SubList.this.size;
            }

            @SuppressWarnings("unchecked")
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= SubList.this.size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[offset + (lastRet = i)];
            }

            public boolean hasPrevious() {
                return cursor != 0;
            }

            @SuppressWarnings("unchecked")
            public E previous() {
                checkForComodification();
                int i = cursor - 1;
                if (i < 0)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (offset + i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i;
                return (E) elementData[offset + (lastRet = i)];
            }

            public int nextIndex() {
                return cursor;
            }

            public int previousIndex() {
                return cursor - 1;
            }

            public void remove() {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    SubList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            public void set(E e) {
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();

                try {
                    ArrayList.this.set(offset + lastRet, e);
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

            public void add(E e) {
                checkForComodification();

                try {
                    int i = cursor;
                    SubList.this.add(i, e);
                    cursor = i + 1;
                    lastRet = -1;
                    expectedModCount = ArrayList.this.modCount;
                } catch (IndexOutOfBoundsException ex) {
                    throw new ConcurrentModificationException();
                }
            }

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

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, offset, fromIndex, toIndex);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > this.size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+this.size;
    }

    private void checkForComodification() {
        if (ArrayList.this.modCount != this.modCount)
            throw new ConcurrentModificationException();
    }
}

  

 

涉及基础知识点

  1. ArrayList中Object[]elementData为什么被transient修饰，transient的意义是什么?

      由于ArrayList实现了java.io.Serializable接口，所以ArrayList中的所有属性和方法 都可以通过序列化进行存储和传输操作，elementData也不例外。而transient的作用是保证被修饰的属性不会被执行序列化操作。也就是说，被transient修饰的属性的生命周期仅存在于其父对象从初始化到被GC回收的这段时间内，不会随着父对象被序列化操作持久保存。

      那么，作为ArrayList中最重要的一个属性成员，为什么要阻止elementData被序列化呢？这是因为ArrayList没有对存储在内的元素限制其类型，换言之，一个ArrayList集合可以存储数量不限的null元素，如果将null元素也序列化的话，不仅没有意义，而且也会增加存储和传输的压力，所以为了避免这种情况，ArrayList重写了writeObject和readObject方法来专门对elementData执行序列化操作。所以，尽管elementData被修饰了transient，但还是可以随着ArrayList整体一起被序列化的，只是对序列化过程做了定制化处理而已。

      综上，关于transient的总结如下：

    1. transient只能修饰变量，不能修饰方法和类；
    2. 被transient修饰的变量不会被序列化，通过被反序列化得到的对象中无法访问被transient修饰的内容。transient 修饰的变量会被设为初始值，如 int 型的是 0，对象型的是 null 。

  2. toArray() T 和E的区别

      在进行类名声明时，ArrayList被声明为：public class ArrayList<E>，这意味着ArrayList内部的所有操作方法的对象类型都将会是E类型。但是我们希望可以通过toArray将ArrayList中的元素转换成更一般类型的元素，换言之，我们希望toArray()返回的元素类型会是E的父类型。所以如果将方法声明为E的话，这一点是无法做到的。

      此外，这个方法不会有关于类型方面的编译异常。我们刚提到了toArray方法的返回类型需要时E的父类型，但是在Java语言体系中，没有关于父子类型校验的语法规则。在Why Collection.toArray(T[]) doesn’t take an E[] instead问题的讨论中，提及了如下的声明：

    1
    public <T super E> T[] toArray(T[] a)

    但这种语法规则Java不支持，所以没有办法将异常通知提前到编译阶段。所以若toArray返回类型不是E的父类型，那么在运行期间会返回一个java.lang.ArrayStoreException异常。可参考如下demo：

    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
    class TestObj {
    	private Long id;
    	private String name;

    	public TestObj(Long id, String name) {
    		super();
    		this.id = id;
    		this.name = name;
    	}

    	@Override
    	public String toString() {
    		return "TestObj [id=" + id + ", name=" + name + "]";
    	}
    	
    }

    class TestObj1 extends TestObj{
    	public TestObj1(Long id, String name) {
    		super(id, name);
    	}

    	private Long id1;

    	public Long getId1() {
    		return id1;
    	}

    	public void setId1(Long id1) {
    		this.id1 = id1;
    	}
    }

    List<TestObj> list = new ArrayList<>();
    list.add(testObj);
    list.add(testObj2);

    TestObj[] obj2 = new TestObj[list.size()];
    list.toArray(obj2);

    TestObj1[] objs = new TestObj1[list.size()];
    list.toArray(objs);

      在运行过程中，第39行代码可以正常运行，而第41行代码会抛出ArrayStoreException异常。

  3. 关于public ArrayList(Collection<? extends E> c) 中S“see 6260652”的延伸

      这是一个JDK的bug问题，详情可浏览(coll) Arrays.asList(x).toArray().getClass() should be Object[].class。问题的大概描述是 collection.toArray()返回的结果的类型应该是java.lang.Object，但是在Arrays.asList中，实际上返回的并不是java.lang.Object，而是java.util.Arrays$ArrayList。所以如果传入的是Arrays.asList得到的c集合，那么其类型并不是java.lang.Object。所在在ArrayList(Collection<? extends E> c)中加入了类型的判断，如果c的类型不是java.lang.Object，那么就以java.lang.Object为基础重新构建一个elementData数组。这个问题已经在JDK9中得到了修复。

  4. modCount的存在意义

      modCount从字面意义上理解为修改次数。因为ArrayList是一个非线程安全的数据结构。除此之外，Arraylist中的listIterator(int index)、listIterator()、iterator()方法如果重复调用的话会生成多个迭代器，而每个迭代器都可以对ArrayList进行元素增删操作。所以modCount可以用来判断ArrayList的最近一次元素增删操作是否是由自身（ArrayList实例或者迭代器）执行的。如果不是由自身完成的，那么就会抛出异常。

      通过迭代器的next、remove、previous方法遍历集合元素时，首先会检查自身维护的expectedModCount和ArrayList中的modCount值是否一致。如果一致，那么认为ArrayList最近的一次结构化修改是否自身完成的，可以继续执行后续操作。

  5. 为什么选择1.5倍进行扩容

      在ArrayList的扩容机制里，ArrayList是按照当前容量的1.5倍进行扩容的。扩容大小的选择决定了实际应用中性能的好坏：如果单次扩容太大，会导致更明显的内存空间浪费，相反，如果扩容幅度变小，那么需要更多的次数来执行扩容，这会导致重新分配内存空间的操作变得更加频繁，从而导致性能受到影响。

      鉴于此，Java设计人员需要在保证集合空间满足实际需求的情况下同时尽可能的减少内存重分配的次数。至于为什么最后决定采用1.5倍扩容，可能他们经过各种分析论证和性能测试之后认为1.5倍是最能满足要求的结果了。根据找到的一些资料表明如果扩容倍数在1.5倍时，内存浪费最多为33%，而2.5 被最多会浪费 60%，3.5 倍则会浪费 71…所以，1.5倍可能是最合适的结果。

  6. ArrayList实现writeObject和readObject的意义

      在(1)中提到了被transient关键字修饰的elementData是无法被序列化的，所以ArrayList自己实现了writeObject和readObject方法用来对elementData执行序列化和反序列操作。那么在执行序列化的过程中就会使用ArrayList自己实现的writeObject和readObject方法来完成序列化和反序列操作的。ArrayList通过writeObject把elementData里的元素写入到输出流ObjectOutputStream )中，通过readObject从输入流（ObjectInputStream ）读取到被序列化的数据并反序列化之后存储到elementData。

      但是，writeObject和readObject方法都被声明为私有方法，且在ArrayList内部没有任何地方调用了该方法。实际上，这两个方法是通过反射的方式出现在了ObjectOutputStream和ObjectInputStream的方法writeObject()和readObject()调用栈中。

  7. length、length()和size()的区别

      length属性常出现在数组中，表示给一个数组分配的空间大小；length()常出现在字符串中，表示一个字符串的长度，某些情况下空格也会被计算在内；size()常出现在集合中，表示集合中存储的元素个数。

 

参考文献

  1. James Gosling等. The Java Language Specification 7th Edtion[M]. Boston:Addison-Wesley.
  2. Oracle Java Bug Database. (coll) Arrays.asList(x).toArray().getClass() should be Object[].class [E]
  3. Stack Overflow. Why does Java have transient fields? [E]
  4. 程序媛想事儿(Alexia). Java transient关键字使用小记 [E]
  5. Stack Overflow. [Logic used in ensureCapacity method in ArrayList [E]
  6. chenssy. ArrayList [E]
  7. Aleksey Shipilëv. Arrays of Wisdom of the Ancients [E]
  8. 小米干饭. 为什么 Java ArrayList.toArray(T[]) 方法的参数类型是 T 而不是 E ? [E]
  9. Stack Overflow. Why Collection.toArray(T[]) doesn’t take an E[] instead [E]
  10. Stack Overflow. Java List T[] toArray(T[] a) implementation [E]
  11. Stack Overflow. Why for toArray hides of Collection? [E]
  12. 像一只狗. 搞懂 Java ArrayList 源码 [E]
  13. 魏福成. modCount到底是干什么的呢 [E]
  14. Hollis. 深入分析Java的序列化与反序列化 [E]

 
 
 
 

------------- End of this article, thanks! -------------
 


  版权声明：本文由N.C.Lee创作和发表，采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可，转载请注明作者及出处。
  本文作者为 N.C.Lee
  本文标题为 Java Collection 03 - ArrayList
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-ArrayList.html