本人的源码阅读主要聚焦于类的使用场景，一般只在java层面进行分析，没有深入到一些native方法的实现。并且由于知识储备不完整，很可能出现疏漏甚至是谬误，欢迎指出共同学习

本文基于corretto-17.0.9源码，参考本文时请打开相应的源码对照，否则你会不知道我在说什么

简介

JCF（Java Collections Framework）为Java开发者提供了通用的容器，而每个可以直接拿来用的容器又实现了很多接口，并且有些接口方法还有default实现，为了更好地掌握JCF的整体结构，甚至以后需要到自己开发容器的时候，对应该实现哪些接口可以做到了然于胸。

接口嘛，一方面是为了实现多态，另一方面是为了规范，而且接口的方法一般不会实现，因此更多的是通过看文档注释来了解这个接口是干什么的。下面按照依赖关系顺序分析，先介绍被依赖的接口/类。

代码分析

Iterator

Iterator是一个集合上的迭代器，用来替代 Enumeration（旧API，可以忽略）进行遍历、迭代。迭代不一定是顺序的，对于List来说可能是顺序的，但是对于Set来说就不一定了。

public interface Iterator<E> {
  // 查询是否有下一个元素
  boolean hasNext();
  // 获取当前，并将指针指向下一个元素
  E next();
	// 移除上一次调用next得到的元素
  default void remove() {
    throw new UnsupportedOperationException("remove");
  }
	// 遍历从当前指针开始的剩余元素
  default void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    while (hasNext())
      action.accept(next());
  }
}

注释里说的“指针”其实是假想出来的。举个例子，比如ArrayList，其新生成的迭代器相当于一个指针，初始指向下标为0的位置，此时hasNext询问“指针”指向的位置有没有元素，next的行为则是返回当前指针指向的元素，然后把“指针”指向下一个元素的位置。

因此使用迭代器遍历是这样的：

ArrayList<String> arr = new ArrayList<>();
Iterator<String> c = arr.iterator();
while (c.hashNext()) {
  String s = c.next();
  // ...
}

另外，迭代器还支持在遍历的过程中删除当前指针指向的元素，比如你像下面这么干，就会删除ArrayList的第一个元素：

ArrayList<String> arr = new ArrayList<>();
Iterator<String> c = arr.iterator();
arr.next();
arr.remove();

当然，remove得子类去根据集合是否支持，不支持的话直接抛异常。

Iterable

public interface Iterable<T> {
  // 返回集合的迭代器
  Iterator<T> iterator();
	// 提供函数调用式的遍历方式
  default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
      action.accept(t);
    }
  }
	// 返回集合的spliterator
  default Spliterator<T> spliterator() {
    return Spliterators.spliteratorUnknownSize(iterator(), 0);
  }
}

实现这个接口主要是可以让对象支持for-each语法，比如ArrayList就实现了这个接口，因此相比使用迭代器，你可以写出更简洁的遍历方式：

ArrayList<String> arr = new ArrayList<>();
for (String s : arr) {
  // ...
}

这种简洁的遍历方式是java的语法糖，实际上它还是依靠iterator来实现的，也就是会被编译成之前使用迭代器的那个样子（可能会与实际的编译情况有差别，不细究）：

ArrayList<String> arr = new ArrayList<>();
Iterator<String> c = arr.iterator();
while (c.hashNext()) {
  String s = c.next();
  // ...
}

最后的spliterator函数，返回一个Spliterator对象，这个是在java8引入的，与stream、并行计算有关，暂时不讲，以后会单独介绍。

Collection

Collection接口实现了Iterable接口，通过注释的方式来说明每个方法的作用。流相关函数忽略。

