Java源码研究之容器(1)

如何看源码

很多时候我们看源码, 看完了以后经常也没啥收获, 有些地方看得懂, 有些地方看得模棱两可, 自己写代码的时候也不太能用得上看到的东西, 顶多就是一些小的知识点可能学得到.

我个人认为看源码是为了什么, 首先是为了模仿, 模仿是任何学习的最简单也是最根本的方法之一, 学习语言需要模仿, 学习设计需要模仿, 学习画画也需要模仿, 模仿是学习的第一步, 只有在充分的模仿之后才会逐步形成自己的东西.

因此我们去读源码的时候, 一定要牢记, 首先我们要模仿的是作者的设计, 去模仿作者的思维方式, 其次才是具体是如何实现的细节等问题.

当去学习一个优秀的开源库或框架的时候, 第一位的是看它的结构, 以及思考作者为什么这样设计.

在这里我们将来一点点的研究Java源码中设计得比较好, 并且经常会被使用, 但要想把它用好, 理解透还是需要下一番功夫的, 这个库就是 Java Collection Framework . 也就是常说的几个容器类.

备注: 本文所有的代码都来自于openjdk 6-b14源代码.

层级结构

首先我们来看Java Collection Framework 的一个基本结构, 它里面包含了很多比较常见的容器类, 例如ArrayList, HashMap这些.

容器类的主要作用还是放置同一类对象, 而容器和容器是既有共性, 又有差异性的. 我们就来看Java的大神是如何设计这个框架的, 当然我们也可以假设, 如果由我们来设计和实现这些容器, 会怎么设计.

一般来说容器可以分为四种, 这也是从常见的数据结构来分, 它们包括常见的List, Set, Queue, Map.

但如果对所有集合进行大分类, Java Collection Framework将所有的容器类都先分为两种:

1. Collection
2. Map

而Collection下面再细分为List, Set, Queue. 这里我们也可以思考一下为什么要这样设计, 可以带着这样的问题去阅读源码.

因为整个容器库比较庞大, 涉及到很多的容器, 因此我们这里先来主要看Collection下的List个分支, 从最顶部的接口一直看到具体的实现容器, 例如ArrayList, LinkedList等.

在看之前, 我们还是先提出几个问题, 在阅读这些大神的源码时, 带着这些问题去研究, 避免看的时候比较盲目.

带着问题看源码:

1. Collection框架的结构是怎样设计得?
2. 容器和容器之间的共性和特性又是什么?
3. ArrayList的实现方式是什么?
4. LinkedList的实现方式是什么?
5. ArrayList和LinkedList的区别是什么?
6. ArrayList和Vector的区别是什么?
7. Iterator和Enumeration的区别是什么?
8. 集合类是如何实现fail-safe机制的?

上面的这些问题, 其他我想大部分人都能够说出一二, 而我们这次去研究源码, 就是为了以后能说出个三四. 所以请先忘记你之前认为是对的知识, 我们跟着源码一起来学习.

Iterable

所有List,Set,Queue这些集合类, 都可以进行遍历, 并使用for循环语句, 这是因为整个Collection层级的类都实现了最根部的这个接口, 它是一切的源头, 因此我们先从它来研究.

// 实现这个接口即允许一个对象可以用于foreach语句
interface Iterable<T> {
  Iterator<T> iterator();
}

这个接口的含义就是可以进行迭代的对象, 它只有一个方法, 返回了一个用于迭代这个集合的迭代器, 迭代器的接口定义如下:

interface Iterator<E> {
  boolean hasNext();
  E next();
  void remove();
}

这个接口的含义是: 集合的迭代器. 这个迭代器是用于替代旧版本的Enumeration接口, 而它和Enumeration的不同在于:

1. Iterator多余了一个remove方法, 用于在迭代的时候删除元素.
2. 方法名字改良了: hasMoreElements改为了hasNext, nextElements改成了next

