春招复习2：Java集合类（上）

Java集合类（上）

集合类我们平时用起来确实是真香，很方便。但理解其底层的数据结构实现才是最重要的，就像了解一个女孩子，要知道她喜欢什么一样。要了解集合类的底层实现，让我们一起来看看源码。

一、集合和数组的区别

集合：集合是java中提供的一种容器，可以用来存储多个数据。

集合和数组既然都是容器，它们有啥区别呢？

• 数组的长度是固定的。集合的长度是可变的。（这很重要）
• 数组中存储的是同一类型的元素，可以存储基本数据类型值。集合存储的都是对象。而且对象的类型可以不一致。在开发中一般当对象多的时候，使用集合进行存储。

集合都是存储的是包装类。例如：Integer、Long、Float、Double

二、集合概述

下面图片是整体的架构，这里只表现了类和接口类的继承实现关系，选取了平时使用比较多的类，如LinkedList、ArrayList、HashMap、TreeMap等，没有考虑并发容器。集合类分为两个体系，Collection和Map。我们先看Collection。

2.1 Collection

从上往下看，非常清晰，Collection实现了Iterable接口，也就是迭代器接口，我们后面马上就说。

Collection有三个子接口，分别是List、Queue、Set。

而且Collection、List、Queue、Set都有自己对应的抽象类。

经典的问题，接口和抽象类的区别是什么?

1. 抽象类是为了代码的一个复用，将子类共同方法组织到抽象类中，减少了代码的重复，结构看起来清晰，体现了多态的特性。

2. 接口更注重的是行为抽象，提高可拓展性，降低代码之间的耦合性，使调用者更关注的是接口，而不是具体的实现。例如Map、HashMap

3. 子类的代码重复，就会抽象出抽象父类来减少重复代码。

4. 接口则是我们在设计系统时先确定好的，之后再考虑具体实现。

还有一些我们平时常用的具体类。ArrayList、LinkedList、HashSet、HashMap、TreeMap

这些类还实现了一些特殊的接口，我们马上再看。

2.2 Map

Map和Collection大同小异，这里只放一下整体架构，大家有个印象就好，后面我们详细再说。

三、Iterable

首先看一下接口定义。Iterable接口表示一种能力，具有迭代的能力(able形容词后缀)，Iterable又叫迭代器接口。Iterable接口中有三个方法，其余两个和本文的内容无关，我们忽略。

iterator方法用于返回一个迭代器，在各个容器中有各自的实现。真正的迭代器类是Iterator接口，其中定义了迭代器的基本操作，在各个容器中也有具体的迭代器实现，在后面的文章再具体分析。

public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    //返回一个迭代器，Iterator是真正的迭代器实现，而Iterable则是表示一种能力（able形容词）——迭代的能力。
    Iterator<T> iterator();
    ......
}

public interface Iterator<E> {
    /**
     * Returns {@code true} if the iteration has more elements.
     * (In other words, returns {@code true} if {@link #next} would
     * return an element rather than throwing an exception.)
     *
     * @return {@code true} if the iteration has more elements
     */
    boolean hasNext();

    /**
     * Returns the next element in the iteration.
     *
     * @return the next element in the iteration
     * @throws NoSuchElementException if the iteration has no more elements
     */
    E next();
    ......
}

四、Cloneable、RandomAccess、Serializable

我们经常发现Cloneable、Serializable、 RandomAccess三个接口经常出现，实现率很高。我们经常使用的类中，都至少实现了这三个接口中的一个。

我们来翻看他们的定义，我们惊讶的发现了一个共同的特征，三个接口都是空的！！这种接口叫做标志接口，他不定义任何操作，只是起到一种标记作用。

 * @author  unascribed
 * @see     java.lang.CloneNotSupportedException
 * @see     java.lang.Object#clone()
 * @since   JDK1.0
 */
public interface Cloneable {
}

 * <p>This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @since 1.4
 */
public interface RandomAccess {
}

 * @author  unascribed
 * @see java.io.ObjectOutputStream
 * @see java.io.ObjectInputStream
 * @see java.io.ObjectOutput
 * @see java.io.ObjectInput
 * @see java.io.Externalizable
 * @since   JDK1.1
 */
public interface Serializable {
}

4.1 Cloneable

Object有个方法 clone()，他和Cloneable一起合作，用来实现Java中的克隆。

class Student implements Cloneable{
    private int number;

