Java中主要的List结构

╰+哭是因爲堅強的太久メ 2022-01-15 02:11 182阅读 0赞

# 源码阅读(1)：Java中主要的List结构——概述 #

置顶 2019年06月10日 23:44:49 [说好不能打脸][Link 1] 阅读数 629 标签： [java.util.List][][java.util.Queue][][java.util.Set][] 更多

个人分类： [javaer][]

# 0. 概述 #

典型的数据结构中，对于“表”结构的定义是：在一维空间下元素按照某种逻辑结构进行线性连接排列的数据结构（一对一）。java中集合定义中所包括的数组表（ArrayList）、链表（LinkedList）、各种队列（Queue/Deque）、栈（Stack）等都满足这样的定义。本文及后续的几篇文章中将介绍Java集合结构中关于List接口、Queue接口、Set接口下的重要实现类。注意，关于java.util.concurrent包下对于List接口、Queue接口和Set接口实现类的介绍，将在后续专门的文章进行介绍。

# 1. Java中List性质集合概述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70]  
上图中展示了Java中的java.util.List接口所涉及的部分重要接口和抽象类，以及java.util.List接口在java.util包中的具体实现类。其中以黄色表示的类就是本文将要介绍的java.util包中关于List接口的重要实现类，他们分别是java.util.ArrayList、java.util.LinkedList、java.util.Vector和java.util.Stack。其中Vector和Stack这两个类是继承关系（从上图中就可以看出），他们从JDK1.0开始就被提供出来供开发人员使用，后来又被性能和设计都更好的其它类替换。例如从名字上就可以看出其功能特点是LIFO性质（后进先出）的Stack类，在其自身的文档中（JDK1.7+）已建议开发者优先使用性能更好的ArrayDeque作为替代方案（关于ArrayDeque本专题的后续文章中进行详细介绍）。

但是本专题依然会介绍java.util.Vector类和java.util.Stack类，因为本专题主要是分析Java源代码的设计思想，以便读者将这些设计思想应用到实际的工作中，在本专题的后续文章中还会继续讨论java中的java.util.Set接口、java.util.Deque接口的构建体系。

# 2.java集合List定义中的重要接口意义 #

要理解java.util包中关于java.util.List接口的重要实现类，就首先要搞清楚其上层和下层涉及的主要接口定义和它们定义的功能范围，它们是：java.lang.Iterable接口、java.util.Collection接口、java.util.AbstractList抽象类和java.util.AbstractSequentialList抽象类：

## 2.1. java.lang.Iterable接口 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 1]  
由上图可知，本专题第一部分将介绍的List、Set、Queue性质的集合接口其上层都需要继承java.lang.Iterable接口。根据该接口上自带的注释描述，实现该接口的类可以使用“for each”循环操作语句进行操作处理。但实际上该接口还提供了两个操作方法（JDK 1.8+），forEach(Consumer<? super T> action) 方法和spliterator() 方法。forEach(Consumer<? super T> action) 方法的一般使用方式示例如下：

// 这里创建一个LinkedList，并且使用forEach方法，“消费”其中每一个要素
    new LinkedList<>().forEach(item -> {
      // ...... 这里对每个item元素进行消费
    });
    
    // 再举一个例子，这里的Lists是 google common工具包提供的一个List性质集合相关的处理包
    Lists.newArrayList("value1","value2","value3","value4").forEach(item -> {
      // ...... 这里对每个item元素进行消费
    });

forEach中的Consumer接口定义在java.util.function包下，这个包是JDK1.8中提供的，里面包括了大量函数式编程功能，java.util.function.Consumer接口就是其中之一：表示消费某个对象。

## 2.2. java.util.Spliterator接口 ##

java.lang.Iterable接口中的另一个方法spliterator()，实际上它是“并行迭代器”的定义接口。要说明这个在JDK1.8中提供的“并行迭代器”接口，就要先大致介绍在JDK1.2版本中提供的一个“顺序迭代器” java.util.Iterator（请注意Iterator接口和Iterable接口在字面上的区别）接口。