这里可以了解一下历史, 那就是1.2这次版本的升级.

之前在1.1版本的时候使用的 Enumeration 类, 而到1.2的时候则替换成了 Iterator , 而几个1.1版本的旧集合类例如 Vector , HashTable 都使用到了 Enumeration , 而在1.2升级的时候则使用 ArrayList 替换了 Vector , HashMap 来替换 HashTable . 可以看出在98年底发布的这个1.2版本是Java一个非常重要的升级, 整个容器类都做出了比较大的改动. 而这整体容器类的框架(Java Collections Framework)都是由当时加入Sun公司的Josh Bloch一手打造的, 而这个顶顶大名的Josh Bloch正是《Effective Java》一书的作者了.

闲话扯远, 继续回来看源码.

对于迭代器, 需要注意的是remove方法. 在使用Iterator遍历集合的时候, 是不能直接调用集合的删除或添加方法来修改集合结构的, 这样会导致抛出 ConcurrentModificationException 异常. 而必须使用Iterator的remove方法来删除, 至于为什么会这样, 在研究ArrayList源码的时候会揭晓.

Collection

下面我们来看例如List, Set, Queue这些集合类的根接口, 集合之父:

interface Collection<E> extends Iterable<E> {
  Iterator<E> iterator();
  
  int size();
  boolean isEmpty();
  
  boolean contains(Object o);
  boolean containsAll(Collection<?> c);
   
  Object[] toArray();
  <T> T[] toArray(T[] a);
  
  boolean add(E e);
  boolean addAll(Collection<? extends E> c);
  boolean remove(Object o);
  boolean removeAll(Collection<?> c);
  boolean retainAll(Collection<?> c); // 取交集
  
  void clear();
  
  boolean equals(Object o);
  int hashCode();
}

这些方法应该都比较熟悉, 当我们使用ArrayList的时候, 基本都是在调用这些方法.

一个Collection指的就是一组对象的集合, 这些对象被称为集合内的元素, 有些集合允许重复的元素, 而有些则不允许. 有些集合是有序的, 而有些则是无序的. JDK不会直接实现这个Collection类, 而是将其分得更细, 例如用List, Set之类的子接口来继承它, 再去实现这些具体的子接口.

一般来说, 所有的集合实现类都应该会提供两个标准的构造函数:

1. 无参的构造函数, 用于创建一个空集合.
2. 有一个参数的构造函数, 这个参数为另一个集合, 用于创建与其参数相同的元素的新集合(即将传入的这个参数的集合复制出一个新集合).

例如ArrayList的两个构造函数:

List<Object> list1 = new ArrayList<>();
List<Object> list2 = new ArrayList<>(list1); // 复制list1, 创建一个新集合

对于一些会修改到集合的方法, 可以抛出UnsupportedOperationException, 来表示该集合不支持该操作, 例如对于不可修改的集合, 调用addAll方法则可以抛出这个异常.

这些方法包括: add addAll remove removeAll retainAll clear

一些集合的实现可能对它所包含的元素有一定的限制条件, 例如一些集合禁止包含null元素, 有些则对它们元素的类型有限制. 尝试添加不符合限制的元素则会抛出unchecked异常, 例如 NullPointerException 或 ClassCastException等. 在尝试查询不合法元素是否存在时, 有些会只是返回false, 而有些则会抛出异常, 一般来说, 对于尝试将不合法元素插入到集合时, 可能会抛出异常, 也有可能什么都没有发生返回成功, 这要看具体实现类时怎么选择的.

这里值得一提的就是 toArray 方法, 当我们需要将例如 List 转换成 array 的时候经常会用到这个方法, 例如:

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");

String[] arr = (String[])list.toArray();

哎呀, 最后一行一定会报错的, 因为无参的toArray方法返回的Object[], 不能强转. 而应该使用有参的方法:

String[] arr = new String[10];
arr = list.toArray(arr);