    @Override
    public Object clone() {
        Student stu = null;
        try{
            stu = (Student)super.clone();
        }catch(CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return stu;
    }
}

4.2 RandomAccess

RandomAccess的意思是快速随机访问（数组快速访问索引）。

下面是Java Collections工具类中二分查找的实现，可以看到。

如果容器支持快速随机访问，则会使用基于索引的二分查找，否则使用基于迭代的二分查找。

// java.util.Collections
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

4.3 Serializable

Serializable标志一个类可以被序列化，数据在网络中传送是串行的，所以在网络中发送数据必须要进行序列化，接受数据要进行反序列化。

下面的方法中，如果需要被序列化的对象没有实现Serializable接口，则会抛出NotSerializableException异常。

// java.io.ObjectOutputStream 在输出流中
/*** @throws  NotSerializableException Some object to be serialized does not
* 		implement the java.io.Serializable interface.
*/
public final void writeObject(Object obj) throws IOException {
  if (enableOverride) {
    writeObjectOverride(obj);
    return;
  }
  try {
    writeObject0(obj, false);
  } catch (IOException ex) {
    if (depth == 0) {
      writeFatalException(ex);
    }
    throw ex;
  }
}

五、Iterator的实现

我们来详细分析一下Iterator接口，以及常见的实现，没有Set，是因为Set其实是一种特殊的Map

//下面是接口定义，定义了迭代器的基本操作。
public interface Iterator<E> {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
	
    //先不需要看此方法
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

Iterator下面有个接口，是ListIterator，一个是HashIterator，最后是PrivateEntryIterator，然后我们来分别看看。

5.1 ListInterator

除了继承Iterator的方法，他还自己定义了一系列用于List的迭代器方法

public interface ListIterator<E> extends Iterator<E> {

    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    void remove();

    void set(E e);

    void add(E e);
}

ListItr和Itr 它们都是Vector里面内部类，所以我们就直接看Vector的源码分析。

5.2 Vector

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    
    protected Object[] elementData;

    protected int elementCount;

    protected int capacityIncrement;
    
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    
	//初始化长度与ArrayList一样，都为10个长度
    public Vector() {
        this(10);
    }
	......很多方法 省略
    public synchronized void setSize(int newSize) {
        modCount++;
        if (newSize > elementCount) {
            ensureCapacityHelper(newSize);
        } else {
            for (int i = newSize ; i < elementCount ; i++) {
                elementData[i] = null;
            }
        }
        elementCount = newSize;
    }

根据源码我们可以知道，Vector的特点

1. 动态增长的数组，增长到原来的2倍长度（ArrayList确实增长到原来的1.5倍）

2. 线程安全（线程同步synchronized）的动态数组，ArrayList是线程不安全的。

   某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。但是由于特点1，在集合中使用数据量比较大的数据，用vector有一定的优势。

5.2.1 Itr

这是Vector默认返回的迭代器

// 获取Itr对象
public synchronized Iterator<E> iterator() {
    return new Itr();
}

// 获取index元素
E elementData(int index) {
	  return (E) elementData[index];
}

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; // 记录操作次数，用来支持 fast fail机制，在迭代时不能修改容器
	public boolean hasNext() {
  	// cursor == elementCount表示遍历到尾部
    return cursor != elementCount;
	}

    public E next() {
        // 锁Vector对象，保证不同的线程使用不同的迭代器操作同一Vector，同步执行
        synchronized (Vector.this) {
            // fast fail 机制，检查容器是否被修改
            checkForComodification();
            int i = cursor;
            if (i >= elementCount)
                throw new NoSuchElementException();
            cursor = i + 1;
            // 获取下一个cursor，并设置lastRet
            return elementData(lastRet = i);
        }
    }

    public void remove() {
        if (lastRet == -1)
            throw new IllegalStateException();
                // 同上
        synchronized (Vector.this) {
                // 同上
                checkForComodification();
                // 调用Vector方法，并重新设置modCount
                Vector.this.remove(lastRet);
                expectedModCount = modCount;
        }
        // 设置当前cursor 为lastRet，上次操作的索引。
        cursor = lastRet;
        lastRet = -1;
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
       // ...
    }

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

5.2.2 ListItr

这是Vector使用listIterator()返回的迭代器，阅读源码前先说明一下

1. cursor为当前索引。hasNext()
2. lastRet为上次返回数据的索引next()，如果调用了add或remove方法，lastRet为-1。
3. expectedModCount记录操作次数，为fast fail机制作准备，在迭代时不能并发修改容器。
4. 同步方法要锁Vector类synchronized，保证不同的迭代器对象同步操作同一个Vector容器

// 获取ListItr对象
public synchronized ListIterator<E> listIterator() {
    return new ListItr(0);
}

// 传入初始cursor值
public synchronized ListIterator<E> listIterator(int index) {
	  if (index < 0 || index > elementCount)
		    throw new IndexOutOfBoundsException("Index: "+index);
	  return new ListItr(index);
}

// 继承了Itr，所以拥有Itr的所有方法，这里只定义了ListIterator特有的方法。
final class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }
		
  	// 可以对比hasNext方法
    public boolean hasPrevious() {
        return cursor != 0;
    }