public interface Collection<E> extends Iterable<E> {
  // 集合元素个数，如果元素个数超过Integer.MAX_VALUE，则返回Integer.MAX_VALUE
  int size();
  // 集合是否为空
  boolean isEmpty();
  // 是否包含o，具体是通过equals方法来对比
  boolean contains(Object o);
  Iterator<E> iterator();
  // 返回一个包含所有元素的新数组，也就是说数组是new出来的（元素不是new出来的），不是集合的底层数组
  Object[] toArray();
  // 返回一个包含所有元素的新数组，类型为T。如果数组长度小于集合大小那么会new一个数组，否则返回a
  <T> T[] toArray(T[] a);
  // 新增一个元素
  boolean add(E e);
  // 移除一个元素
  boolean remove(Object o);
  // 是否包含c中的所有元素
  boolean containsAll(Collection<?> c);
  // 添加c中的所有元素
  boolean addAll(Collection<? extends E> c);
  // 移除c中的所有元素（如果元素不在集合中的话不产生影响）
  boolean removeAll(Collection<?> c);
  // 移除所有满足filter的元素，返回是否有元素被移除
  default boolean removeIf(Predicate<? super E> filter);
  // 移除所有不在c中的元素，与removeAll的功能恰好相反
  boolean retainAll(Collection<?> c);
  // 移除集合中所有元素
  void clear();
  
  // 流相关
  default Spliterator<E> spliterator();
  default Stream<E> stream();
  default Stream<E> parallelStream();
}

AbstractCollection

AbstractCollection实现了Collection接口，目的是实现一些通用的方法，这样一来想要实现Collection的类可以考虑继承AbstractCollection，省去功夫重新实现其中的一些方法，比如isEmpty显而易见可以实现成size()==0，如果子类有更加高效的实现再考虑重写AbstractCollection提供的默认实现。

下面来看一下AbstractCollection实现了的方法：

isEmptry

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

contains

// 循环遍历比较o和集合中的元素，如果equals则返回true
public boolean contains(Object o) {
  Iterator<E> it = iterator();
  if (o==null) {
    while (it.hasNext())
      if (it.next()==null)
        return true;
  } else {
    while (it.hasNext())
      if (o.equals(it.next()))
        return true;
  }
  return false;
}

toArray

// 循环遍历集合，将元素放到数组r。集合大小可能会在遍历时由于并发增删发生变化，从而影响最终数组的大小
public Object[] toArray() {
  Object[] r = new Object[size()];
  Iterator<E> it = iterator();
  for (int i = 0; i < r.length; i++) {
    // 如果没有下一个元素了，那么直接truncate
    if (!it.hasNext())
      return Arrays.copyOf(r, i);
    r[i] = it.next();
  }
  // 如果集合大小大于原来的大小，那么调用finishToArray继续加入元素到数组中
  return it.hasNext() ? finishToArray(r, it) : r;
}

// 使用iterator将剩下的元素加入数组中
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
  int len = r.length;
  int i = len;
  while (it.hasNext()) {
    // 数组需要扩容
    if (i == len) {
      // 一般情况下扩展数组大小为原先大小的两倍+1（具体查看ArraysSupport.newLength）
      len = ArraysSupport.newLength(len,
        1,             /* minimum growth */
        (len >> 1) + 1 /* preferred growth */);
      r = Arrays.copyOf(r, len);
    }
    r[i++] = (T)it.next();
  }
	// 返回数组并且删除扩容后多余的长度
  return (i == len) ? r : Arrays.copyOf(r, i);
}

add

public boolean add(E e) {
  // 实现为抛出异常的原因：
  // 1. 默认集合为immutable的，如果要支持add，重写这个方法即可
  // 2. AbstractCollection没有默认的存储元素的底层数据结构，而且迭代器不支持add操作，因此add方法留给子类实现
  throw new UnsupportedOperationException();
}

remove

// 类似contains方法，只是多了一句it.remove
public boolean remove(Object o) {
  Iterator<E> it = iterator();
  if (o==null) {
    while (it.hasNext()) {
      if (it.next()==null) {
        it.remove();
        return true;
      }
    }
  } else {
    while (it.hasNext()) {
      if (o.equals(it.next())) {
        it.remove();
        return true;
      }
    }
  }
  return false;
}