传进去的参数是一个具体类型的数组, 这样返回的就为这个类型的数组了, 不需要强转类型, 也就不会报错了.

这里就有两个疑问:

1. 对于toArray返回的这个数组进行修改的时候, 会不会影响到原来的List呢?
2. 如果传入的这个array的大小和List的大小不一致会怎样呢?

对于问题1, 答案是否定的, toArray返回的数组是独立于List的, 因为它返回的是一份复制出来的数组, 对其进行修改不会影响到原来的List.

对于问题2, 则有三种可能:

1. 如果传入的array小于list的size, 即不够装, 那么则会重新创建一个数组, 将list的元素copy进去.
2. 如果传入的array等于list的size, 即刚刚够装, 那么则会直接将list的元素copy进传入的这个array里面去,
3. 如果传入的array大于list的size, 即空间反则多了, 那么还是会将list的元素copy进传入的这个array里面去, 但是在最后一项的后面, 设置以为null值作为数组的末尾标识符.

如下所示:

{
    String[] arr1 = new String[0];
    String[] arr2 = list.toArray(arr1);
    System.out.println(Arrays.toString(arr2)); 
    // output: [0, 1, 2]
    System.out.println(arr1 != arr2); 
    // output: true, 重新创建了一个arr对象, 和传入的对象不相同
}

{
    String[] arr1 = new String[]{"a", "b", "c", "d", "e"};
    String[] arr2 = list.toArray(arr1);
    System.out.println(Arrays.toString(arr2)); 
    // output: [0, 1, 2, null, "e"]
    System.out.println(arr1 == arr2); 
    // output: true, 是同一个arr对象
}

List

下面就来看这次的重点, List接口:

interface List<E> extends Collection<E> {
  
  ListIterator<E> listIterator();
  ListIterator<E> listIterator(int index);

  void add(int index, E element);
  boolean addAll(int index, Collection<? extends E> c);
  
  E remove(int index);
  
  int indexOf(Object o);
  int lastIndexOf(Object o);
  
  E get(int index);
  E set(int index, E element);
  
  List<E> subList(int formIndex, int toIndex);
}

之前我们说了, Collection代表的是一个集合, 而List, Set, Queue是更细分的子接口, 用于表达各种不同类型的集合, 而不同的地方主要在于这个集合是如何存储和处理元素的, 例如是有序还是无序, 是否允许null等等.

而List接口代表的是一种有序的集合, 也被称为序列(sequence), 这种集合可以精准的控制列表中每个元素的插入位置. 也可以通过一个index来访问具体的元素, 并且可以搜索列表中的元素.

和set不同, List允许重复的元素. 也允许null作为元素.

List接口虽然继承于Collection, 也即间接继承与Iterable, 但是它除了提供Iterator迭代器用于遍历, 还提供一种特殊的迭代器叫做 ListIterator , 它继承与Iterator接口, 但提供更多的方法:

interface ListIterator<E> extends Iterator<E> {
  boolean hasNext();
  E next();
  
  boolean hasPrevious();
  E previous();
  
  int nextIndex();
  int previousIndex();
  
  void add(E e);
  void set(E e);
  void remove();
}

由此可看出, ListIterator增加了双向的访问, 以及set/add方法分别用于替换和插入.

除此之外, List接口还提供在指定的位置开始使用ListIterator遍历的方法, 而不需要从开头进行遍历.

List接口还提供两种方法来搜索指定的对象(indexOf, lastIndexOf). 从性能的角度来看, 应该谨慎使用它们, 因为在很多实现类中, 它们都讲执行昂贵而费时的线性搜索. 即遍历集合直到找到指定的元素.

另外List接口还提供一个subList方法, 用于返回列表中的一个子视图(从fromIndex到toIndex之间), 这里必须注意它返回的不是一个复制后的子集合, 而是list的一个子视图, 为什么成为子视图, 因为它其实就是原来的list, 只是通过偏移量来进行访问来进行访问, 所以对subList和原list进行任何非结构性的结构, 会都互相影响到.

