看完了顶层接口,和实现了基本骨架的 AbstractList,下一步就来看真正的实现类,也是我们平时用的最多的集合类之一的动态数组列表 —— ArrayList

类注释

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List 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 Vector, except that it is unsynchronized.)

ArrayList 是一个可变大小List 接口实现。ArrayList 实现了所有 List 接口定义的操作,并且允许 null 元素的存在。除了实现 List 接口之外, ArrayList 还提供了操作内部存储列表数组大小的方法。【 ArrayList 的底层数据结构是 数组】

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized(平摊) constant time, 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 LinkedList implementation.
Each ArrayList instance has a capacity. 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.

szieisEmptygetsetiteratorlistIterator 操作都是常量级的时间复杂度,添加元素的 add 方法则是 O(n) 的时间复杂度【也就是随着数据规模的增大,方法耗时也会增加】。

所有其他操作是线性时间复杂度【意思是比 O(n) 还要再高一些】

LinkedList 相比, ArrayList常数因子(constant factor) 较低。【意思是耗时比 LinkedList 要低吗?】

每个 ArrayList 都存在容量(capacity) 这一状态。容量指的是 ArrayList 中用来真正保存数据的底层数组的大小。一般来说,容量至少等于数组的实际大小。将元素添加到 List 中后,容量会自动增长。除了添加元素的固定开销之外,并没有扩容的具体策略开销。

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

应用程序可以在向 ArrayList 中添加大量元素之前指定 ArrayList 实例的容量,这可以减少多次扩容所带来的开销。【也就是构造容器时直接先指定一个大的容量】

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must 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. If no such object exists, the list should be "wrapped" using the

Collections.synchronizedList method. This is best done at creation time, to prevent accidental(意外地) unsynchronized access to the list:
List list = Collections.synchronizedList(new ArrayList(...));
④The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a 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.
⑤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 ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
This class is a member of the Java Collections Framework.

①: ArrayList 是非线程安全的 List 实现。 如果多个线程同时访问 ArrayList 实例,并且至少有一个线程可能会对数据进行修改,那么就必须使用额外的同步策略。

②: 这里的修改 List 结构指的是:添加/删除一个或多个元素,或修改 backing list 的数组大小,仅修改 List 中存储的元素的状态并不是修改 List 的结构。【也就是与保存的对象本身的状态无关,而是不能修改 List 的状态】

③: 通常在封装 List 的对象上使用同步机制来保证底层数据容器的线程安全性,如果这样的对象不存在,就使用

List list = Collections.synchronizedList(new ArrayList(...)); 这个包装器方法创建一个线程安全的 List,这是最好地避免意外的以非同步的方式读取 List 导致异常发生的方法。

④: 这个类的 iterator 和 listiterator 是 快速失败地(fail-fast),在创建迭代器之后,如果没有通过迭代器对 List 的元素进行 add/remove ,就会导致计数器异常,从而抛出 ConcurrentModificationException 并发修改异常。所以,面对并发修改,迭代器会快速而干净地是啊比,而不会因为数据可能被修改,导致程序在未来发生不确定行为的风险。 【快速失败机制的设计意义】

⑤: 需要注意的是,迭代器的快速失败行为机制无法得到保证,通常来说,在没有使用同步机制的情况下发生对容器地并发修改, fail-fast 机制会尽最大努力抛出 ConcurrentModificationException 异常。【但是这并不是一个强力地机制,无法保证一定抛出】所以程序不能完全依赖并发修改异常带来的正确性,这个异常仅用于检测错误。

关键点总结:

  • ArrayList 这个 List 的具体实现类,底层是数组,允许存在 null 元素。
  • szieisEmptygetsetiteratorlistIterator 是 O(1) 时间复杂度,所以非常适合查询遍历, 添加元素 add 是 O(n) 复杂度,其他的操作是线性复杂度
  • 与 LinkedList 相比, ArrayList 的 常数因子更低。【但是还不知道这代表着啥,需要查一下】
  • ArrayList 的数组会动态地扩容,并且带来相应地开销。
  • ArrayList 非线程安全,多线程环境下需要使用同步机制,要么将其封装在线程安全的类中,要么就使用提供的 wrapper 方法创建一个线程安全的 List【但是这种 List 性能太低,其实现原理就是在所有对 Lits 访问地方法上增加了监视器锁】
  • 快速失败并不能保证线程安全性,只是用来检测错误,不能过于依赖。

类变量:

// 默认容量,也就是数组的初始大小
private static final int DEFAULT_CAPACITY = 10;

// ArrayList 空实例的共享数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 共享空数组实例,用于默认大小的空数组实例,用来明确添加第一个元素时需要多大的容量。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 真正存储 ArrayList 中元素的数组
transient Object[] elementData; // non-private to simplify nested class access

// ArrayList 的真正大小
private int size;

构造方法:


// Collection 规范中要求的无参构造,这里的具体是把上面的空数组作为无参构造的数组
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}    


// 指定数组大小的构造函数 如果给定的参数 大于0,就新创建一个指定个大小的数组赋值给 elementData
// 如果指定大小为0, 则将  EMPTY_ELEMENTDATA 赋值给 elementData
// todo 这里有个疑问, EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是 static final 的空数组,区别在哪里?为什么要定义2个,而无参构造使用的是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这里当数组大小为0的时候使用的却是 EMPTY_ELEMENTDATA 
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  }
}

 
// Collection 规范中定义的要有的入参是 Collection 的构造函数 
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // replace with empty array.
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

核心方法

1. 添加元素,以及添加的过程中可能涉及到的扩容操作

添加元素流程图:

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 直接将元素放入数组尾部
  elementData[size++] = e;
  return true;
}