还有几个xxxAll的批操作方法就不展示了，大同小异。

AbstratctCollection基于迭代器实现了一些常用的删除、包含等操作，总体来说比较简单。

List

List接口实现Collection接口，代表的是 有序的集合（sequence），每个元素都对应一个下标，允许存储重复的元素（这是官方推荐的做法），支持随机访问、插入、新增。在Collection的Iterator的基础上，List提供了列表迭代器ListIterator，除了Iterator接口提供的操作外，还允许基于位置的元素插入、替换以及双向遍历。

先看一下新增的迭代器ListIterator

public interface ListIterator<E> extends Iterator<E> {
	// 就是Iterator中的hashNext、next、remove
  boolean hasNext();
  E next();
  void remove();
  
  // 询问当前指针的上一个位置是否有元素
  boolean hasPrevious();
  // 将指针-1，并返回指针指向的位置
  E previous();
	// 当前指针的指向的下标
  int nextIndex();
  // 当前指针指向的下标-1
  int previousIndex();
  
  void set(E e);
  void add(E e);
}

下面是新增的方法，太简单的就不注释了，猜也能猜出来功能是什么。

// 通过迭代器的set方法，将每个位置上的元素替换为用户指定的元素
default void replaceAll(UnaryOperator<E> operator) {
  Objects.requireNonNull(operator);
  final ListIterator<E> li = this.listIterator();
  while (li.hasNext()) {
    li.set(operator.apply(li.next()));
  }
}
// 通过toArray转换成数组并用工具类Arrays.sort排序，然后再把排序后的数组重新设到集合上
default void sort(Comparator<? super E> c) {
  Object[] a = this.toArray();
  Arrays.sort(a, (Comparator) c);
  ListIterator<E> i = this.listIterator();
  for (Object e : a) {
    i.next();
    i.set((E) e);
  }
}
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
// 其实就是firstIndexOf
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
// 从index开始的列表迭代器，即“指针”初始位置为index而不是-1
ListIterator<E> listIterator(int index);
// 返回列表的一个“view”。对view做结构化的修改以及非结构的修改都会影响原始的列表
// 如果在生成了view之后对原列表做结构化的修改，并且不是通过view作的这个修改，那么这个行为是未定义的（由子类定义），比如在ArrayList会抛ConcurrentModificationException
// 结构化修改：比如subList(0, 10).clear()会使得原始列表的前10个元素被删除
// 非结构化修改：比如subList(3, 5).set(0, obj)会使得原列表下标为3的元素被设置为obj
List<E> subList(int fromIndex, int toIndex);

List还添加了一堆静态方法of的重载，来方便地生成immutable List，比如

static <E> List<E> of(E... elements);

AbstractList

AbstractList继承于AbstractColletion。类似AbstractColletion，AbstractList实现了List的一些方法。Iterator、ListIterator也是在本类中实现的。

Itr（Iterator的实现）

只需要牢记，Iterator用于向后（单向）遍历，指针指向下一个获取的元素，因此是先获取指针指向的元素，然后指针+1。

private class Itr implements Iterator<E> {
  // iterator的“指针”，实际上是当前遍历到的下标
  int cursor = 0;
  // 上次指针修改前的值
  int lastRet = -1;
  // 记录创建iterator时列表的结构化修改次数
  int expectedModCount = modCount;

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

  public E next() {
    checkForComodification();
    try {
      // 获取当前指针指向的元素
      int i = cursor;
      E next = get(i);
      lastRet = i;
      // 指针+1
      cursor = i + 1;
      return next;
    } catch (IndexOutOfBoundsException e) {
      checkForComodification();
      throw new NoSuchElementException(e);
    }
  }
	// 删除上次next对应的元素
  public void remove() {
    if (lastRet < 0)
      throw new IllegalStateException();
    checkForComodification();

    try {
      // 移除指针修改前指向的元素
      AbstractList.this.remove(lastRet);
      // 指针-1
      if (lastRet < cursor)
        cursor--;
      // 重设lastRet，指示该位置的元素已经被移除，不能二次移除
      lastRet = -1;
      expectedModCount = modCount;
    } catch (IndexOutOfBoundsException e) {
      throw new ConcurrentModificationException();
    }
  }