List<String> list = new ArrayList<>();
list.add("0");
list.add("1");
list.add("2");
list.add("3");
list.add("4");

List<String> subList = list.subList(0, 3); // [0, 1, 2]

// 非结构性修改: 对subList修改一个元素
subList.set(0, "a");
System.out.println(subList); // [a, 1, 2]
System.out.println(list);    // [a, 1, 2, 3, 4] 原来的list也被修改了

// 结构性修改: 对subList增加一个元素
subList.add("b");
System.out.println(subList); // [a, 1, 2, b]
System.out.println(list);    // [a, 1, 2, b, 3, 4] 原来的list也添加了一个元素

// 结构性修改: 对list增加一个元素
list.add("c");
System.out.println(subList); 
// 报错ConcurrentModificationException

由此可看出, 对于subList和list之间的联系:

1. 对于subList或list进行非结构性修改, 会同时影响到subList和list.
2. 对于subList进行结构性修改(删除或添加元素), 则会对list有同样的影响.
3. 但对于list进行结构性修改后, 原来的subList就不能用了, 访问时会抛出ConcurrentModificationException异常.

利用这一点, 可以快速的删除一个列表的一个区间, 例如:

list.subList(from, to).clear();

AbstractCollection

之前的几个类都是接口, 这里开始研究几个关键的抽象类, 分别对应之前介绍的那几个接口:

例如: AbstractCollection实现了Collection接口, 而AbstractList实现了List接口:

abstract class AbstractCollection<E> implements Collection<E> {

  public abstract Iterator<E> iterator();
  public abstract int size(); 
  
  public boolean add(E e) {
    throw new UnsupportedOperationException();
  }
  
  // ...
}

这个类实现了Collection接口的一些基本结构, 要去实现一个不可修改的Collection, 只需要继承这个抽象类并实现它的两个抽象方法即可.

而要去实现一个可修改的Collection, 则需要重写这个抽象类的add方法, 因为在这个抽象类的add方法里什么都没有做, 只是抛出了UnsupportedOperationException异常. 其次是iterator方法返回的迭代器必须实现remove方法.

当然这个抽象类对于很多方法的实现都是一个通用性的方案, 对于具体的集合在继承它的时候都可以去重写它的任何方法.

这里我们可以理解一下这个类的设计思路, 也能对Collection下的几个容器有一个粗鲁的认知.

我们之前讲过整个Java Collection Framework的设计, 是不断是对容器进行细化, 具体化的过程.

例如最根部的这个AbstractCollection抽象类, 首先它是对于Collection接口的实现, 那么我们来思考它到底抽象出来的是一个怎样的容器.

在Iterable接口的层面, 抽象出来的是:

1. 一个可以遍历的对象

而在AbstractCollection抽象类的层面, 是第一次抽象出Collection这个概念, 它其实描述了所有容器的共性, 我们来看这些共性是什么, 这个容器的概念究竟是什么:

一个容器:

1. 它可以被遍历.
2. 它是有大小的.
3. 它可以被转换成数组.
4. 可以添加元素(如果支持的前提下)
5. 可以删除元素(如果它的迭代器支持删除操作的前提下)
6. 可以清空元素(如果它的迭代器支持删除操作的前提下)
7. 可以取交集(如果它的迭代器支持删除操作的前提下)

基本上在这个层次, 容器这个概念就被抽象到这里了. 也就是说在这个层面并不限定容器具体如何去放置它的元素, 而只是抽象出这个容器概念, 以及它应该有的一些操作. 而且对于有些操作, 例如是否可以add, 是否可以remove, 这些都没有明确的定义.这样设计得好处就是, 它没有限制这个容器是否可以被修改, 而这这个层面, 这个容器是不可以被修改的, 除非继承者去明确的支持它.