    public int nextIndex() {
        return cursor;
    }

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

  	// 对比next方法
    public E previous() {
      	// 同上
        synchronized (Vector.this) {
          	// 同上
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            cursor = i;
          	// 同样设置lastRet
            return elementData(lastRet = i);
        }
    }

  	// 设置上次遍历的值
    public void set(E e) {
        if (lastRet == -1)
            throw new IllegalStateException();
        synchronized (Vector.this) {
            checkForComodification();
            Vector.this.set(lastRet, e);
        }
    }
		
  	// 添加到cursor前一个位置
    public void add(E e) {
        int i = cursor;
        synchronized (Vector.this) {
            checkForComodification();
          	// 调用Vector方法，添加到cursor的位置，底层使用数组拷贝，将后面的元素向后移动
            Vector.this.add(i, e);
            expectedModCount = modCount;
        }
        cursor = i + 1;
        lastRet = -1;
    }
}

5.3 ArrayList

5.3.1 Itr

它与Vector一样，Itr是返回的默认迭代器方法。

ArrayList和Vector的迭代器实现基本相同，只是不支持并发访问，代码贴出来，大家看一下就好。

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

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;

    Itr() {}

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

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        // ...
    }

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

5.3.2 ListItr

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

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

5.4 LinkedList

5.4.1 ListItr

看源码前，我们先说明一下：

1. next方法：将当前节点的值返回，更新当前节点、当前索引，记录lastReturned
2. previous方法：如果初始化index为size，则将当前节点和lastReturned都指向最后一个节点。否则将当前节点和lastReturned都指向当前节点的前驱节点。将索引值减1.
3. remove方法：删除lastReturned指向的节点。如果当前节点next也指向被删除的节点，则将next指向下一个节点，否则当前索引减1.
4. set方法：比较简单，直接修改lastReturned指向的节点的值
5. add方法：如果初始化index为size，则添加到链表尾部，否则添加到当前节点的前面。当前索引+1.

public ListIterator<E> listIterator(int index) {
	  checkPositionIndex(index);
  	return new ListItr(index);
}

// Node
private static class Node<E> {
  	E item;
  	Node<E> next;
  	Node<E> prev;

  	Node(Node<E> prev, E element, Node<E> next) {
    		this.item = element;
    		this.next = next;
    		this.prev = prev;
  	}
}

// 定位第index个节点
Node<E> node(int index) {
  	// index在前一半，从前往后遍历，反之从后往前遍历
  	// 使用位运算，size / 2
  	if (index < (size >> 1)) {
    		Node<E> x = first;
    		for (int i = 0; i < index; i++)
      		x = x.next;
    		return x;
  	} else {
    		Node<E> x = last;
    		for (int i = size - 1; i > index; i--)
      		x = x.prev;
    		return x;
  	}
}


private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned; // 上一个返回的节点
    private Node<E> next; // 下一个准备返回的节点，可以理解为当前节点
    private int nextIndex; // 同样，下一个准备返回的索引，可以理解为当前索引
    private int expectedModCount = modCount; // 维护操作次数

    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

  	// ArrayList中使用的是 ！= 符号
  	// ArrayList中的cursor和LinkedList的nextIndex的操作只有++ 和 -- ，两个类的作者都是同一个人
  	// 实在不知道这两种写法有什么区别，或者说真的就是没有区别，望大神指点。
    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
      	// fast fail机制，后面就不再提了
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
				// 更新lastReture next nextIndex
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

  	// 参考hasNext方法
    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
				
      	// next == null 说明初始化index为size ->查看构造函数
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

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

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();
      
        Node<E> lastNext = lastReturned.next;
      	// 将lastreturned节点从链表中脱离出来
      	unlink(lastReturned);

      	// 如果之前调用previous方法，next == lastReturned，移除的是当前节点，则让当前引用指向下一个节点
      	// 否则之前调用的是next方法，lastReturned.next == next,移除的是next的前一个节点，则将当前索引减1
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
      
      	// 清除引用，方便GC
        lastReturned = null;
        expectedModCount++;
    }

  	// 设置lastReturned节点的值
    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        // 说明初始化index为size， 添加到链表尾
        if (next == null)
            linkLast(e);
        else
        // 添加到当前节点的前面
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        // ...
    }

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

5.4.2 DescendingIterator

Descending Iterator 翻译成中文是 下降迭代器。顾名思义，他是反向遍历的迭代器，只是对ListItr进行了简单的封装，源码如下。

即next为原先的previous，hasNext为原来的hasPrevious()

public Iterator<E> descendingIterator() {
    return new DescendingIterator();
}

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

5.5 PriorityQueue

PriorityQueue为优先队列，入列操作并没对所有加入的元素进行优先级排序。仅仅保证数组第一个元素是最小的即可。当第一个元素出列之后，对剩下的元素进行再排序，挑选出最小的元素排在数组第一个位置。