  // 检查列表是否被结构化修改了，而且不是被this iterator修改的，那么抛出异常避免进一步出错
  final void checkForComodification() {
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
  }
}

比较简单，基本上是把Iterator接口定义好的功能用代码翻译一下而已，看注释就行。

需要注意的点：

checkForComodification，虽然抛出的异常名是“并发修改异常”，看，但分析代码可以知道，在iterator被创建后，只能用这个iterator来修改集合的结构（比如remove），否则，无论是当前线程还是其他线程修改了集合的结构后，这个iterator不能再被使用，否则会抛异常。
不能连续remove元素，remove相当于在逻辑上留下了一个“空洞”（lastRet=-1），即非法元素，那肯定不能remove一个“空洞”。如果要实现从当前元素开始删除后面所有的元素可以写成：
```
while (ite.hasNext()) {
  it.next();
  it.remove();
}
```

ListItr（ListIterator的实现）

ListItr实现了ListIterator，继承于Itr。只需要牢记ListIterator用于双向遍历，向后遍历的行为与Iterator一样，向前遍历时，指针先-1，然后获取指针指向的元素。

private class ListItr extends Itr implements ListIterator<E> {
	// 指针从index开始
  ListItr(int index) {
    cursor = index;
  }
	// 如果指针=0，那么前一个元素就是-1，前面就没有元素了，返回false
  public boolean hasPrevious() {
    return cursor != 0;
  }
	// 获取上一个元素
  public E previous() {
    checkForComodification();
    try {
      // 指针-1
      int i = cursor - 1;
      // 获取上一个元素
      E previous = get(i);
      lastRet = cursor = i;
      return previous;
    } catch (IndexOutOfBoundsException e) {
      checkForComodification();
      throw new NoSuchElementException(e);
    }
  }
	// 获取下一个元素下标
  public int nextIndex() {
    return cursor;
  }
	// 获取上一个元素下标
  public int previousIndex() {
    return cursor-1;
  }
	// 设置当前指针指向的元素
  public void set(E e) {
    // 如果是非法位置，则抛异常
    if (lastRet < 0)
      throw new IllegalStateException();
    checkForComodification();

    try {
      AbstractList.this.set(lastRet, e);
      expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
      throw new ConcurrentModificationException();
    }
  }
	// 将元素插入当前指针指向的位置，当前指针指向的元素及其后面的元素全体“后移”
  public void add(E e) {
    checkForComodification();

    try {
      int i = cursor;
      AbstractList.this.add(i, e);
      // 注意这两行
      lastRet = -1;
      cursor = i + 1;
      expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
      throw new ConcurrentModificationException();
    }
  }
}

需要注意的点：

之前说过，使用remove删除完元素之后，当前指针可以视为指向“空洞”，不可以进行操作，包括set。因此lastRet=-1的时候进行set的话会抛异常
add之后，指针还是指向原来的元素，因此cursor=i+1，并且lastRet=-1设置“空洞”，不能进行set和remove。

回归AbstractList，看一下它实现了List接口的方法：

// 在尾部添加一个元素
public boolean add(E e) {
  add(size(), e);
  return true;
}

// 往后找o第一次出现的下标
public int indexOf(Object o) {
  ListIterator<E> it = listIterator();
  if (o==null) {
    while (it.hasNext())
      if (it.next()==null)
        return it.previousIndex();
  } else {
    while (it.hasNext())
      if (o.equals(it.next()))
        return it.previousIndex();
  }
  return -1;
}