而AbstractCollection的实现, 主要是利用两个抽象方法的调用 iterator() 和 size() 来实现:

1. isEmpty() 检查是否为空, size() 为 0 则为空.
2. contains(Object) 检查是否包含某个元素 , 使用迭代器将容器遍历一遍, 如果有equals的则表示包含, 立即返回true.
3. toArray() 使用迭代器遍历一遍复制到新的数组里
4. remove() 使用迭代器遍历一遍, 如果有equals的则马上使用迭代器的remove来删除元素.
5. clear() 使用迭代器遍历一遍, 一个个的删除元素.

这里可以看出, 基本上这个抽象类就使用了两个抽象方法, 把其他所有的Collection接口的方法都实现了一遍(除了add), 这正是设计的巧妙之处, 而大部分的实现都是靠遍历来实现的, 包括删除操作都是由迭代器提供的, 也可以看出来迭代器在容器中的作用.

而为什么只需要把迭代器抽象出来, 下面的子类就可以实现出不同的容器出来呢, 因为大部分容器的区别还是在于如何放置元素和取出元素上面, 因此不同的迭代器就足以提供不同的容器特性了.

AbstractList

这个抽象类继承于刚才的AbstractCollection的类, 它主要是对List接口进行一个基本实现, 它的实现是主要是由支持随机访问的数据结构所支持(例如array), 而对于需要按顺序访问数据的结构应该使用AbstractSequentialList类.

abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    public abstract E get(int index);
    //public abstract int size(); 
  
    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }
  
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
  
    public void remove(int index) {
        throw new UnsupportedOperationException();
    }
}

实现一个不可修改的List, 需要继承这个抽象类, 并且实现get(int)和size()方法即可.

去实现一个可修改的列表, 则必须另外重写set(int ,E)方法.

去实现一个可变大小的列表, 则必须另外重写add(int, E)和remove(int)方法.

这个抽象类还实现了Iterator和ListIterator两个迭代器, 则继承它的类不需要再去实现迭代器了.

这里同样的我们先理解一下在List这个层面, 到底抽象出的是一个怎样更具体的容器.

List:

1. 它是一个有序的容器.
2. 它是一个支持随机访问的容器.
3. 它支持双向遍历.
4. 它可能还支持从中间插入/替换/删除.
5. 它可以搜索某个元素.(从头开始搜索或从尾开始搜索).

而在AbstractList这个抽象, 它主要实现的是迭代器, 之前我们说过在AbstractCollection抽象层, 基本靠抽象的迭代器就实现了绝大部分的方法, 而在AbstractList层面, 则具体的实现了一个列表迭代器.

也可以理解ListIterator是List的关键所在, 正是因为它才提供了List的大部分功能. 而仅仅靠Iterator是不够的. 所以我们在仔细研究这个列表迭代器到底是如何实现的.

首先我们知道ListIterator接口是继承与Iterator接口的, 也就是说它其实是一种特殊的迭代器, 专门用于对List进行迭代而已.

而它的实现类也分为了两步走, 第一步是实现Iterator接口:

private class Itr implements Iterator<E> {
}

第二步是继承这个类, 并且扩展的实现ListIterator接口:

private class ListItr extends Itr implements ListIterator<E> {
}

这是一个比较好的设计, 首先它把逻辑根据概念区分开了, 没有混在一起, 如果一般设计可能直接混成一个类, 直接实现ListIterator接口了(因为它本来就继承了Iterator), 但是从概念上来说首先是它就是一个纯粹的迭代器, 只需要实现迭代的功能, 然后才出现一个列表迭代器, 来实现一些便于遍历List的扩展功能. 并且在不同需求的时候只返回对应的迭代器:

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

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