所谓“顺序迭代器”是可以将集合中的元素基于一定的顺序规则，一个接一个的进行遍历处理。其处理过程基于单核单线程；而“并行迭代器”可以将集合中的元素进行拆解后把他们同时交给多个线程进行处理——也就是说基于多核多线程处理。实际上其内部处理原理涉及到Java同样在JDK1.8开始提供的Fork/Join框架。

## 2.3. java.util.Collection接口 ##

该接口是一个非常关键的接口，如果读者仔细观察java.util包中的源码结构，就会发现该接口并没有一个直接的实现类。凡是实现了该接口的下级类或者接口，都属于Java Collections Framework（Java集合框架）的一部分。

凡是实现了java.util.Collection接口的操作类，代表着这个类中可以按照某种逻辑结构和物理结构，“线性关联”的存储着一组元素的集合。这种线性关联的逻辑结构可能是链表（例如：LinkedList），也可能是固定长度的数组（例如：Vector）；可能向外界的输出的结果是有序的（例如：ArrayList），也可能是无序的（例如：HashSet）；可能是保证了多线程下的操作安全性的（例如：CopyOnWriteArrayList），也可能是不保证多线程下的操作安全性的（例如：ArrayDeque）；

## 2.4. java.util.AbstractList抽象类 ##

**读者一定要知道，在Java中根据List性质的集合在各个维度上表现出来的工作特点，这些List结合可以被分成三种类型：是否支持随机访问的特点进行分类、按照是否具有可修改权限进行分类、按照大小是否可变进行分类**

**Java中List性质的集合，根据是否支持随机访问的特点进行分类的话，当然就包括两种类型：支持随机访问（读）的集合和不支持随机访问（读）的集合**。所谓支持随机访问集合，就是指集合提供相关功能可以对List集合中任意位置的元素进行时间复杂度不改变的定位操作。

请注意**Java中为List定义的“随机访问”的意义和磁盘IO上的“随机读”是有区别的（也有相似性），虽然两者都是在说“可以在某个指定的独立位置读取数据”这个事情，但是由于机械磁盘“旋转”的定位方式或者由于固态磁盘的垃圾标记/回收机制，所以磁盘IO读写中的“随机读”性能是要显著慢于磁盘IO读写中的“顺序读”的；List中定义的“随机访问”需要从算法的“时间复杂度”层面考虑，例如使用数组结构作为List集合基本结构时，其找到一个“指定”位置的时间复杂度为常量O(1)——因为可以直接定位到指定的内存起始位置，并通过偏移量进行最终定位。所以List性质的集合中定义的支持“随机访问”的集合结构，在数据读取性能上远远优于那些不支持“随机访问”的List集合——后续内容介绍ArrayList和LinkedList时，还会详细讲解。**

**另外，如果将List集合按照是否具有可修改权限进行分类，那么List集合分为可修改集合和不可修改集合**。所谓可修改集合是指操作者可以在集合指定的索引位置指定一个存储值；所谓不可修改集合既是操作者只能获取集合指定索引位置的存储值，但是并不能对这个索引位置的值进行替换，使用者也可以获取当前集合的大小，且这个大小的值一定是不可改变的。

**最后，如果将List性质的集合按照大小是否可变进行分类，那么List集合分为大小可变集合和大小不可变集合**，所谓大小不可变集合，既是说一旦这个集合完成了实例化，那么大小就一直固定下来不再变化，而大小可变集合的定义则刚好相反。

针对这三个维度的不同类型定义，开发人员就可以定义出不同操作特性的List集合。**为了保证具有不同分类特点的List集合提供的操作方法符合规范性，也为了减少开发人员针对这些不同分类的List集合的开发工作量，还为了向使用者屏蔽这些分类定义的细节差异，Java为List性质的集合提供了java.util.AbstractList抽象类**。