它的Iterator也是默认的Itr，存在 删除节点时节点上浮到已经遍历的位置 的问题。重点是使用forgetMeNot队列保存上浮的节点，最后遍历。

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

private final class Itr implements Iterator<E> {
	// 当前索引
    private int cursor = 0;
    // 上一个返回的索引
    private int lastRet = -1;
   	// 在remove方法中，调用Vector的removeAt方法。
  	// removeAt方法中会将最后一个节点替换到被删除的元素的位置
  	// 然后进行下沉操作siftDown，如果没有执行，说明当前节点比子节点都大
  	// 这时进行上浮操作siftUp，如果节点上浮，说明当前节点比父节点小
    
  	// 即当前节点上浮到已经遍历过的位置，此时使用forgetMeNot队列保存节点，最后再遍历
    private ArrayDeque<E> forgetMeNot = null;
    
	// 上一个返回的节点
    private E lastRetElt = null;
  	// 同上，fast fail机制
    private int expectedModCount = modCount;

    public boolean hasNext() {
      	// 首先判断索引是否超过size，没有直接返回，一定有next
        return cursor < size ||
          	// 索引超过size后，查看forgetMeNot队列
          	// 有节点说明在之前remove时，有上浮到已经遍历过的位置的节点，返回true
            (forgetMeNot != null && !forgetMeNot.isEmpty());
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (expectedModCount != modCount)
            throw new ConcurrentModificationException();
      
        if (cursor < size)
            return (E) queue[lastRet = cursor++];
      	
      	// 索引超过size后，查看forgetMeNot队列中是否有剩余的，在之前remove时上浮到已经遍历过的位置的节点
      	// 有则继续遍历forgetMeNot队列
        if (forgetMeNot != null) {
            lastRet = -1;
          	// 记录上一个返回节点
            lastRetElt = forgetMeNot.poll();
            if (lastRetElt != null)
                return lastRetElt;
        }
        throw new NoSuchElementException();
    }

    public void remove() {
        if (expectedModCount != modCount)
            throw new ConcurrentModificationException();
        if (lastRet != -1) { 
          	// 后面PriorityQueue类专题会分析removeAt方法
          	// 方法会将最后一个节点替换到被删除的位置，再进行下沉、上浮
          	// 通过返回值来说明是否上浮，不为null说明上浮了，返回目标节点
            E moved = PriorityQueue.this.removeAt(lastRet);
            lastRet = -1;
          
          	// moved == null说明最后一个节点替换到被删除位置后没有上浮
            if (moved == null)
                cursor--;
          	// 否则，说明节点上浮到已经遍历的位置，就将节点加到队列中，等待最后遍历
            else {
                if (forgetMeNot == null)
                    forgetMeNot = new ArrayDeque<>();
                forgetMeNot.add(moved);
            }
          
        } else if (lastRetElt != null) {
          	// 进入这里，说明上一次遍历是遍历forgetMeNot队列，则不存在上浮的问题
          	// 通过遍历找到目标节点索引，调用removeAt删除。（方法实现在本段代码最后）
            PriorityQueue.this.removeEq(lastRetElt);
            lastRetElt = null;
        } else {
            throw new IllegalStateException();
        }
      	// 删除节点，修改操作次数
        expectedModCount = modCount;
    }
}

boolean removeEq(Object o) {
  for (int i = 0; i < size; i++) {
    if (o == queue[i]) {
      removeAt(i);
      return true;
    }
  }
  return false;
}

5.6 HashMap

HashMap中Key、Value封装成Entry保存，所以遍历时有三种方式，Key、Value和Entry。

HashMap使用HashIterator用来实现基本遍历操作，再用KeyIterator、ValueIterator和EntryIterator封装next方法。

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
	// 省略方法...
}

abstract class HashIterator {
  	// 其实可以把next理解成当前节点，current理解成lastReturned节点，像之前那样
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot 桶索引

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
          	// 初始化next，找到第一个不为空的桶，next引用其第一个节点
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
      	// ******************核心***********************
      	// 更新current的值为next，next为更新后current的next
      	// 如果next为空，说明当前桶遍历完毕，进入下一个
        if ((next = (current = e).next) == null && (t = table) != null) {
          	// 找到下一个不为空的桶，next引用其第一个节点
            do {} while (index < t.length && (next = t[index++]) == null);
        }
      	// ******************核心***********************
        return e;
    }

  	// 移除current节点
    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
      
        current = null;
        K key = p.key;
      	// 调用HashMap的removeNode方法
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

// 下面是获取迭代器的方法

// HashMap.KeySet
public final Iterator<K> iterator() { 
  	return new KeyIterator(); 
}

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { 
      	return nextNode().key; 
    }
}