这样设计其实就是一个最小化特权的设计, 例如当我们仅仅向对一个list进行常规迭代的时候, 那么它就只需要返回我们一个常规的迭代器, 而不会返回我们一个包含了其他功能的特殊迭代器, 一则调用者根本不需要, 二则这样一来更为安全. 作为一个良好封装的模块, 就是应该按需提供最小化的访问权限给外部调用者.

一个个的来看, 先看Itr类:, 在这个迭代器里面实现了fast-fail机制, 所谓fast-fail机制即指两种情况:

1. 在单线程的情况下, 遍历时修改了list的结构则抛出异常.
2. 在多线程的情况下, 一个线程正在遍历, 而另一个线程修改了list的结构, 则抛出异常.

而所谓的结构性修改包括add, remove, clear等操作. 需要注意的在这个抽象层次只是提供了fast-fail机制的支持, 但具体的使用不使用这个机制还是由具体的实现类来控制的, 而例如ArrayList都是使用了该机制的.

下面我们来具体看, 是如何实现fast-fail机制的, 关键的代码如下:

protected transient int modCount = 0;

private class Itr implements Iterator<E> {
    int expectedModCount = modCount;
  
    final void checkForComodification() {
        if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
  
    public E next() {
      checkForComodification();
      // ...
    }
  
    public void remove() {
      // ...
      checkForComodification();
      // ...
    }
}

首先在List容器里有一个结构修改次数的count值, 这里说一个题外话就是transient 关键词表示的是指在序列化对象的时候不用序列化这个成员变量.

然后在每次初始化迭代器的时候, 都会将当前List的这个count值复制一遍, 存在迭代器里面, 而在每次进行对list进行结构性修改时, list里面的count就自增, 而在迭代器进行遍历的过程中, 一旦检查到这个count值变化了, 则会抛出 ConcurrentModificationException 异常. 从而实现避免在遍历的过程中因为List的结构发生变化而导致不确定的结果, 就是具体fast-fail的实现机制.

而ListIterator的实现比较简单, 就是在Iterator的基础上增加了双向访问, 和set/add方法, 这里就不累述了. 而正是因为ListIterator可以实现反向访问, 因此lastIndexOf才可以从末尾开始查找.

除了迭代器以外, 另一个重要的实现就是对于 subList 的支持, 需要注意的是例如在ArrayList上调用 subList() 方法返回的这个子视图并不是一个ArrayList, 而是 SubList 类型.

public List<E> subList(int fromIndex, int toIndex) {
    return (this instanceof RandomAccess ?
            new RandomAccessSubList<E>(this, fromIndex, toIndex) :
            new SubList<E>(this, fromIndex, toIndex));
}

而且SubList是两个变种的, 其中一个实现了 RandomAccess . 如果这个List实现了RandomAccess接口, 那么subList返回的也是一个实现了RandomAccess接口的SubList类型. 例如ArrayList和Vector都实现了这个接口. 这个接口其实是一个标记接口, 用来表示这个类支持快速的(通常是恒定时间)的随机访问. 而对于这个接口的实现类, 一般情况下for循环比foreach/iterator循环要快一些.

我们先来看SubList类, 这个类是直接继承于AbstractList的:

class SubList<E> extends AbstractList<E> {
  private final AbstractList<E> l;
  private final int offset;
  private int size;
  
  SubList(AbstractList<E> list, int fromIndex, int toIndex) {
    // ...
    l = list;
    offset = fromIndex;
    size = toIndex - fromIndex;
    this.modeCount = l.modCount;
  }
  
    public void add(int index, E element) {
        // ...
        checkForComodification();
        // ...
        this.modCount = l.modCount;
        // ...
    }
  
    // ...
  
    private void checkForComodification() {
        if (this.modCount != l.modCount)
            throw new ConcurrentModificationException();
        }
    }
}

从上我们看出来为什么说对SubList的非结构性结构修改会直接对原list造成影响, 而且影响是相互的, 而对list进行结构性修改则直接对导致subList抛出ConcurrentModificationException异常.