这样保证了各种具体的List集合的实现类中只需要按照自身情况重写java.util.AbstractList抽象类中的不同方法即可。例如，set(int) 方法其工作特点一定是替换指定索引位的元素值，如果当前List性质的集合不支持修改，则一定会抛出UnsupportedOperationException异常；再例如，具有不可修改性质的List集合，开发人员只需要重写java.util.AbstractList抽象类中的 get(int) 和 size() 方法即可；如果开发人员自行定义一个支持可变大小性质的集合，则只需要重写对add(int , E) 方法和 remove(int) 方法的实现；最后再举例，如果开发人员不需要实现支持随机访问的List集合，则可以优先继承java.util.AbstractSequentialList抽象类。

## 2.5. java.util.RandomAccess接口 ##

java.util.RandomAccess接口是一个标识接口，所谓标识接口是Java中用来定义拥有某一种操作特性、功能特性的方式。Java中有很多标识接口，例如：java.lang.Cloneable接口、java.io.Serializable接口。

上文已经提到，List性质的集合中专门有一组集合实现类是支持“随机访问”特性的，包括java.util.ArrayList、java.util.Vector和java.util.concurrent.CopyOnWriteArrayList集合。java.util.RandomAccess标识接口就是为了向调用者表示这些List性质的集合实现类支持集合元素的随机访问。如下图所示：

![// TODO 这里差一张图][TODO]  
从上图可以看出，List性质的集合java.util.ArrayList、java.util.Vector和java.util.concurrent.CopyOnWriteArrayList，都实现了这个java.util.RandomAccess标识接口，表示自己支持随机访问（读）操作。实现java.util.RandomAccess标识接口的还有很多第三方类库，例如上图中举例就是阿里巴巴开源的JSON分析组件中的JSONArray类。这些实现了java.util.RandomAccess标识接口的List集合在使用时也会被区别对待，如下所示：

/**
     * Replaces all of the elements of the specified list with the specified
     * element. <p>
     * This method runs in linear time.
     * @param  <T> the class of the objects in the list
     * @param  list the list to be filled with the specified element.
     * @param  obj The element with which to fill the specified list.
     * @throws UnsupportedOperationException if the specified list or its
     *         list-iterator does not support the <tt>set</tt> operation.
     */
    public static <T> void fill(List<? super T> list, T obj) {
      int size = list.size();
      // 如果当前集合的大小规模小于FILL_THRESHOLD （25），或者当前List集合支持“随机访问”
      // 那么优先使用索引定位的方式替换集合中的每个位置的对象引用
      if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
        for (int i=0; i<size; i++)
          list.set(i, obj);
      }
      // 否则使用 ListIterator顺序迭代器一次寻找集合的每一个位置，并替换其中的对象引用
      else {
        ListIterator<? super T> itr = list.listIterator();
        for (int i=0; i<size; i++) {
          itr.next();
          itr.set(obj);
        }
      }
    }

如上示例代码来源于java.util.Collections类的fill()方法，该方法主要用于向一个List性质集合填充默认的Object对象。在这个方法中如果当前给定的List性质的集合如果支持RandomAccess随机访问特性，则优先使用for()循环的方式定位并填充集合中的每一个位置；如果当前给定的List性质集合不支持“随机访问”，则是用ListIterator迭代器顺序定位和填充集合中的每一个位置。

为什么会出现这种处理逻辑呢？我们来看看在List集合默认的上层抽象类java.util.AbstractList中的list.listIterator()方法返回的ListIterator迭代器是如何实现next()方法的。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
      // ......
      // Collections类的fill()方法，就是调用的该方法
      public ListIterator<E> listIterator() {
        return listIterator(0);
      }
      public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);
        return new ListItr(index);
      }
      // ......
      // AbstractList类中并不会实现get()方法，而是将该方法的实现交给具体的实现类。
      // 也就是说不同的实现类中会有不同的get()方法的实现过程。
      abstract public E get(int index);
      // ......
    
      // ListItr类是Itr的子类，next()方法就是在后者中进行定义的
      private class Itr implements Iterator<E> { 
        // ......
        // next方法的调用过程在这里
        public E next() { 
          checkForComodification();
          try { 
            // 关于cursor变量和lastRet 变量在迭代器中的意义
            // 在后文会进行介绍，这里我们主要关注本方法内容中的get()方法。
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
          } catch (IndexOutOfBoundsException e) { 
            checkForComodification();
            throw new NoSuchElementException();
          } 
        }
        // ......
      }
    }