// 往前找o第一次出现的下标
public int lastIndexOf(Object o) {
  ListIterator<E> it = listIterator(size());
  if (o==null) {
    while (it.hasPrevious())
        if (it.previous()==null)
          return it.nextIndex();
  } else {
    while (it.hasPrevious())
      if (o.equals(it.previous()))
        return it.nextIndex();
  }
  return -1;
}

// 删除所有元素
public void clear() {
  removeRange(0, size());
}

// 移除[fromIndex, toIndex)内的元素
protected void removeRange(int fromIndex, int toIndex) {
  ListIterator<E> it = listIterator(fromIndex);
  for (int i=0, n=toIndex-fromIndex; i<n; i++) {
    it.next();
    it.remove();
  }
}

// 获取迭代器
public Iterator<E> iterator() {
  return new Itr();
}

// 获取列表迭代器
public ListIterator<E> listIterator() {
  return listIterator(0);
}

// 获取列表的子视图
public List<E> subList(int fromIndex, int toIndex) {
  subListRangeCheck(fromIndex, toIndex, size());
  return (this instanceof RandomAccess ?
      new RandomAccessSubList<>(this, fromIndex, toIndex) :
      new SubList<>(this, fromIndex, toIndex));
}

// 重写equals规则
public boolean equals(Object o) {
  if (o == this)
    return true;
  if (!(o instanceof List))
    return false;

  ListIterator<E> e1 = listIterator();
  ListIterator<?> e2 = ((List<?>) o).listIterator();
  while (e1.hasNext() && e2.hasNext()) {
    E o1 = e1.next();
    Object o2 = e2.next();
    if (!(o1==null ? o2==null : o1.equals(o2)))
      return false;
  }
  return !(e1.hasNext() || e2.hasNext());
}

值得分析的方法只有两个：subList和equals

equals：对Object.equals的重载。当两个列表的每个元素都相等的时候，列表视为相等
subList：这个方法根据列表是否支持随机访问，分别返回SubList或RandomAccessSubList。这两个类都继承自AbstractList，以 代理模式，代理this对象，封装了对列表某个范围的数据访问，官方文档称之为原列表的一个“视图”，对该视图的任何结构与非结构上的修改都相当于对原列表进行修改，目的是方便我们像使用普通List那样来操作列表的子列表。

SubList

SubList是AbstractList的静态内部类，继承于AbstractList。看一下成员变量：

private static class SubList<E> extends AbstractList<E> {
  // 被代理对象
  private final AbstractList<E> root;
  // 由于SubList也是一个List，因此subList可以链式调用，parent记录调用subList的SubList对象
  private final SubList<E> parent;
  // 记录该子列表在原列表的偏移量，比如list.subList(3, 5)，那么生成的SubList.offset=3
  private final int offset;
  // 子列表大小
  protected int size;
}

下面分析SubList的方法，由于SubList是代理类，因此SubList的方法肯定是借助被代理对象来实现的：

public R xyz(params) {
  // ...
  return root.xyz(params)
  // ...
}

几乎每个公有方法都调用了checkForComodification，之前稍微提到过，但都不够详细或者有所缺漏，在这儿结合SubList全面剖析一下它背后的理念。

checkForComodification检查列表是否被非子孙子列表做过结构性修改（即检查modCount与parent.modCount是否相等）如果被修改过的话，再去访问该子列表是不允许的。这里“子孙”一词借用了树的概念：原列表视为根节点，其subList为第二层节点，subList.subList为第三层节点....，当对某个节点做结构性修改，只会对祖先进行同步，此时访问本节点和祖先节点都是没问题的，但除了该节点的祖先外的其他节点与本节点此时是不一致的，访问它们就会抛异常。talk is cheap, show me the code：

List<String> list = ...;
List<String> sub1 = list.subList(3, 5);
List<String> sub1_1 = sub2.subList(0, 3);
List<String> sub2 = list.subList(6, 10);