因为首先SubList为什么称为一个子视图, 因为它本来就是由原list所支撑的, 它访问的就是原list, 只是在访问的时候增加了一个offset的偏移量进行访问, 因此对subList和list任何一方做修改都会影响到对方, 它们两从本质来说就是一个list.

其二在在初始化SubList的时候也是将原List的结构修改次数modCount复制并保持一个一份, 每次在访问SubList的时候, 都会去检查这两个count是否相同, 如果不相等, 则表明原list的结构被别人修改了, 那么这个SubList则应该被废弃, 不能再访问, 直接抛出异常.

对于RandomAccessSubList而言, 因为它是目的只是为了实现RandomAccess接口, 因此基本逻辑和SubList并没有什么区别, 只是使用这个接口进行了标记可支持快速随机访问而已, 这里也不再累述.

ArrayList

研究了这么久, 终于到了List家族最熟悉的一个类了, 那就是伟大的ArrayList. ArrayList继承于上一节介绍的AbstractList, 同样继承于AbstractList的还有Vector, 这里我们先来研究ArrayList, 再去研究Vector.

ArrayList是对List接口的一个重要实现类, 它由一个可调整大小的数组(array)来实现, 它是目前为止我们研究的第一个具体的容器类. 它实现了所有的List接口, 并且允许包含任何一种元素, 包括null值. 这个类大致上相当于Vector, 但是不是同步的(线程安全的).

size(), isEmpty(), get(), set(), iterator(), listIterator() 操作的时间复杂度是常数阶, 即O(1),

add() 操作是的时间复杂度是线性阶, 即O(n),

其他操作大体上来说也可以说是线性的, 复杂度的常量比LinkedList要小一些.

每个ArrayList实例都有一个容量(capacity), 这个容量就是用于存储列表中元素的array的大小. 它总是至少与列表大小一样大. 当把元素添加到ArrayList的时候, 其容量也有自动增长.

需要注意的是ArrayList不是线程安全的, 必须使用Collections.synchronizedList来包装它才能变为线程安全的, 支持并发访问.

然后我们刚才说了AbstractList提供了fast-fail机制, 提供了modCount字段, 而ArrayList里使用了这个字段, 实现了fast-fail机制, 因此在遍历的时候需要对结构进行了修改会抛出ConcurrentModificationException.

需要说明的是fast-fail并不是做任何硬性的保证, 支持fast-fail的迭代器会尽早的去抛出异常, 但程序的正常性不应该依赖于此机制, 此机制只应该用于检测bug.

我们来看ArrayList的关键代码:

public class ArrayList<E> extends AbstractList<E> 
        implements List<E>, RandomAccess, Cloneable, Serializable {
    private transient Object[] elementData;
    private int size;
  
    public ArrayList(int initialCapacity) {
      super();
      // ...
      this.elementData = new Object[initialCapacity];
    }
  
    public E get(int index) {
      rangeCheck(index);
      return elementData(index);
    }
  
    public E set(int index, E element) {
      rangeCheck(index);
      
      E oldValue = elementData(index);
      elementData[index] = element;
      return oldValue;
    }
  
    public boolean add(E e) {
      ensureCapacity(size + 1);
      elementData[size++] = e;
      return true;
    }

}

这里先研究最基础的代码, 其他内容再一一来看, 从此我们基本已经可以看出来ArrayList的基本实现方式, 之所以叫做ArrayList, 就是因为它是用一个Array来实现List接口的.

在其内部有一个默认大小的Object数组, list的元素都会放置在这个array中, 在get的时候直接从这个数组中取元素, 而在add的时候, 会先去自动调整array的大小, 再将元素放置到array里面.

所有从理论来说, 可以把ArrayList看成是一个支持自动动态调整大小的数组.

这里面比较关键的就是看它是如何动态的调整数组大小的:

public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

