Java 集合深入理解 （三） ：java.util 包的集合中 fail-fast 快速失败机制

Java 集合深入理解 （一）： ArrayList

简介:
Vector是java集合框架在现在看来比较古老，和arraylist一样同样维护一个数组, 但通过加synchronized来保证线程安全，看起来源码和arraylist基本相同，还是有研究的价值，废话不多说先从注释开始理解

/**
 * The {@code Vector} class implements a growable array of
 * objects. Like an array, it contains components that can be
 * accessed using an integer index. However, the size of a
 * {@code Vector} can grow or shrink as needed to accommodate
 * adding and removing items after the {@code Vector} has been created.
 *
 * <p>Each vector tries to optimize storage management by maintaining a
 * {@code capacity} and a {@code capacityIncrement}. The
 * {@code capacity} is always at least as large as the vector
 * size; it is usually larger because as components are added to the
 * vector, the vector's storage increases in chunks the size of
 * {@code capacityIncrement}. An application can increase the
 * capacity of a vector before inserting a large number of
 * components; this reduces the amount of incremental reallocation.
 *
 * <p><a name="fail-fast">
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em></a>:
 * if the vector is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.  The {@link Enumeration Enumerations} returned by
 * the {@link #elements() elements} method are <em>not</em> fail-fast.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 *
 * <p>As of the Java 2 platform v1.2, this class was retrofitted to
 * implement the {@link List} interface, making it a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.  Unlike the new collection
 * implementations, {@code Vector} is synchronized.  If a thread-safe
 * implementation is not needed, it is recommended to use {@link
 * ArrayList} in place of {@code Vector}.
 *
 * @author  Lee Boynton
 * @author  Jonathan Payne
 * @see Collection
 * @see LinkedList
 * @since   JDK1.0
 */

翻译后

/**
*{@code Vector}类实现了一个可增长的对象。与数组一样，它包含可以使用整数索引访问。然而，一个
*{@code Vector}可以根据需要增长或收缩以适应在创建{@code Vector}之后添加和删除项。<p>每个向量都试图通过维护
*{@code capacity}和{@code capacityIncrement}。这个{@code capacity}总是至少和向量一样大尺寸；它通常更大，因为组件添加到
*向量，向量的存储以块的大小增加{@code capacityIncrement}。应用程序可以提高
*在插入大量数据之前向量的容量部件；这减少了增量再分配的数量。
*<p><a name=“fail fast”>java中的fail-fast(快速失败)机制这个类的{@link#iterator（）iterator}和
*{@link#lisiterator（int）lisiterator}方法是快速失败的：如果在迭代器运行后的任何时候对向量进行了结构修改
*以任何方式创建，除了通过迭代器自己的{@link ListIterator#remove（）remove}或
*{@link ListIterator#add（Object）add}方法，迭代器将抛出{@link ConcurrentModificationException}。因此，面对
*并发修改时，迭代器会快速而干净地失败，而不是而不是冒着武断的、不确定的行为
*未来的时间。返回的{@link Enumerations}{@link#elements（）elements}方法是<em>not</em>fail fast。
*<p>请注意，不能保证迭代器的快速失败行为一般说来，不可能在未来作出任何硬性保证
*存在未同步的并发修改。失败快速迭代器
*尽最大努力抛出{@code ConcurrentModificationException}。
*因此，编写依赖于此的程序是错误的其正确性例外：<i>迭代器的快速失败行为
*应仅用于检测错误。</i>
*<p>从Java2平台v1.2开始，这个类被改进为
*实现{@link List}接口，使其成为
*<a href=“{@docRoot}/./technotes/guides/collections/index.html”>
*Java集合框架</a>。与新系列不同
*实现时，{@code Vector}是同步的。如果线程安全
*不需要实现，建议使用{@link
*ArrayList}代替{@code Vector}。
 * @author  Lee Boynton
 * @author  Jonathan Payne
 * @see Collection
 * @see LinkedList
 * @since   JDK1.0
 */