/*
此时的树：
list(root)
├── sub1
│   └── sub1_1
└── sub2
*/

list.remove(0); // 最后一行报错
sub2.remove(0); // 最后一行报错
sub1_1.remove(0); // ok的
sub1.remove(0); // ok的

// 访问sub1节点
sub1.size();

由此，我们进一步思考为什么要这样设计：回到“视图”这个概念，子节点是对父节点的视图，使用视图的初衷就是为了方便操作原列表的某个范围，因此：

子节点发生结构性修改后，肯定能继续访问父节点，否则如果抛异常的话，要视图干什么呢。
父节点发生结构性修改后，子节点（视图）可能没办法再去正确映射父节点这段范围，如果还要更新子节点的话，成本太高了，因为子节点可能不止一个，直接把子节点给废了就好了。
兄弟/叔父等旁系节点发生结构性修改后，与父节点发生修改同理，都是对同一个祖先的映射，相当于祖先被修改了，因此本节点要废掉。

有了前面的铺垫，很多方法基本不用再分析。只有updateSizeAndModCount和listIterator需要讲下：

updateSizeAndModCount：每次对子列表做完结构性修改后（remove、add等），维护modCount和size：
```
private void updateSizeAndModCount(int sizeChange) {
  SubList<E> slist = this;
  do {
    slist.size += sizeChange;
    slist.modCount = root.modCount;
    slist = slist.parent;
  } while (slist != null);
}
```
上面说过，节点发生修改，只需要同步祖先即可，因此借助parent，往root的方向，更新一路上父节点的modCount。

listIterator：由于子列表只映射原列表的某个范围，因此肯定不能直接返回原列表的迭代器，SubList自己实现了一个匿名内部类，并且也是代理模式，代理原列表（父节点）的迭代器，比较简单，明白原理随便看看就行：

public ListIterator<E> listIterator(int index) {
  checkForComodification();
  rangeCheckForAdd(index);

  return new ListIterator<E>() {
    private final ListIterator<E> i = root.listIterator(offset + index);

    public boolean hasNext() {
      return nextIndex() < size;
    }

    public E next() {
      if (hasNext())
        return i.next();
      else
        throw new NoSuchElementException();
    }

    public boolean hasPrevious() {
      return previousIndex() >= 0;
    }

    public E previous() {
      if (hasPrevious())
        return i.previous();
      else
        throw new NoSuchElementException();
    }

    public int nextIndex() {
      return i.nextIndex() - offset;
    }

    public int previousIndex() {
      return i.previousIndex() - offset;
    }

    public void remove() {
      i.remove();
      updateSizeAndModCount(-1);
    }

    public void set(E e) {
      i.set(e);
    }

    public void add(E e) {
      i.add(e);
      updateSizeAndModCount(1);
    }
  };
}

RandomAccessSubList

继承于SubList，没有实现新的方法，只是多实现了一个RandomAccess接口，这个接口作为标记接口没有任何方法。这个类的目的是用于调用subList的时候保留RandomAccess接口。

说个题外话，像RandomAccess的空接口有什么用呢？用作标记。举个例子，某个函数接收参数类型为List，功能是遍历并输出元素，但是你不想采用迭代器的方式，而是使用下标的方式去遍历（因为可能下标方式是直接访问数组，而迭代器还得创建迭代器对象，调用额外的方法等，直接下标可能效率更高），但如果List是不支持随机访问的LinkedList，那么用下标方式就会很慢了，因此可以判断有没有实现RandomAccess快速判断支不支持随机访问，以选择迭代方式：

public void iter(List<String> list) {
  if (list instanceof RandomAccess) {
    for (int i = 0; i < list.size(); i++) {
      String s = list[i];
      sout(s);
    }
  } else {
    for (String s : list) {
      sout(s);
    }
  }
}

类似的，还有Cloneable接口、Serializable接口等，都是用作标记。