// HashMap.Values
public final Iterator<V> iterator() { 
  	return new ValueIterator(); 
}

final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { 
      	return nextNode().value; 
    }
}

// HashMap.entrySet
public final Iterator<Map.Entry<K,V>> iterator() {
  	return new EntryIterator();
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { 
      	return nextNode(); 
    }
}

5.7 TreeMap

abstract class PrivateEntryIterator<T> implements Iterator<T> {
    Entry<K,V> next; // 当前节点
    Entry<K,V> lastReturned; // 上一个返回的节点
    int expectedModCount; // 操作次数 fast fail机制

    PrivateEntryIterator(Entry<K,V> first) {
        expectedModCount = modCount;
        lastReturned = null;
        next = first;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
      	// 找到后继节点
        next = successor(e);
        lastReturned = e;
        return e;
    }

    final Entry<K,V> prevEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
      	// 找到前驱节点
        next = predecessor(e);
        lastReturned = e;
        return e;
    }

    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
      	// 删除上一个返回的节点
      	// 如果他有一个孩子，则子树则会替代他的位置
      	// 如果他有两个孩子，则会使其后继节点（右子树的最左孩子）替代他的位置，就需要调整next引用到lastReturned
        // deleted entries are replaced by their successors
        if (lastReturned.left != null && lastReturned.right != null)
            next = lastReturned;
        deleteEntry(lastReturned);
        expectedModCount = modCount;
        lastReturned = null;
    }
}


// 下面是获取迭代器的方法

// TreeMap.EntrySet
public Iterator<Map.Entry<K,V>> iterator() {
	  return new EntryIterator(getFirstEntry());
}

final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
    EntryIterator(Entry<K,V> first) {
        super(first);
    }
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}

// TreeMap.Values
public Iterator<V> iterator() {
		return new ValueIterator(getFirstEntry());
}

final class ValueIterator extends PrivateEntryIterator<V> {
    ValueIterator(Entry<K,V> first) {
        super(first);
    }
    public V next() {
        return nextEntry().value;
    }
}

Iterator<K> keyIterator() {
	  return new KeyIterator(getFirstEntry());
}

final class KeyIterator extends PrivateEntryIterator<K> {
    KeyIterator(Entry<K,V> first) {
        super(first);
    }
    public K next() {
        return nextEntry().key;
    }
}

Iterator<K> descendingKeyIterator() {
	  return new DescendingKeyIterator(getLastEntry());
}

final class DescendingKeyIterator extends PrivateEntryIterator<K> {
    DescendingKeyIterator(Entry<K,V> first) {
        super(first);
    }
    public K next() {
        return prevEntry().key;
    }
    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        deleteEntry(lastReturned);
        lastReturned = null;
        expectedModCount = modCount;
    }
}

六、Collection接口

下面是Collection中定义的接口列表，其中equals和hashCode是继承自Object，iterator方法是继承自Iterable，我们刚刚分析过。

6.1 接口源码分析

下面是Collection接口，我们主要看一下接口方法注释。

public interface Collection<E> extends Iterable<E> {
  
		/*************************查询操作******************************/

    /**
     * 返回集合的元素数量，最大是Integer.MAX_VALUE
     */
    int size();

    /**
     * list没有元素，则返回true
     */
    boolean isEmpty();

    /**
     * 如果在list中至少存在一个e，满足(o==null ? e==null : o.equals(e))，则返回true
     * @throws ClassCastException 如果集合不接受指定元素的类型
     * @throws NullPointerException 如果特定元素是null，而集合不接受null
     */
    boolean contains(Object o);
  
    /**
     * 返回一个迭代器
     */
    Iterator<E> iterator();

  	/**
     * 按照一定顺序返回一个包含所有元素的数组，返回Object数组（范型会在编译期擦除），修改数组不会影响集合。
     * 是基于数组和基于集合之间的api之间的桥梁
     */
    Object[] toArray();

    /**
     * 返回一个包含所有元素的数组，保存到指定数组，返回数组的运行时类型是指定数组的运行时类型。
     * 如果数组length小于集合数量，则按照指定类型和该集合的大小分配新数组。
     * 如果数组length大于集合数量，则将剩余空闲元素设为null
     *
     * 如果集合保证迭代器返回元素顺序，这个方法必须以相同的顺序返回元素
     * 是基于数组和基于集合之间的api之间的桥梁，并且可以控制返回数组的运行时类型，在某些情况下可以节省分配成本
     * （猜想应该是如果要在数组后面追加内容，则可以直接分配最后需要的空间大小，否则第一次分配的空间则面临回收）
     * 
     * 集合转数组demo：
     *     String[] y = x.toArray(new String[0]);
     *
     * @throws ArrayStoreException 如果指定数组的运行时类型不是集合中每一个元素的父类型
     * @throws NullPointerException 如果指定数组是null
     */
    <T> T[] toArray(T[] a);