整段注释翻译 主要体现在 vector是动态扩容、并且为保证数据的安全使用快速失败机制，并且建议我们如果线程安全不需要实现，则使用arraylist。

从接口来看，和arraylist的继承和实现是一致的，都是实现AbstractList 并获得一些sublist等方法，以及实现list接口 实现 add方法等

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{

 /**
    *将向量的分量放入其中的数组缓冲区已存储。向量的容量就是这个数组缓冲区的长度，
    *并且至少足够大以包含向量的所有元素。<p>向量中最后一个元素后面的任何数组元素都为空。
     */
    protected Object[] elementData;

   /**
    *此{@code Vector}对象中有效组件的数目。组件{@code elementData[0]}到
    *{@code elementData[elementCount-1]}是实际项。@序列号
    */
    protected int elementCount;

   /**
    *向量容量自动计算的量当其大小大于其容量时递增。如果容量增量小于或等于零，则容量
    *每次需要生长时，载体的体积都会加倍。
    *@序列号 
    */
    protected int capacityIncrement;

下面是arraylist中的成员变量，

 /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

对比arraylist确实是少了很多优化的地方，比如说序列化优化的transient，根据不同构造方法构造不同的数组的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，以及默认长度DEFAULT_CAPACITY 等等；我想应该是作者也应该没优化该类了

  /**
     * 构造一个具有指定初始容量和容量增量。
     *
     * @param   initialCapacity     initialCapacity向量的初始容量
     * @param   capacityIncrement   capacityIncrement容量的增量
     *                              向量溢出时增加
     * @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);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
      /**
     * 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);
    }

就是简单的new了一个数组，指定初始化容量机容量增量 ，直接指定好 10的容量

通过关键方法去理解一下，add方法 ，首先通过 synchronized 关键字去保证多线程下数据的安全，modCount 记录好每次操作次数，在ensureCapacityHelper 中判断容量是否超出，如果超出则直接扩大一倍在来对比数据，扩大一倍还是不够，这选择扩大到增加数据的大小 ，如果小于 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
则直接使用 MAX_VALUE ，最后采用 Arrays.copyOf 进行扩容

 /**
     * 将指定的元素追加到此向量的末尾。
     *
     * @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) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
       /**
		*这实现了ensureCapacity的非同步语义。此类中的同步方法可以在内部调用一种在不增加生产成本的情   况下保证生产能力的方法额外的同步。
     *
     * @see #ensureCapacity(int)
     */
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

删除此向量中指定元素的第一个匹配项如果向量不包含元素，返回是否成功。

   /**
    *删除此向量中指定元素的第一个匹配项如果向量不包含元素，则它是不变的。更多形式上，移除索引i最低的元  素
*{@code（o==null？get（i）==null:o.equals（get（i）））}（如果是这样的话）元素存在）。
    * @param o  要从此向量中删除的元素（如果存在）
     * @return 如果向量包含指定的元素，则为true
     * @since 1.2
     */
    public boolean remove(Object o) {
        return removeElement(o);
    }
   /**
     *删除参数的第一个（索引最低的）匹配项从这个向量。如果在这个向量中找到对象，每个向量中索引大于或等于
     *对象的索引向下移动，使索引变小
     *比以前的价值要高。
     *
     * <p>This method is identical in functionality to the
     * {@link #remove(Object)} method (which is part of the
     * {@link List} interface).
     *
     * @param   obj   the component to be removed
     * @return  {@code true} if the argument was a component of this
     *          vector; {@code false} otherwise.
     */
    public synchronized boolean removeElement(Object obj) {
        modCount++;
        int i = indexOf(obj);
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
    }

java.util集合结构图

最后：vector都是采用synchronized 作关键字通过对象锁来保证数据安全，这部分我解析的比较少，因为大部分和arraylist差不多，并且实现理解更简单，具体还是看arraylist中的解析