在AbstractList.Itr类的next()方法中，我们主要关注其中的get()方法。并且在上面的代码片段上已经说明，不同实现原理下的具体List集合类对于get()方法的实现是不一样的，那么我们来看一下两个典型的List集合ArrayList和LinkedList对于get()方法的实现。

*  首先来看一下LinkedList中对于get()方法的实现：

public E get(int index) {
      // 后续文章会说明checkElementIndex()方法，在本文中的内容中，它并不重要
      checkElementIndex(index);
      return node(index).item;
    }
    
    Node<E> node(int index) {
      // 如果给定的index小于当前集合大小的一半，那么从连表的头部开始寻找
      // 否则就从连表的尾部开始寻找
      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;
      }
    }

由于LinkedList是一个双向链表，要寻找链表中的某一个位置上的元素，就只能从头部或者从尾部一个一个的找。如下图所示：

![// TODO 这里差一张图][TODO 1]

这样我们就可以复盘java.util.Collections类的fill()方法中，如何进行LinkedList中的元素填充了，如下图所示：  
![// TODO 这里有差一张图][TODO 2]

*  然后我们再来看一下ArrayList中对于get()方法的实现：

// ArrayLit类中的elementData变量就是这个集合的数组形式表示
    transient Object[] elementData;
    
    public E get(int index) {
      // rangeCheck方法后文会进行讲解，但和这里讲解的内容关联不大
      rangeCheck(index);
      // 通过elementData方法，直接定位数组中的元素
      // 保证了对“随机访问”特性的支持，对算法复杂度O(1)的支持
      return elementData(index);
    }
    
    E elementData(int index) {
      return (E) elementData[index];
    }

由于ArrayList本质上是一个数组，要寻找到数组中的某一个位置上的元素并不用挨个元素意义进行遍历。JVM会根据对象在内存中的起始位置和数组位置的偏移量直接找到这个元素。按照这样的原理，我们同样可以复盘java.util.Collections类的fill()方法中，如何进行ArrayList中的元素填充了，如下图所示：

![支持“随机访问”][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 2]

以上示例的分析中，本文将支持“随机访问”和不支持“随机访问”的具体List集合在访问性能上的工作差异做了详细标识，实际上典型的ArrayList和LinkedList的性能差别还不仅仅在于此处，后续文章还会做更详细说明。另外，在本文第1小节给出的List集成体系简图中，还出现了java.util.Queue接口和java.util.Deque接口，这两个接口代表Java集合体系中另外一块和List集合体系平行的集合体系，在后续文章中也将进行详细介绍。

========  
(接后文《[源码阅读(2)：Java中主要的List结构——ArrayList和Vector][2_Java_List_ArrayList_Vector]》)

================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================

# 源码阅读(2)：Java中主要的List结构——Vector集合 #

置顶 2019年06月10日 23:47:42 [说好不能打脸][Link 1] 阅读数 415 标签： [java.util.Vector][][RandomAccess][][随机访问][Link 2] 更多

个人分类： [javaer][]

（接上文《[源码阅读(1)：Java中主要的List结构——概述][1_Java_List]》）

# 3.java.util.Vector结构解析 #

java.util.Vector类是从Java较早版本就开始提供的List形式的集合结构（从JDK 1.0开始），其主要的继承体系如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 3]  
从上图我们可知，Vector是支持“随机访问”特性的，该特性在上一篇文章中已经进行了讲解，这里就不再赘述了。如果严格描述Vector的特性的话，那么Vector是一个支持集合元素读写、且大小可变、且线程安全、最后还支持“随机访问”特性的List性质的集合。下面我们就对Vector类中的典型操作进行详细介绍，首先我们需要详细描述的是存在于Vector类中和其上级AbstractList类中的重要变量信息：

// 向量
    public class Vector<E>
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
      // ......
      /**
       * 这个数组就是用来存储Vector中每个元素的。其数组大小可以扩展，并且数组的最小值都足以存储下已写入Vector集合的每一个元素
       * 数组的大小也可以大于当前已写入Vector集合的所有元素的大小。如果是那样的话，那么多出来的数组位置上的值都为null
       * 该数组的初始化大小由构造函数中的initialCapacity参数决定，initialCapacity参数的默认大小为10
       */
      protected Object[] elementData;
      /**
       * 这个变量用于记录当前Vector集合中真实的元素数量，在后续的源代码阅读中会发现这个值在整个操作过程中更多起到的是验证作用。
       * 例如判断元素的位置是否超过了最大位置。
       */
      protected int elementCount;
      /**
       * Vector集合支持大小扩容，实际上也就是对其中的elementData进行“变长”操作。
       * capacityIncrement变量表示每次扩容的大小，如果capacityIncrement的值小于等于0，那么扩容大小为其当前大小的一倍
       */
      protected int capacityIncrement;
      // ......
    }