		/*************************修改操作******************************/

    /**
     * 添加成功，返回true
     * 如果集合拒绝添加一个元素，必须抛出异常，而不是返回false
     * @throws UnsupportedOperationException 当前的集合不支持add操作
     * @throws ClassCastException 指定元素的类阻止将其添加到此集合中
     * @throws NullPointerException 指定元素为null，并且集合不允许null元素
     * @throws IllegalArgumentException 元素的某些属性阻止它被添加到这个集合中
     * @throws IllegalStateException 由于插入限制，此时不能添加元素
     */
    boolean add(E e);

    /**
     * 如果集合存在任意一个e，对于o满足 (o==null ? e==null : o.equals(e)，则移除e
     * 如果集合更改，返回true
     * @throws ClassCastException 如果集合不接受指定元素的类型
     * @throws NullPointerException 指定元素为null，并且集合不允许null元素
     * @throws UnsupportedOperationException 当前的集合不支持remove操作
     */
    boolean remove(Object o);


		/*************************批量操作******************************/

    /**
     * 如果集合包含所有指定元素返回true
     * @throws ClassCastException 如果集合不接受指定元素的类型
     * @throws NullPointerException 指定集合包含null，并且集合不允许null元素
     */
    boolean containsAll(Collection<?> c);

    /**
     * 将指定集合的所有元素添加到此集合，在操作中不能修改指定结合
     * @throws UnsupportedOperationException 当前的集合不支持addAll操作
     * @throws ClassCastException 指定集合中元素的类阻止将其添加到此集合中
     * @throws NullPointerException 指定集合包含null，并且集合不允许null元素
     * @throws IllegalArgumentException 如果集合中元素的某些属性阻止将其添加到此集合中
     * @throws IllegalStateException 由于插入限制，不是所有元素都可以在此时添加
     */
    boolean addAll(Collection<? extends E> c);

    /**
     * 删除此集合中包含指定集合的所有元素
     * @throws UnsupportedOperationException 当前的集合不支持removeAll操作
     * @throws ClassCastException 如果集合不接受指定元素的类型
     * @throws NullPointerException 指定集合包含null，并且集合不允许null元素
     */
    boolean removeAll(Collection<?> c);

    /**
     * 删除此集合中给定谓词的所有元素。迭代期间由谓词抛出的错误或运行时异常将传递给调用者。
     *
     * 实现要求：
     * 默认实现使用其iterator()遍历集合的所有元素。使用Iterator.remove()删除每个匹配的元素。
     * 如果集合的迭代器不支持删除，则将在第一个匹配的元素上抛出UnsupportedOperationException。
     * @param filter 对于要删除的元素，返回true的谓词
     * @return 如果任一元素被删除，返回true
     * @throws NullPointerException 如果指定过滤器为null
     * @throws UnsupportedOperationException 如果无法从该集合中删除元素
     * 如果无法删除匹配的元素，或者通常不支持删除，则实现可能会抛出此异常
     * @since 1.8
     */
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

    /**
     * 从此集合中删除指定集合中不包含的所有元素
     * 集合改变，返回true
     * @throws UnsupportedOperationException 当前集合不支持retainAll操作
     * @throws ClassCastException 至少一个元素的类型与指定集合不兼容（可选）
     * @throws NullPointerException 当前集合存在至少一个null元素，并且指定元素不支持null
     */
    boolean retainAll(Collection<?> c);

    /**
     * 移除集合中所有元素，方法返回后集合为空
     * @throws UnsupportedOperationException 当前的集合不支持clear操作
     */
    void clear();

  
		/*************************比较和散列******************************/

    /**
     * 将指定的对象与此集合进行相等性比较。
		 * 集合接口没有对Object.equal的通用契约添加任何规定
		 * “直接”实现集合接口的程序员必须考虑是否选择重写Object.equals。
		 * 最简单的方法是依赖对象的实现，实现者可能希望实现一个“值比较”来代替默认的“引用比较”。
		 * 
		 * 该方法的一般约定规定，等号必须是对称的
		 * List.equal方法和Set.equal方法的契约中，List只与其他List相等，而Set与其他Set相等。
     */
    boolean equals(Object o);

    /**
     * 返回当前集合的hash码
     * 虽然Collection接口没有对方法的通用契约添加任何规定
     * 但程序员应该注意，任何覆盖equals方法的类也必须覆盖hashCode方法，以满足hashCode的通用契约。
     * 特别是 c1.equals(c2) 意味着 c1.hashCode()==c2.hashCode()
     */
    int hashCode();

    /**
     * stream方法，暂时不管
     */
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }

    /**
     * stream方法，暂时不管
     */
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }

    /**
     * stream方法，暂时不管
     */
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

