Vector集合源码分析

Vector集合源码分析

内容如有错误或者其他需要注意的知识点，欢迎指正或者探讨补充，共同进步。

一、字段分析

//用于存储该集合中的所有数据对象，所以是基于数组实现的
protected Object[] elementData;//用于记录当前集合中的数据量
protected int elementCount;//在进行扩容操作时，每次扩容的大小。如果为0，则按每次两倍的容量进行扩容（即增加当前容量的一倍）
protected int capacityIncrement;/*
**该字段继承自父类AbstractList，用于记录对列表结构进行修改的次数。
**当通过迭代器遍历列表时，迭代器会记录当前迭代的列表结构版本号，即初始时的 modCount 值。
**每次调用 next() 方法时，迭代器都会检查当前的 modCount 值是否与初始时的版本号一致，如果不一致
**则说明列表在迭代期间被修改过，就会抛出 ConcurrentModificationException 异常。
**使用 modCount 可以在迭代过程中及时检测到列表结构的修改，从而确保迭代器遍历的安全性和可靠性。
*/
protected transient int modCount = 0;

---

二、方法分析

• 添加元素 方法，是线程安全的方法。

  //向已插入元素的后一位插入元素
  public synchronized boolean add(E e) {//记录当前迭代的列表结构版本号，防止迭代过程中被别人也操作修改了，导致非线程安全问题。modCount++;//判断是否需要扩容ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}//这时候的minCapacity 值为当前元素数量 + 1
  private void ensureCapacityHelper(int minCapacity) {// 判断当前需要的容量大小 是否大于 数组的大小，大则需要扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}//当前 minCapacity = 当前元素数量 + 1 即 elementcount + 1 
  private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//这一步很关键，我们在Vector初始化的时候如果传入了参数capacityIncrement 且大于0，//则在原先的容量基础上+capacityIncrement ，如果没传或者为0，则扩容为原先数组容量的两倍。int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);//如果扩容后溢出了，则就只在原先容量上+1，其实还是有溢出的可能，所以我们操作该集合时，要注意该可能性                                 if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//这是后虽然还没溢出，但也几乎要溢出了，因为 MAX_ARRAY_SIZE  值为Integer.MAX_VALUE - 8，如果比MAX_ARRAY_SIZE  还打，则扩容为Integer.MAX_VALUE,否则为MAX_ARRAY_SIZEif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//用扩容后的容量创建新的数组，并将原数组数据迁移过来。//1。如果扩容后的数组塞不满之，后面补充null，或基本数据类型的默认值，比如int 默认0。//2。如果新的容量比原型容量还行，则进行阶段。elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}//向数组的指定位置插入元素
  public void add(int index, E element) {insertElementAt(element, index);}
  //同样是线程安全的
  public synchronized void insertElementAt(E obj, int index) {modCount++;if (index > elementCount) {throw new ArrayIndexOutOfBoundsException(index+ " > " + elementCount);}//确定是否扩容，上面分析过了ensureCapacityHelper(elementCount + 1);//生成扩容后的新数组System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);elementData[index] = obj;//每次添加元素+1，这个值就是实际的元素数量，我们调用集合类的size（）方法时，返回的就是这个值。elementCount++;}

• 获取元素 方法：根据索引获取值

  public synchronized E get(int index) {//越界了if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);//就是返回该数组下标位置的元素，没啥好说的。return elementData(index);}@SuppressWarnings("unchecked")
  E elementData(int index) {return (E) elementData[index];
  }
  

• 扩容方法：介绍添加元素方法时说过了。

• 移除元素方法：可以根据下标位置移除元素，也可更具元素值移除元素。

  //根据元素值删除元素
  public boolean remove(Object o) {return removeElement(o);}
  //同样是线程安全的
  public synchronized boolean removeElement(Object obj) {// 修改版本号，防止正在被迭代，导致非线程安全问题。modCount++;//确定元素下下标位置int i = indexOf(obj);if (i >= 0) {removeElementAt(i);return true;}return false;}
  //确定元素o下标位置
  public int indexOf(Object o) {//为啥传0呢，因为要在一个数组里面找指定值的元素，当然是从该数组下标0开始往后遍历啦。return indexOf(o, 0);}//从下标index开始，查找元素o
  public synchronized int indexOf(Object o, int index) {//从这里也可看出，Vector 集合支持null的存储的。//同时我们也可看出，如果集合中存在值相同（基本数据类型），或者同一对象（非基本类型），会将靠索引小的删除掉，而后面的不会删除。这点操作时要注意，比如我们往 Vector<Integer> 添加两个形同对象，在掉remove（该对象）,只能删除一个，如下图测试所示。if (o == null) {for (int i = index ; i < elementCount ; i++)if (elementData[i]==null)return i;} else {for (int i = index ; i < eleme0ntCount ; i++)if (o.equals(elementData[i]))return i;}return -1;}//获取到元素下标后，更具下标移除元素
  public synchronized void removeElementAt(int index) {//生成新的版本号modCount++;//越界if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);}//越界else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);}//计算要删除元素后面还有多少个元素int j = elementCount - index - 1;if (j > 0) {//将元素通过赋值前移System.arraycopy(elementData, index + 1, elementData, index, j);}//元素数量-1elementCount--;//如果是最后一个元素，或是是已经调用 System.arraycopy迁移后的数组，则将最后以为设为nullelementData[elementCount] = null; /* to let gc do its work */}//根据索引位置删除元素
  public synchronized E remove(int index) {//版本号+1modCount++;//判断是都越界if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);//获取要删除的元素值    E oldValue = elementData(index);//需要移动的元素数量，就是你讲index位置的元素删了，那这个元素后院的所有的元素都要前移，这个值就是需要//移动的元素数量即index后面元素的数量int numMoved = elementCount - index - 1;//判断index后面是否有值if (numMoved > 0)//将要移动的元素前移，其实是吧那个要删除的元素覆盖了从而达到了删除元素的目的。System.arraycopy(elementData, index+1, elementData, index,numMoved);为什么要删除末尾元素呢，因为如果index 是最后以为元素，那么就不会触发元素前移，所以这里//多一步，将末尾元素设置为null，就是为了处理这一特殊情况。所以如果index 后面有值，这一步是//多余的，末尾已经是null了。                     elementData[--elementCount] = null; // Let gc do its work//返回被删除的元素元素值return oldValue;
  }

  

• 迭代设计：内部类，实现了 Iterator。

  • 但是Vector 提供了两种内部类用来实现 Iterator，分别是 Itr 和 ListItr，两种有所区别，使用场景也有所不同
  • Itr：实现基本的迭代功能，通过维护一个 游标cursor 来遍历Vector的元素，不支持迭代过程中对Vector进行修改（增加或者删除元素），否则会抛出ConcurrentModificationException 异常。
  • 适用于只需要遍历访问Vector元素而不进行修改的场景。

public synchronized Iterator<E> iterator() {return new Itr();}
private class Itr implements Iterator<E> {//游标，记录元素访问的位置，需要注意的是，游标记录的是下一次会访问的元素位置，而不是最后已经访问过的元素，比如：//初始化时，游标值是0，调用next是，由于游标是0，所以会返回0下标位置的元素，然后游标+1，即下一次元素访问下标。int cursor;       // index of next element to return//记录上一次已经访问的元素的位置，比如我们这次访问下标1，则lastRet 记录1，而cursor会记录2（即下一次回访问的位置）。int lastRet = -1; // index of last element returned; -1 if no such//记录版本号，记录在初始化迭代器时，当时的Vector的版本号。//前面也介绍过，在对Vector集合进行添加或者删除元素时，会执行 modCount ++；//在迭代的过程中，或比对 modCount  和 expectedModCount 的值，//从而判断迭代过程中Vector集合是否被修改过，修改过则抛出ConcurrentModificationException 异常。int expectedModCount = modCount;//判断下一步迭代是否还有元素，很简单，就是用当前迭代的位置（即游标的值） 和 元素的数量比较即可。public boolean hasNext() {// Racy but within spec, since modifications are checked// within or after synchronization in next/previousreturn cursor != elementCount;}//获取下一个元素，线程安全的，锁的是Vector.class 对象，保证在创建多个迭代器对象时，也是线程安全的。public E next() {synchronized (Vector.this) {//就是判断是Vector集合是否被修改过，就是用的版本号modCount 和 初始化时记录的 expectedModCount 比较，//判断是否发生变化，变化了则被修改过。下边也贴出了源码，很简单。checkForComodification();//当前要访问的元素位置，呼应前面讲的，cursor记录的是要访问元素的位置。int i = cursor;//如果说当前位置是最后一个元素位置了，即后面没值了，会抛出异常，这也告诉我们，在调用next（）方法是，最好想用//hasNext（）判断下，防止一直掉next（），遍历到末尾了从而抛出异常。下面贴出了测试情况。if (i >= elementCount)throw new NoSuchElementException();//游标+1，即下一次要访问元素的位置。cursor = i + 1;//记录本次访问的元素下标位置，并返回该位置的元素。return elementData(lastRet = i);}}//移除元素，通过代码可以知道，这里有一个细节需要注意：移除的并不是最末尾的那个元素，而是我们已经遍历过的//所有元素的末尾那个元素。比如用来存储数据的数组elementData[5],有五个元素，而我们在调用next（）迭代访问元素的//过程中，访问到了index = 2，则游标cursor = 3，lastRef = 2，那么我们调用remove时，//其实删除的是index = 2位置的元素，无图说。。下面贴出来了测试结果。public void remove() {//判断参数是否异常if (lastRet == -1)throw new IllegalStateException();synchronized (Vector.this) {//判断迭代过程中Vector是否被修改过checkForComodification();//删除 lastRec 下标位置的元素，该方法上面分析过了，删除之后，后面的元素前移。Vector.this.remove(lastRet);//更新版本号，这里有点奇怪，按理说我们初始化开始时版本号是多少，我们在操作迭代器的整个过程中，//版本应该是不能改变的,所以这里按理说应该是一直相等的，为啥要重新赋值呢？？？//所以也可以看出，Vector 的删除过程并不是100% 保证集合不被修改的。//即在checkForComodification（）执行完之后正好对集合发生修改，不会抛出错误，而且迭代器也不会抛出异常。//这里和next（）迭代不同了，next（）要求整个迭代过程都不能修改Vector集合。//个人思考这里为啥这样：//	可能和方法的目的不同有关，next（）迭代目的是获取所有元素，我们希望获取创建迭代器那一时刻的元素，//	关心的是元素的值，肯定不希望我获取这些元素过程中还有别人来修改。//	而remove（）只是删除，对于元素值并不关心的。只要达到删除的目的即可。// 所以因为这里，也可能导致next（）获取的值和我们刚刚开始创建迭代器时集合的值发生变化。如何做呢？//		我们先调用next（）获取值，在调用remove删除，并且删除时好巧不巧在checkForComodification（）//		执行后,修改了集合，后面在调用next（）也不会报错，正常迭代，但是集合已经被修改了。。。//总之：该迭代器并不能100%保证迭代过程中，集合不被修改的（即调用next，又调用remove），并且不抛出异常。//但是如果只调用next（）确实可以保证。expectedModCount = modCount;}//更新游标，因为后面元素都往前移了cursor = lastRet;//可以看出迭代器不能连续调用两次，否则抛出异常lastRet = -1;}//函数接口作为参数，可以在遍历过程中，执行该函数@Overridepublic void forEachRemaining(Consumer<? super E> action) {//不能为空Objects.requireNonNull(action);synchronized (Vector.this) {final int size = elementCount;int i = cursor;if (i >= size) {return;}@SuppressWarnings("unchecked")final E[] elementData = (E[]) Vector.this.elementData;if (i >= elementData.length) {throw new ConcurrentModificationException();}//遍历参数，让每一个元素都执行action的方法，同时保证执行过程中，集合不能被修改while (i != size && modCount == expectedModCount) {action.accept(elementData[i++]);}// update once at end of iteration to reduce heap write traffic//更新游标到末尾，其实就是遍历完了，五元素可编列。//举个例子：比如elementData[5]，这时，cursor，就是5，lastRef = 4；cursor = i;lastRet = i - 1;//最后再次检查集合是否被修改过。checkForComodification();}}//检查集合版本和迭代器版本是相同，从而判断迭代过程中，集合有没有被修改。final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}//判断迭代过程中，Vector集合是否被修改，修改了则抛出 ConcurrentModificationException 异常。
final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}
//返回该索引位置的元素
E elementData(int index) {return (E) elementData[index];}

• ListItr：继承自Itr，实现了ListIterator。
  • 相比Itr，提供了额外的方法功能。并且支持在迭代的过程中对 Vector进行修改（增加、删除元素），不会抛出ConcurrentModificationException异常。
  • 通过维护一个 游标cursor 和一个最后访问元素的索引 lastRet 来遍历和修改 Vector 中的元素。
  • 适用于访问 Vector 元素并且对其进行修改的场景。

final class ListItr extends Itr implements ListIterator<E> {//初始化迭代器，这里和Itr迭代器不同。//Itr迭代只能从头开始迭代//而ListItr可以从指定位置开始迭代ListItr(int index) {super();cursor = index;}//判断当前游标位置的前面是否有值public boolean hasPrevious() {return cursor != 0;}//获取游标位置public int nextIndex() {return cursor;}//获取游标位置的前一个值，其实就是Itr的LastRef，即上一次已经遍历过的值。public int previousIndex() {return cursor - 1;}//获取上一次已经遍历过得值，其实就是前遍历。public E previous() {synchronized (Vector.this) {checkForComodification();//要获取的元素下标int i = cursor - 1;if (i < 0)throw new NoSuchElementException();//更新游标，即下一次访问元素下标。cursor = i;//返回要访问的元素，这里为什么要last = i呢？？在Itr迭代器中，我们知道last 都是 = cur-1的，但是这里//lastRef = cursor了。我们只要记住他们的含义就好理解了，cursor记录的是下一个要访问元素的下标（正向遍历）//而lastRet记录的上一次访问的元素下标，因为这次我们访问的是cursor - 1，所以更新lastRet = i;return elementData(lastRet = i);}}//将上一次访问的元素用e给替换掉。public void set(E e) {if (lastRet == -1)throw new IllegalStateException();synchronized (Vector.this) {checkForComodification();Vector.this.set(lastRet, e);}}//向集合中添加元素，添加位置为cursor位置，需要注意并不是在数组末尾添加的，如果cursor后面还有值，会往后移动。//比如 elementData[5]{0，1，2，3，4},cursor = 3,调用add(8),则变成{0，1，2，8，3，4}public void add(E e) {int i = cursor;synchronized (Vector.this) {checkForComodification();//添加元素，并修改集合版本号Vector.this.add(i, e);//更新版本号expectedModCount = modCount;}cursor = i + 1;//这次是添加元素，所以没有对元素访问，即为-1lastRet = -1;}}

三、总结

• Vector：是线程安全的集合。因为添加元素和删除元素的方法都有syncnized修饰。因为syncnized是重量级锁且是悲观锁，所以效率并不高。
• 使用数组来存储元素。
• Vector有两种迭代器，可根据不同场景选择不同的迭代器。通过维护游标curosr和lastRet来维护下一个要访问的元素下标和上一次访问元素下标。
  • Itr迭代器迭代过程不允许集合被修改，通过该迭代器初始化时记录集合的版本号，并在跌单的过程用该版本号和集合的版本号进行比对来判断是否被修改。但其实在遍历的过程中如果调用迭代器的remove（）方法，可能会导致集合被修改，而又不触发异常的风险，详细可看上面的分析。
  • ListItr迭代器提供了遍历过程中修改元素的方法，并且更新集合版本号和迭代器版本号，并使其一致。