通过对以上三个重要变量的描述，我们可以大致知晓Vector集合的基本结构，其包括了一个数组，一个指向当前数组的可验证“边界”，以及一个数组扩容的参考值，如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 4]  
elementCount变量的在Vector集合中非常重要，它在Vector集合进行addXXXX()、removeXXXX()性质的操作时都会发生变化。elementCount变量的值可能小于elementData数组的容量大小（capacity()方法可获取当前数组的容量大小），也可能和elementData数组的容量大小相等——当整个elementData数组的每一个索引位置都已经设定了元素（元素也可以设置为null）。

另外一个已知的知识点是，Java中的数组是内存中的一个连续地址，一旦完成了初始化其大小不可变化。那么如果理解上文中提到的“变长”了，我们将在下文中专门讲解Vector集合的扩容操作。搞清楚了Vector集合中的重要变量信息后，我们就可以介绍Vector类中的典型操作方法了。

## 3.1、Vector集合的扩容操作 ##

上文已经描述过Vector集合支持扩容操作，说得具体一点就是支持Vector类中用于真实存储数据的“elementData”数组的大小允许变化，再说得根本一点，就是允许重新为“elementData”数组变量指定新的地址引用。

## 3.1.1、什么时候扩容？ ##

Vector集合在两种情况下需要进行扩容。首先Vector集合在初始化时会进行扩容，其“elementData”数组变量将从Null第一次指向一个新的数组地址；其次当Vector集合中“elementCount”代表的元素数量将要超出“elementData”数组的最大容量capacity时，也会进行扩容操作，这时“elementData”数组中的元素将会被“拷贝”到另一个更大的数组中，并且“elementData”数组变量将从新指向后者。

*  初始化Vector集合时的详细扩容过程：

首先关注以下Vector集合的构造函数：

/**
     * Constructs an empty vector with the specified initial capacity and capacity increment.
     * @param   initialCapacity     the initial capacity of the vector
     * @param   capacityIncrement   the amount by which the capacity is increased when the vector overflows
     * @throws IllegalArgumentException if the specified initial capacity is negative
     */
    public Vector(int initialCapacity, int capacityIncrement) {
    	super();
    	if (initialCapacity < 0)
    	  throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    	// elementData 数组从null被重新指定了一个数组的地址，数组大小默认为10；
    	this.elementData = new Object[initialCapacity];
    	this.capacityIncrement = capacityIncrement;
    }
    /**
     * Constructs an empty vector with the specified initial capacity and
     * with its capacity increment equal to zero.
     * @param   initialCapacity   the initial capacity of the vector
     * @throws IllegalArgumentException if the specified initial capacity is negative
     */
    public Vector(int initialCapacity) {
    	this(initialCapacity, 0);
    }
    /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is zero.
     */
    public Vector() {
    	this(10);
    }