6.2 实现类AbstractCollection

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

    // 唯一的构造函数，通常提供给子类调用
    protected AbstractCollection() {
    }

    // 两个抽象方法
    public abstract Iterator<E> iterator();

    public abstract int size();


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

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

    public Object[] toArray() {
        // 这里的size只是估计值
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext())
              	// i还在循环，但是迭代器却没有下一个元素了，说明有并发remove操作，返回数组副本
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
      	// i遍历结束，迭代器还有下一个，说明有并发add操作，扩容，并将剩余元素添加到数组中
      	// 否则，返回数组
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        int size = size();
      	// 判断a的大小，不满足则利用反射创建新数组
        T[] r = a.length >= size ? a :
                  (T[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);
        Iterator<E> it = iterator();
				
        for (int i = 0; i < r.length; i++) {
          	// i还在循环，但是迭代器却没有下一个元素了，说明有并发remove操作
            if (! it.hasNext()) { 
              	// 如果没有创建新数组，最后一个元素置null，返回a
                if (a == r) {
                    r[i] = null; // null-terminate
                // 如果创建了新数组，并且当前数组长度大于a的长度，返回当前数组副本
                } else if (a.length < i) {
                    return Arrays.copyOf(r, i);
                // 如果创建了新数组，并且当前数组长度小于a的长度，将当前数组拷贝给a
                } else {
                    System.arraycopy(r, 0, a, 0, i);
                  	// 如果a数组没有用完，最后一个元素置null，返回a
                    if (a.length > i) {
                        a[i] = null;
                    } 
                }
                return a;
            }
            r[i] = (T)it.next();
        }
        // i遍历结束，迭代器还有下一个，说明有并发add操作，扩容，并将剩余元素添加到数组中
      	// 否则，返回数组
        return it.hasNext() ? finishToArray(r, it) : r;
    }

   /**
    * The maximum size of array to allocate.
    * Some VMs reserve some header words in an array.
    * Attempts to allocate larger arrays may result in
    * OutOfMemoryError: Requested array size exceeds VM limit
    */
  	// 最大数组数量 为 Integer.MAX_VALUE - 8
  	// 有的虚拟机实现，数组对象的头部会占用这8个字节
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  	// 扩容，并将迭代器剩余元素添加到数组中
    @SuppressWarnings("unchecked")
    private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
      	// 当前数组索引，从数组尾开始
        int i = r.length;
        while (it.hasNext()) {
          	// cap为数组长度
            int cap = r.length;
          	// 当前数组索引等于数组长度，扩容
            if (i == cap) {
              	// 扩容大小 newCap = cap * 1.5 + 1
                int newCap = cap + (cap >> 1) + 1;
                // 保证数组最大长度
                if (newCap - MAX_ARRAY_SIZE > 0)
                    newCap = hugeCapacity(cap + 1);
              	// 扩容
                r = Arrays.copyOf(r, newCap);
            }
          	// 迭代，添加到数组中
            r[i++] = (T)it.next();
        }
        // 如果当前索引等于数组长度，说明数组刚好用完，返回数组。否则，按照当前长度返回数组副本
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

  	// 求数组最大长度
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError
                ("Required array size too large");
      	// 如果没超过MAX_ARRAY_SIZE，就是MAX_ARRAY_SIZE
      	// 超过MAX_ARRAY_SIZE，最大是Integer.MAX_VALUE
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

	// 通过Collection接口注释中已经说明UnsupportedOperationException
  	// 说明AbstractCollection不支持add方法
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

  	// 移除o
    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;
    }

  	// 如果此集合中包含c中所有元素，返回true
    public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }

  	// 添加c中元素到此集合中
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
      	// 如果此集合改变，返回true
        return modified;
    }

  	// 对比retainAll，删除c中含有的元素
    public boolean removeAll(Collection<?> c) {
      	// 首先判断c不为空
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
     		// 如果此集合改变，返回true
        return modified;
    }

		// 删除c中没有的元素
    public boolean retainAll(Collection<?> c) {
      	// 首先判断c不为空
        Objects.requireNonNull(c);
      	// 标志
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
          	// 使用contains方法，使用迭代器遍历此集合中的元素，如果c中不存在，删除
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
      	// 如果此集合改变，返回true
        return modified;
    }

  	// 使用迭代器remove所有元素
    public void clear() {
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
    }

  	// 使用StringBuilder
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
          	// 当集合中添加了集合本身作为元素，会打印(this Collection)
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }

}

七、List接口

List接口继承了Collection接口，Collection接口中的定义就不重复了，还有就是自定的方法。

7.1 接口源码分析

// 在指定位置插入    
void add(int index, E element);

// 在指定位置，按照指定集合的迭代器顺序插入到当前list    
boolean addAll(int index, Collection<? extends E> c);

// 返回第index个元素    
E get(int index);