首先初始化list的时候可以提供一个初始的大小, 例如默认为10, 那么则会创建一个大小为10的object数组, 当每次往list里add数据的时候, 都会先去检查这个数组的大小够不够, 例如在插入第11个元素的时候, 发现数组的大小不够放下新的元素, 那么则会对数组进行扩容, 理论来说会将数组扩大到当前大小的1.5倍+1, 例如默认为10, 第一次扩容后为16, 第二次扩容后为25, 依次类推.

因此大多数情况下, 其实ArrayList内部的数组大小是要对于其size值的, 正是因为这样所有ArrayList还提供一个方法可以将当期的数组大小刚好调整到size的值, 即最小化空间.

public void trimToSize() {
  modCount++;
  int oldCapacity = elementData.length;
  if(size < oldCapacity) {
    elementData = Arrays.copyOf(elementData, size);
  }
}

我们看到每当对list进行结构性修改的时候, 都会对modCount进行自增操作, 这正是fast-fail机制的基础.

从源码上我们可能看出为什么get(int)和set(int, E)的时间复杂度为O(1), 因为它们都是直接使用下标对数组进行操作, 都比较快, 所以说ArrayList支持快速随机访问.

而add(E)的时间复杂度为O(n), 随着元素的增多而更慢, 因为每次当空间不足的时候, 都需要把所有元素复制到一个新的更大的数组里去, 因此平均下来, 每次add所需的时间和元素的多少成正比.

而为什么说ArrayList在中间进行插入和删除会比较慢呢(比如相对于LinkedList而言), 我们来看源码就一目了然了:

public void add(int index, E element) { 
    rangeCheckForAdd(index);

    ensureCapacity(size+1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

我们可以看到当在列表中间进行插入操作的时候会将整个数组在插入的位置整体向后复制移动, 然后将新元素插入到制定的位置. 这显然是比较低效的, 而且在数组大小不足的时候, 还会先对数组进行扩容(也会复制一遍整个数组). 因此在列表中间进行插入操作肯定会比较慢, 并且随着元素的增多越来越慢.

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; // Let gc do its work

    return oldValue;
}

从中间删除则类似, 是将删除下标之后的数组整体前移一位, 然后将末尾的一位设置为null.

例如: [0, 1, 2, 3, 4, 5], remove(3)后则变为了 [0, 1, 2, 4, 5, null]

这里有一个题外话题就是, 之前ensureCapacity方法里使用的是Arrays.copyOf, 而在remove方法里使用的是System.arraycopy(), 这两个方法有什么区别呢?

public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

其实Arrays.copyOf也是在调用System.arraycopy来复制数组的, 唯一区别是它在复制前创建了了一个新的数组, 然后复制到了这个新的数组里了. 而至于System.arraycopy则是一个native方法.

其中有一个批量删除的方法中的算法比较巧妙, 它使用两个变量来对数组进行平移:

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) {
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

例如列表为: [0, 1, 2, 3, 4, 5, 6]

需要删除的列表为 [2, 5], 那么遍历的时候, 数组是这样变化的:

r=0,w=0: [0, 1, 2, 3, 4, 5, 6] r++, w++

r=1,w=1: [0, 1, 2, 3, 4, 5, 6] r++, w++

r=2,w=2: [0, 1, 2, 3, 4, 5, 6] r++, w不变, 使得后面的元素都往前平移一位

r=3,w=2: [0, 1, 3, 3, 4, 5, 6] r++, w++

r=4,w=3: [0, 1, 3, 4, 4, 5, 6] r++, w++

r=5,w=4: [0, 1, 3, 4, 5, 6, 6] r++, w不变

r=6,w=4: [0, 1, 3, 4, 6, 6, 6]

finally: w < size: [0 , 1, 3, 4, 6, null, null] , 清空后面的项目.

另外在ArrayList里面又重新实现了自己的迭代器和SubList. 其他都没有特别的地方了.

下一节将来研究LInkedList和Vector两个List容器类.