以上三个构造函数的执行内容和关联关系一目了然，不需要在做过多介绍。通过以上的代码片段我们知道，如果没有在Vector集合初始化时指定集合的初始化容量（initialCapacity），那么初始化容量将设定为10；如果没有在Vector集合初始化时指定扩容增量（capacityIncrement），那么扩容增量的值将被设定为0；从上文中的介绍我们还可以知道，一旦扩容增量（capacityIncrement）被设置成了0，那么随后进行的每次扩容中，“elementData”数组的大小都会变为当前大小的一倍，也就是说说 10->20->40->80…………以此类推。

*  当前Vector集合的数据总量将超出数组容量限制时也会进行扩容：

我们来看一下的判定方法：

/**
     * 此私有方法用于在进行各种会引起容器内数据量发生变化的操作前，进行容器容量检查。
     * Vector集合是一个线程安全的集合（虽然锁性能不高），也就是说以上提到的各种“可能引起容器内数据量发生变化”的操作都是通过
     * synchronized关键字进行了线程安全控制的，所以此私有方法就无需再加synchronized关键字了，以便减少性能开销
     */
    private void ensureCapacityHelper(int minCapacity) {
      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
        grow(minCapacity);
    }

ensureCapacityHelper方法中的内容很简单：如果当前调用该私有方法时，入参所传入的最小容量（minCapacity）如果大于当前Vector集合elementData数组的大小，则进行扩容——调用grow(int)方法。而ensureCapacityHelper方法的调用广泛存在于那些“可能引起Vector集合内数据量发生变化”的方法中，例如：setSize()方法、insertElementAt()方法、addElement()方法、add()方法、addAll()方法等等，以及那些主动寻求容量验证的方法：ensureCapacity()方法。

## 3.1.2、怎样进行扩容？ ##

当Vector集合进行初始化时的扩容操作很简单，实际上就是elementData数组的初始化过程；这里我们主要讲解grow(int)方法，也就是上文提到的ensureCapacityHelper()方法中调用的grow(int)方法，首先上源代码：