// 返回list中指定元素第一次出现的索引，没有返回-1.最低i(o==null ?get(i)==null: o.equals(get(i))   
int indexOf(Object o);

// 返回list中指定元素最后一次出现的索引，没有返回-1.最高i(o==null ?get(i)==null: o.equals(get(i))   
int lastIndexOf(Object o);

// 获取list迭代器    
ListIterator<E> listIterator();

// 获取从index索引开始的迭代器    
ListIterator<E> listIterator(int index);

// 删除index索引对应元素    
E remove(int index);

// 暂时不管
default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }  

// 修改index索引对应元素
E set(int index, E element);

// 排序的实现，个人感觉效率有点低。先获取数组，然后调用Arrays工具类排序，再用迭代器将排序后的元素set回去
// 我们发现Collections工具类的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);
        }
    }

// 返回从fromIndex索引到toIndex索引的列表的视图，下面会说到他的实现
List<E> subList(int fromIndex, int toIndex);

7.2 实现类AbstractList

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

  	// 通过迭代器，查看两个list中的每个元素是否相等
    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))) // 使用元素对象的equals方法
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

// hash值计算
public int hashCode() {
  	int hashCode = 1;
  	for (E e : this)
    		hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
  	return hashCode;
}

// 调用下面的方法，将由子类重写
public boolean add(E e) {
  	add(size(), e);
  	return true;
}

// 不支持add操作
public void add(int index, E element) {
  	throw new UnsupportedOperationException();
}

// 使用foreach，语法糖（另一篇博客有讲）编译期会改成迭代器实现
public boolean addAll(int index, Collection<? extends E> c) {
  	rangeCheckForAdd(index);
  	boolean modified = false;
  	for (E e : c) {
    		add(index++, e);
    		modified = true;
  	}
  	return modified;
}

// remove，从头到尾
public void clear() {
  	removeRange(0, size());
}

// 从前往后，查找指定元素索引，没有返回-1
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;
}

// 从后往前，查找指定元素索引，没有返回-1
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 Iterator<E> iterator() {
  	return new Itr();
}

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

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

  	return new ListItr(index);
}

// 不支持remove、set方法
public E remove(int index) {
  	throw new UnsupportedOperationException();
}

public E set(int index, E element) {
  	throw new UnsupportedOperationException();
}

// 返回从fromIndex索引到toIndex索引的列表的视图
// 这里根据RandomAccess进行了一个区分，之前的博客分析过，RandomAccess是支持随机访问的
public List<E> subList(int fromIndex, int toIndex) {
  	return (this instanceof RandomAccess ?
          new RandomAccessSubList<>(this, fromIndex, toIndex) :
          new SubList<>(this, fromIndex, toIndex));
}

// 还有三个工具方法
// 删除从索引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();
  	}
}

// 判断index合法性
private void rangeCheckForAdd(int index) {
  	if (index < 0 || index > size())
    		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 越界信息
private String outOfBoundsMsg(int index) {
  	return "Index: "+index+", Size: "+size();
}

7.2.1 AbstractList的实现类SubList

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) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }

  /**************************************************************************/
  /*下面的方法，封装了父列表的相关方法，进行相关检查，考虑offset，修改size、modCount，以适应视图*/
    public E set(int index, E element) {
        rangeCheck(index);
        checkForComodification();
        return l.set(index+offset, element);
    }

    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return l.get(index+offset);
    }

    public int size() {
        checkForComodification();
        return size;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        checkForComodification();
        l.add(index+offset, element);
        this.modCount = l.modCount;
        size++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = l.remove(index+offset);
        this.modCount = l.modCount;
        size--;
        return result;
    }

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

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

        checkForComodification();
        l.addAll(offset+index, c);
        this.modCount = l.modCount;
        size += cSize;
        return true;
    }
  
  /*************************************************************************************/

  	// 获取视图的listIterator
    public Iterator<E> iterator() {
        return listIterator();
    }

  	// 封装父列表的listIterator
  	// 考虑offset，修改size、modCount，以适应视图
    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);

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

            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();
                SubList.this.modCount = l.modCount;
                size--;
            }

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

            public void add(E e) {
                i.add(e);
                SubList.this.modCount = l.modCount;
                size++;
            }
        };
    }

  	// 创建当前试图的视图
    public List<E> subList(int fromIndex, int toIndex) {
        return new SubList<>(this, fromIndex, toIndex);
    }

  	// 工具方法
  	// 检查index合法性
    private void rangeCheck(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
  
		// 检查index合法性（添加元素）
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
  
		// 越界信息
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
  
		// 检查是否并发修改父列表
    private void checkForComodification() {
        if (this.modCount != l.modCount)
            throw new ConcurrentModificationException();
    }
}

// 对SubList的简单封装，实现RandomAccess标志接口
class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }
		// 获取当前视图的视图
    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}