// 将元素放入插入指定索引处
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++;
}

// ---------- 添加元素相关调用方法 ---------- // 

// 这里的 minCapacity 是 当前的 ArrayList 大小 + 1 ,也就是最顶上的 add 方法传入进来的 参数
private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 这里如果当前的数组是初始数组,则将当前 size + 1 与默认容量 10 比较,返回较大的那个,如果不是初始数组,则直接返回 size + 1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

// 这个方法有两个作用,1、是计数器 modCount 的累加  2是判断是否需要扩容
// 当 size + 1 > 当前数组的长度的时候 进行扩容 这里主要针对的还是初始化的情况
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;
  // 这里的新容量是旧的容量的 1.5 倍 ,新容量 = 旧容量 +  旧容量/2 
  int newCapacity = oldCapacity + (oldCapacity >> 1); 
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  // 如果插入的元素量非常巨大,大到 Integer.MAX_VALUE - 8 这个量级,则进行一次巨大化扩容
  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);
}

// 这里感觉  Integer.MAX_VALUE 和  MAX_ARRAY_SIZE 也差不多了,后者就必前者小8 
private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}

删除元素

这里提供了两个删除方法:

  • 删除指定索引位置的元素
  • 删除指定对象
// 删除指定索引位置的元素 
public E remove(int index) {
  // 先检查范围,如果索引超出大小就抛索引越界异常
  rangeCheck(index);
	// 修改计数器,如果有其他线程或非迭代器修改则抛出并发修改异常
  modCount++;
  // 获取对应索引的元素
  E oldValue = elementData(index);
	
  // 定位删除索引后的第一个元素,并将其之后的元素向前移动一位,复制到新的数组中
  // 数组的随后一个元素被置为null 等待垃圾回收器回收
  // 将被删除的元素作为方法的返回值
  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;
}

// 传入一个要删除的对象,可以传入 null 
public boolean remove(Object o) {
  // 如果传入的是 null ,则遍历 List,并去除第一个为 null 的元素
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    // 如果删除元素不为空,则遍历并调用 equals 方法找到与传入对象相同的元素,并移除,返回 true
    for (int index = 0; index < size; index++)
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  // 如果对象不存在,返回 false 删除失败
  return false;
}

// ---------- 删除元素相关调用方法 ---------- // 

// 根据索引快速删除元素的方法
// 这里是将要删除索引之后的所有元素复制到一个新的数组中,前移一位,并将最后一个元素设置为 null ,方便 GC 工作。
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
}

遍历元素

ArrayList 的几种遍历方式:

  • for 循环通过下标遍历
  • 使用 Iterator 或 ListIterator 迭代器遍历
  • foreach 循环 (使用 Consumer)

Iterator 与 ListIterator 之间的区别:

区别ListIteratorIterator
添加对象add() 方法,支持向 List 中添加对象不支持
遍历对象双向遍历,hasNext()、next() 向后遍历
hasPrevious() 和 previous() 方法,可以向前遍历
只能向后遍历
定位当前元素索引位置通过 nextIndex() 和 previousIndex() 可以定位当前索引位置不支持
删除对象可以可以
修改对象通过 set() 支持修改 ArrayList 中的对象不支持

序列化

这里真正存储数据的数组被 transient 修饰,这个关键字的作用是让被修饰的成员属性不被序列化。

 transient Object[] elementData;

这与背后与 Java 的序列化机制有关:

  • 序列化的类必须实现 java.io.Serializable,否则会抛出 NotSerializableException 异常。
  • 如果没有显示声明 serialVersionUID 变量,则 Java 序列化机制会根据编译时 class 自动生成一个 serialVersionUID 作为序列化版本比较(用来验证一致性),如果检测到反序列化后的类的 serialVersionUID 与 对象二进制流的 serialVersionUID 不一致,则抛出异常。
  • Java 的序列化会将一个类包含的引用中所有成员变量保留下来(深度复制),所以类中的引用也必须实现 java.io.Serializable 接口
  • 字段被声明为 transient 后,默认序列化机制会忽略该字段,反序列化后自动获得 0 或者 null 值。
  • 静态成员不参与序列化
  • 每个类可以实现 readObjectwriteObject 实现自己的序列化策略、所以即使被 transient 修饰的成员变量也可以手动调用 ObjectOutputStreamwriteInt 等方法将这个成员变量序列化。
  • 任何一个 readObject 方法不管是显式还是默认,都会返回一个新建的实例,这个新建实例不同于该类初始化时创建的实例。
  • 每个类都可以实现 private Object readResolve() 方法,调用 readObject 之后,如果存在 readResolve 方法则自动调用该方法,readResolve 将对 readObject 的结果进行处理,并将其作为 readObject 的结果返回。 readResolve 的目的是保护性恢复对象,最重要的应用是保护性恢复单例、枚举类型对象。

所以 ArrayList 这里自己实现了 readObjectwriteObject 方法手动对 elementData 进行序列化。

不是要默认机制序列化 elementData 的原因是效率问题,如果 elementData 长度为100,但是实际并没有使用这么长,未使用的部分可以不进行序列化,这样可以提高效率,并且节省空间

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

  // 只序列化 size 个对象
  for (int i=0; i<size; i++) {
    s.writeObject(elementData[i]);
  }

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


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
    int capacity = calculateCapacity(elementData, size);
    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, 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();
    }
  }
}

小结

ArrayList 的特性与其底层数据结构密不可分,因为是数组,所以支持下标查询,查询性能很好,但是也因为是数组,如果增删会导致移动目标索引之前/之后的所有元素,并且涉及到数组的赋复制,所以性能与 LinkedList 相比并没有那么好。

参考资料

序列化那部分讲的挺全面的ArrayList 源码分析

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。