Java集合，Vector底层实现和原理

为什么80%的码农都做不了架构师？>>>

概述

文章的内容基于JDK1.7进行分析，之所以选用这个版本，是因为1.8的有些类做了改动，增加了阅读的难度，虽然是1.7，但是对于1.8做了重大改动的内容，文章也会进行说明。

作为List的另外一个典型实现类，完全支持List的全部功能，类也封装了一个动态的，允许在分配的[]数组，是一个比较古老的集合，JDK1.0就已经存在，建议尽量不要使用这个集合，与的主要是区别是，是线程安全的，但是性能比要低。

数据结构 继承关系

java.lang.Object java.util.AbstractCollection java.util.AbstractList java.util.Vector 

实现接口

Serializable, Cloneable, Iterable, Collection, List, RandomAccess 

子类

Stack 

基本属性

 protected Object[] elementData;  //存放元素的数组protected int elementCount;    //已经放入数组的元素个数protected int capacityIncrement; //数组的增长系数

源码解析

package java.util;public class Vectorextends AbstractListimplements List, RandomAccess, Cloneable, java.io.Serializable {//定义数组，存放元素protected Object[] elementData;//已经放入数组的元素数量protected int elementCount;//增长的系数protected int capacityIncrement;//可序列化版本号private static final long serialVersionUID = -2767605614048989439L;//构造方法，提供初始大小，和增长系数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);}//无参构造方法public Vector() {this(10);}//构造方法，将指定的集合元素转化为Vectorpublic Vector(Collection c) {elementData = c.toArray();elementCount = elementData.length;// c.toArray might (incorrectly) not return Object[] (see 6260652)//判断c.toArray是否是Object[]类型if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, elementCount, Object[].class);}//将elementData中的元素全部拷贝到anArray数组中public synchronized void copyInto(Object[] anArray) {System.arraycopy(elementData, 0, anArray, 0, elementCount);}//将数组长度设置为等于vector的个数public synchronized void trimToSize() {modCount++;int oldCapacity = elementData.length;if (elementCount < oldCapacity) {elementData = Arrays.copyOf(elementData, elementCount);}}//扩充容量public synchronized void ensureCapacity(int minCapacity) {if (minCapacity > 0) {modCount++;ensureCapacityHelper(minCapacity);}}//扩充容量帮助函数private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}//最大容量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//扩充容量执行方法private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//根据capacityIncrement进行判断，capacityIncrement> 0 增加capacityIncrement个容量，否则容量扩充当前容量的一倍int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);//扩容操作，生成已给新的数组，容量为newCapacity,并将elementData中的元素全部拷贝到新数组中，并将新生成的数组在赋值给elementData 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;}//设置sizepublic synchronized void setSize(int newSize) {modCount++;if (newSize > elementCount) {ensureCapacityHelper(newSize);} else {for (int i = newSize ; i < elementCount ; i++) {elementData[i] = null;}}elementCount = newSize;}//返回当前容量public synchronized int capacity() {return elementData.length;}//返回vector的元素个数public synchronized int size() {return elementCount;}//是否为空public synchronized boolean isEmpty() {return elementCount == 0;}//返回vector中全部元素对应的Enumerationpublic Enumeration elements() {//匿名内部类实现return new Enumeration() {int count = 0;public boolean hasMoreElements() {return count < elementCount;}public E nextElement() {synchronized (Vector.this) {if (count < elementCount) {return elementData(count++);}}throw new NoSuchElementException("Vector Enumeration");}};}//是否包含Object对线o public boolean contains(Object o) {return indexOf(o, 0) >= 0;}//返回 o 对象的位置public int indexOf(Object o) {return indexOf(o, 0);}//从index位置开始，向后查找Object对象 （o）public synchronized int indexOf(Object o, int index) {if (o == null) {for (int i = index ; i < elementCount ; i++)if (elementData[i]==null)return i;} else {for (int i = index ; i < elementCount ; i++)if (o.equals(elementData[i]))return i;}return -1;}//倒序查找对象 o public synchronized int lastIndexOf(Object o) {return lastIndexOf(o, elementCount-1);}//从最后一个元素开始，向前查找对象o ,找到返回元素的索引，否则返回 -1 public synchronized int lastIndexOf(Object o, int index) {if (index >= elementCount)throw new IndexOutOfBoundsException(index + " >= "+ elementCount);if (o == null) {for (int i = index; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = index; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}//返回索引为index的元素public synchronized E elementAt(int index) {if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);}return elementData(index);}//返回第一个元素public synchronized E firstElement() {if (elementCount == 0) {throw new NoSuchElementException();}return elementData(0);}//返回最后一个元素public synchronized E lastElement() {if (elementCount == 0) {throw new NoSuchElementException();}return elementData(elementCount - 1);}//将index位置的元素设置为obj public synchronized void setElementAt(E obj, int index) {if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " +elementCount);}elementData[index] = obj;}//删除指定位置的元素，Object[]对象数组从index+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);}elementCount--;elementData[elementCount] = null; /* to let gc do its work */}//将obj元素插入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;elementCount++;}//添加元素public synchronized void addElement(E obj) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = obj;}//删除元素 ，删除成功返回true, 否则返回falsepublic synchronized boolean removeElement(Object obj) {modCount++;int i = indexOf(obj);if (i >= 0) {removeElementAt(i);return true;}return false;}//清空所有的元素public synchronized void removeAllElements() {modCount++;// Let gc do its workfor (int i = 0; i < elementCount; i++)elementData[i] = null;elementCount = 0;}//克隆方法public synchronized Object clone() {try {@SuppressWarnings("unchecked")Vector v = (Vector) super.clone();v.elementData = Arrays.copyOf(elementData, elementCount);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// this shouldn't happen, since we are Cloneablethrow new InternalError();}}//转化为数组public synchronized Object[] toArray() {return Arrays.copyOf(elementData, elementCount);}//转化为指定类型的数组@SuppressWarnings("unchecked")public synchronized  T[] toArray(T[] a) {if (a.length < elementCount)return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());System.arraycopy(elementData, 0, a, 0, elementCount);if (a.length > elementCount)a[elementCount] = null;return a;}// Positional Access Operations@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}//得到索引为index的元素public synchronized E get(int index) {if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);return elementData(index);}//设置index位置的元素为element public synchronized E set(int index, E element) {if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}//添加方法public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}//删除操作public boolean remove(Object o) {return removeElement(o);}//将element添加到index位置上public void add(int index, E element) {insertElementAt(element, index);}//删除index位置的元素public synchronized E remove(int index) {modCount++;if (index >= elementCount)throw new ArrayIndexOutOfBoundsException(index);E oldValue = elementData(index);int numMoved = elementCount - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--elementCount] = null; // Let gc do its workreturn oldValue;}//清除public void clear() {removeAllElements();}// Bulk Operations//是否包含集合c中所有的元素public synchronized boolean containsAll(Collection c) {return super.containsAll(c);}//将集合c中所有的元素添加到列表中，借助System.copyOf()方法实现public synchronized boolean addAll(Collection c) {modCount++;Object[] a = c.toArray();int numNew = a.length;ensureCapacityHelper(elementCount + numNew);System.arraycopy(a, 0, elementData, elementCount, numNew);elementCount += numNew;return numNew != 0;}//删除集合c中所有的元素public synchronized boolean removeAll(Collection c) {return super.removeAll(c);}public synchronized boolean retainAll(Collection c) {return super.retainAll(c);}//将集合c 添加到index之后的位置上public synchronized boolean addAll(int index, Collection c) {modCount++;if (index < 0 || index > elementCount)throw new ArrayIndexOutOfBoundsException(index);Object[] a = c.toArray();int numNew = a.length;ensureCapacityHelper(elementCount + numNew);int numMoved = elementCount - index;if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);System.arraycopy(a, 0, elementData, index, numNew);elementCount += numNew;return numNew != 0;}//判断方法public synchronized boolean equals(Object o) {return super.equals(o);}//计算hashCode值public synchronized int hashCode() {return super.hashCode();}public synchronized String toString() {return super.toString();}//返回从fromIndex到toIndex之间的子集合public synchronized List subList(int fromIndex, int toIndex) {return Collections.synchronizedList(super.subList(fromIndex, toIndex),this);}//范围删除元素protected synchronized void removeRange(int fromIndex, int toIndex) {modCount++;int numMoved = elementCount - toIndex;System.arraycopy(elementData, toIndex, elementData, fromIndex,numMoved);// Let gc do its workint newElementCount = elementCount - (toIndex-fromIndex);while (elementCount != newElementCount)elementData[--elementCount] = null;}//将对象写入到输出流中private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {final java.io.ObjectOutputStream.PutField fields = s.putFields();final Object[] data;synchronized (this) {fields.put("capacityIncrement", capacityIncrement);fields.put("elementCount", elementCount);data = elementData.clone();}fields.put("elementData", data);s.writeFields();}public synchronized ListIterator listIterator(int index) {if (index < 0 || index > elementCount)throw new IndexOutOfBoundsException("Index: "+index);return new ListItr(index);}public synchronized ListIterator listIterator() {return new ListItr(0);}public synchronized Iterator iterator() {return new Itr();}//省略了Itr、ListItr、VectorSpliterator内部类的实现
}

总结

和的实现方式可以看出非常的类似，既然类建议尽量少的使用，还是最好不要用了，通过上面的源码发现，每个方法中都添加了的关键字来保证同步，所以它是线程安全的，但正是这些方法的同步，让它的效率大大的降低了，比的效率要慢。

给出如下几点总结：

1.有四个不同的构造方法。无参构造方法的容量为默认值10，仅包含容量的构造方法则将容量增长量（从源码中可以看出容量增长量的作用，第二点也会对容量增长量详细说）明置为0。

2.注意扩充容量的方法。

与相同，在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就先看构造方法中传入的容量增长量参数是否为0，如果不为0，就设置新的容量为就容量加上容量增长量，如果为0，就设置新的容量为旧的容量的2倍，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后同样用.()方法将元素拷贝到新的数组。

3.很多方法都加入了同步语句，来保证线程安全。

4.同样在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，中也允许元素为null。

5.其他很多地方都与实现大同小异，现在已经基本不再使用。