private void grow(int minCapacity) {
      // 将“扩容”操作前当前elementData数组的大小保存下来（保存成oldCapacity），后面可能用到。
      int oldCapacity = elementData.length;
      // 这句代码非常关键，确定新的容量有两种情况：
      // 1、如果当前设定了有效的扩容大小（在Vector集合初始化时可以设定），那么新的容量 = 老的容量 + 设定的扩容值
      // 2、如果当前没有设定有效的扩容大小（既是capacityIncrement的值 <= 0 ），那么新的容量 = 老的容量 * 2
      int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
      // 如果当前新的容量 小于 grow方法调用时传入的最小容量，则新的容量以传入的最小容量为准
      if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
      // 如果当前新的容量 大于 MAX_ARRAY_SIZE常量，这个常量为2147483639[0x7ffffff7]
      // 那么调用hugeCapacity()方法确认新的容量，
      if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
      
      // 最后使用Arrays工具类提供的copyOf方法完成真实的扩容过程
      elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    // 该私有方法的名字叫做：巨大的容量.......
    // 好吧，如果真的在Vector集合中管理这么大一个数组，那真的是非常危险的。
    private static int hugeCapacity(int minCapacity) {
      if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
      // 如果当前方法调用传入的minCapacity的值，大于常量2147483639，那么取Java中整数类型的最大值2147483647
      // 否则就取MAX_ARRAY_SIZE常量的值2147483639
      return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

以上的方法注释已经把每一句源代码描述得很清楚了，这里重点说明一下Arrays.copyOf()方法和hugeCapacity()方法。

*  Arrays.copyOf(T\[\] original, int newLength)方法：该方法是一个工具性质的方法，其方法意义为复制指定数组（original）为一个新的数组对象，后者的长度为给定的新长度（newLength）。按照这样的描述，根据给定的新长度（newLength）就会出现两种不同的情况：第一种情况是新长度（newLength）小于指定的数组（original）的原始长度，那么无法复制的数组部分将会被阶段；第二种情况是新长度（newLength）大于等于指定的数组（original）的原始长度，这时原始数组中的所有元素对象（的引用地址）将依据原来的索引位置被依次复制到新的数组中，多出来空余的部分将被填充null值。如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 5]  
注意上图所代表的过程描述中，并不包括新长度（newLength）参数无效的情况，例如当newLength为负数时，该方法会抛出java.lang.NegativeArraySizeException异常。那么有的读者会问当newLength为0时会出现的情况，这种情况满足以上描述的第一种情况的输出——没有任何元素可以进行填充，当然就是输出一个空数组

上图所代表的过程描述中，也不包括类似int\[\]、long\[\]、float\[\]等java基础类型数组进行复制的场景，在这些基础类型数组的复制过程中，新数组中多余的位置将填充这个基础类型的默认值，例如int\[\]数组的复制过程中，新数组的多余的位置将被填充“0”。

*  hugeCapacity()方法：  
    该方法中出现了两个关键的常量MAX\_ARRAY\_SIZE和MAX\_VALUE，MAX\_ARRAY\_SIZE的大小为2147483639（7FFF FFF7），表示支持的最大数组大小；MAX\_VALUE的大小为2147483647（7FFF FFFF），标识32位int类型所代表的最大整数值。那么按照上文源代码的意义，Vector集合最大支持的数组容量就是2147483647。

## 3.2、add(E) 方法 ##

add(E)方法的意义是在Vector集合的尾部增加一个新的元素，这个尾部并不是以当前Vector集合中elementData数组的长度决定，而是以Vector集合中当前元素数量elementCount来决定的——elementData的长度永远大于或者等于elementCount。

/**
     * Appends the specified element to the end of this Vector.
     * @param e element to be appended to this Vector
     * @return {@code true} (as specified by {@link Collection#add})
     * @since 1.2
     */
    public synchronized boolean add(E e) {
      // 该变量来自于Vector集合的父类AbstractList，后文将进行详细介绍
      // 目前可以单纯的理解为当前Vector集合被操作的次数。
      modCount++;
      // 该方法来确认是否进行elementData数组的“扩容”操作，并在满足条件时进行扩容。
      ensureCapacityHelper(elementCount + 1);
      // 在当前数组的elementCount位置之后，添加新的对象e
      elementData[elementCount++] = e;
      return true;
    }

那么整个add方法的操作过程实际上就分为两种情况，第一种情况当elementCount代表的集合中元素数量小于当前elementData数组大小时，这时不必进行elementData数组的“扩容”，直接在elementData数组的第elementCount的位置增加新的数据即可；当elementCount代表的集合中元素数量大于或者等于当前elementData数组大小时，就需要先进行elementData数组的“扩容”操作，再进行新数据在elementCount位置的添加操作。

## 3.3、set(int , E) 方法 ##

该方法在指定的索引位置设定指定的元素，指定的元素可以为null。该方法有两个参数第一个参数为int类型的索引位置，第二参数为需要在这个索引位置设定的新的元数值。该方法有几个关键点：

*  可指定的索引位置的有效范围并不是当前Vector集合中elementData数组的大小，而是当前Vector集合中存在的数据数量elementCount——这个elementCount数据值在Vector集合中的另一个表达就是Vector集合的大小（Vector集合的size值）
 *  该方法有一个返回值，这个返回值将向调用者返回指定索引位置上变更之前的值。

/**
     * Replaces the element at the specified position in this Vector with the
     * specified element.
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @since 1.2
     */
    public synchronized E set(int index, E element) {
      // 如果当指定的索引位置大于等于当前集合的数据量，则抛出超界异常
      if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
      
      // 原始值将在替换操作之前被保存下来，以便进行返回
      E oldValue = elementData(index);
      // 将elementData数组的指定位置的数据值替换成新的值
      elementData[index] = element;
      return oldValue;
    }

## 3.4、removeElementAt(int) 方法 ##

该方法用于移除Vector集合中elementData数组指定位置的数据值，并且改变其索引位置的指向。在操作者看来这个操作可以成功移除索引位置X上的元素（X < elementCount），并且操作成功后，操作者虽然依旧可以使用索引位置X取得数据（X < elementCount），但是之后取得的值将是“紧邻”的数据。如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 6]  
上图展示了removeElementAt(int) 方法的运行实质：既是以当前指定索引位置为几点，将后续元素位置向前一次移动一个索引位置，请看该方法的源代码：

public synchronized void removeElementAt(int index) {
      modCount++;
      if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
      }
      else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
      }
      // 以上代码中两种会报错的情况就不做详细分析了，其意义就是当index的位置 < 0 或者大于等于当前elementData数组的大小时抛出异常
      // =========
      // j 代表elementData数组将要移动部分的长度
      int j = elementCount - index - 1;
      // 什么时候 j == 0 呢？就是index指向当前elementData数组的最后一个索引位置时
      if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
      }
      // 元数数量 - 1
      elementCount--;
      // 这句代码将着重进行说明
      elementData[elementCount] = null; /* to let gc do its work */
    }

首先来描述一下以上代码中的System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法，该方法是一种JNI native方法，是JDK提供的进行两个数组中元素复制的性能最快的方法。其参数意义描述如下：

*  src：该参数只能传入数组，表示当前进行数组元素复制的来源
 *  srcPos：该参数描述源数组中进行复制操作时的起始元素位置
 *  dest：该参数同样只能传入数组，标识当前进行数组元素复制的目标数组
 *  destPos：该参数描述目标数组中进行复制操作时的起始元素位置
 *  length：该参数指定进行复制的长度。

那么这样，以上代码段落中使用System.arraycopy方法的意图就很好理解了，如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 7]  
上图所示，虽然完成了数组自身的元素移动，但这时数组最后一个元素的值并没有改变，所以需要人工进行数组中元素值的减少，并手动设置最后一个位置上的元素为null。所以会出现上文中源代码的内容：

public synchronized void removeElementAt(int index) {
      // ......
      elementCount--;
      elementData[elementCount] = null; /* to let gc do its work */
      // ......
    }

====================

[Link 1]: https://me.csdn.net/yinwenjie
[java.util.List]: https://so.csdn.net/so/search/s.do?q=java.util.List&t=blog
[java.util.Queue]: https://so.csdn.net/so/search/s.do?q=java.util.Queue&t=blog
[java.util.Set]: https://so.csdn.net/so/search/s.do?q=java.util.Set&t=blog
[javaer]: https://blog.csdn.net/yinwenjie/article/category/187173
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70]: /images/20220114/77ebc348305f4d8fb3eef1a077bd0285.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 1]: /images/20220114/2e81a94aa7d94438a7ff0b3f349dbc7b.png
[TODO]: /images/20220114/45a21083f803489ea68e2a9d41a822cf.png
[TODO 1]: /images/20220114/5b916680b17e48e7ab06bb5004a04703.png
[TODO 2]: /images/20220114/b03cee31b36f43ca9ddf7a62106ff37d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 2]: /images/20220114/e40c43a150014c9f9dd1922f33f42ad4.png
[2_Java_List_ArrayList_Vector]: https://blog.csdn.net/yinwenjie/article/details/90581835
[java.util.Vector]: https://so.csdn.net/so/search/s.do?q=java.util.Vector&t=blog
[RandomAccess]: https://so.csdn.net/so/search/s.do?q=RandomAccess&t=blog
[Link 2]: https://so.csdn.net/so/search/s.do?q=%E9%9A%8F%E6%9C%BA%E8%AE%BF%E9%97%AE&t=blog
[1_Java_List]: https://blog.csdn.net/yinwenjie/article/details/90292422
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 3]: /images/20220114/08053029df534fdf9c53d724bf609cca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 4]: /images/20220114/c37c7486334d4939be53446749cffdc1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 5]: /images/20220114/dcacba26fb0f48c09d270795647d0bc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 6]: /images/20220114/2c69f6bb7acc4fa89623f9e642813b6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpbndlbmppZQ_size_16_color_FFFFFF_t_70 7]: /images/20220114/b2f80cc3c6d749d98cb109b57268ab9c.png