java 集合类源码分析--Vector

时间:2022-10-10 17:03:37

首先我们来看JDK源码中Java.util.Vector的代码,剔除所有的方法和静态变量,

Java.lang.Vector的核心代码如下:

  1. public class Vector<E>  
  2.     extends AbstractList<E>  
  3.     implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
  4. {  
  5.      
  6.     protected Object[] elementData;  
  7.   
  8.     /** 
  9.      * The number of valid components in this {@code Vector} object. 
  10.      * Components {@code elementData[0]} through 
  11.      * {@code elementData[elementCount-1]} are the actual items. 
  12.      * 
  13.      * @serial 
  14.      */  
  15.     protected int elementCount;  
  16.   
  17.     protected int capacityIncrement; //可以设定固定增量  
  18. }  

通过上面的代码我们能看到他是数组存储。

 

它的构造方法有四个:

  1. /** 
  2.     * Constructs an empty vector with the specified initial capacity and 
  3.     * capacity increment. 
  4.     * 
  5.     * @param   initialCapacity     the initial capacity of the vector 
  6.     * @param   capacityIncrement   the amount by which the capacity is 
  7.     *                              increased when the vector overflows 
  8.     * @throws IllegalArgumentException if the specified initial capacity 
  9.     *         is negative 
  10.     */  
  11.    public Vector(int initialCapacity, int capacityIncrement) {   //设置初始容量,及固定增量  
  12. super();  
  13.        if (initialCapacity < 0)  
  14.            throw new IllegalArgumentException("Illegal Capacity: "+  
  15.                                               initialCapacity);  
  16. this.elementData = new Object[initialCapacity];  
  17. this.capacityIncrement = capacityIncrement;  
  18.    }  
  19.   
  20.    /** 
  21.     * Constructs an empty vector with the specified initial capacity and 
  22.     * with its capacity increment equal to zero. 
  23.     * 
  24.     * @param   initialCapacity   the initial capacity of the vector 
  25.     * @throws IllegalArgumentException if the specified initial capacity 
  26.     *         is negative 
  27.     */  
  28.    public Vector(int initialCapacity) {    //设置初始容量,不设定固定增量(如果不设定固定增量,则成倍增长)  
  29. this(initialCapacity, 0);  
  30.    }  
  31.   
  32.    /** 
  33.     * Constructs an empty vector so that its internal data array 
  34.     * has size {@code 10} and its standard capacity increment is 
  35.     * zero. 
  36.     */  
  37.    public Vector() {    //不设置初始容量,初始容量为10,不设定固定增量(如果不设定固定增量,则成倍增长)  
  38. this(10);  
  39.    }  
  40.   
  41.    /** 
  42.     * Constructs a vector containing the elements of the specified 
  43.     * collection, in the order they are returned by the collection's 
  44.     * iterator. 
  45.     * 
  46.     * @param c the collection whose elements are to be placed into this 
  47.     *       vector 
  48.     * @throws NullPointerException if the specified collection is null 
  49.     * @since   1.2 
  50.     */  
  51.    public Vector(Collection<? extends E> c) {  //以集合初始化  
  52. elementData = c.toArray();  
  53. elementCount = elementData.length;  
  54. // c.toArray might (incorrectly) not return Object[] (see 6260652)  
  55. if (elementData.getClass() != Object[].class)  
  56.     elementData = Arrays.copyOf(elementData, elementCount, Object[].class);  
  57.    }  

下面我们再看一下 Vector类的 add(E e)方法的源代码:

 

 

[java]  view plain copy
 
 
  1.   /** 
  2.     * Appends the specified element to the end of this Vector. 
  3.     * 
  4.     * @param e element to be appended to this Vector 
  5.     * @return {@code true} (as specified by {@link Collection#add}) 
  6.     * @since 1.2 
  7.     */  
  8.    public synchronized boolean add(E e) {    //从这里的synchronized我们可以知道他是线程同步的  
  9. modCount++;  
  10. ensureCapacityHelper(elementCount + 1);   //是否需要扩容  
  11. elementData[elementCount++] = e;   //后放的永远在最后一位  
  12.        return true;   // 好像他永远返回true 哦  
  13.    }  

[java]  view plain copy
 
 
  1.    /** 
  2.     * This implements the unsynchronized semantics of ensureCapacity. 
  3.     * Synchronized methods in this class can internally call this 
  4.     * method for ensuring capacity without incurring the cost of an 
  5.     * extra synchronization. 
  6.     * 
  7.     * @see #ensureCapacity(int) 
  8.     */  
  9.    private void ensureCapacityHelper(int minCapacity) {  
  10. int oldCapacity = elementData.length;  
  11. if (minCapacity > oldCapacity) {    //最新的值如果超出现有容量 扩容  
  12.     Object[] oldData = elementData;  
  13.     int newCapacity = (capacityIncrement > 0) ?  
  14.     (oldCapacity + capacityIncrement) : (oldCapacity * 2);  //如果固定增量不为0则增长固定增量,否则成倍增长  
  15.   
  16.         if (newCapacity < minCapacity) {   //新容量还小,这个可能性应该不大  
  17.     newCapacity = minCapacity;  
  18.     }  
  19.            elementData = Arrays.copyOf(elementData, newCapacity);   // 改变数组的大小,这个方法可以记一下  
  20. }  
  21.    }  

下面我们再看一下 Vector类的 remove(Object o)方法的源代码:

 

 

[java]  view plain copy
 
 
  1. /** 
  2.     * Removes the first occurrence of the specified element in this Vector 
  3.     * If the Vector does not contain the element, it is unchanged.  More 
  4.     * formally, removes the element with the lowest index i such that 
  5.     * {@code (o==null ? get(i)==null : o.equals(get(i)))} (if such 
  6.     * an element exists). 
  7.     * 
  8.     * @param o element to be removed from this Vector, if present 
  9.     * @return true if the Vector contained the specified element 
  10.     * @since 1.2 
  11.     */  
  12.    public boolean remove(Object o) {  
  13.        return removeElement(o);      //他是调用的removeElement  
  14.    }  
  15.    
  16. /** 
  17.     * Removes the first (lowest-indexed) occurrence of the argument 
  18.     * from this vector. If the object is found in this vector, each 
  19.     * component in the vector with an index greater or equal to the 
  20.     * object's index is shifted downward to have an index one smaller 
  21.     * than the value it had previously. 
  22.     * 
  23.     * <p>This method is identical in functionality to the 
  24.     * {@link #remove(Object)} method (which is part of the 
  25.     * {@link List} interface). 
  26.     * 
  27.     * @param   obj   the component to be removed 
  28.     * @return  {@code true} if the argument was a component of this 
  29.     *          vector; {@code false} otherwise. 
  30.     */  
  31.    public synchronized boolean removeElement(Object obj) {  
  32. modCount++;  
  33. int i = indexOf(obj);         //查找obj第一次出现的位置,(Vector是允许重复值的)  
  34. if (i >= 0) {  
  35.     removeElementAt(i);          
  36.     return true;  
  37. }  
  38. return false;  
  39.    }  
  40.   
  41. /** 
  42.     * Deletes the component at the specified index. Each component in 
  43.     * this vector with an index greater or equal to the specified 
  44.     * {@code index} is shifted downward to have an index one 
  45.     * smaller than the value it had previously. The size of this vector 
  46.     * is decreased by {@code 1}. 
  47.     * 
  48.     * <p>The index must be a value greater than or equal to {@code 0} 
  49.     * and less than the current size of the vector.  
  50.     * 
  51.     * <p>This method is identical in functionality to the {@link #remove(int)} 
  52.     * method (which is part of the {@link List} interface).  Note that the 
  53.     * {@code remove} method returns the old value that was stored at the 
  54.     * specified position. 
  55.     * 
  56.     * @param      index   the index of the object to remove 
  57.     * @throws ArrayIndexOutOfBoundsException if the index is out of range 
  58.     *          ({@code index < 0 || index >= size()}) 
  59.     */  
  60.    public synchronized void removeElementAt(int index) {  
  61. modCount++;  
  62. if (index >= elementCount) {  
  63.     throw new ArrayIndexOutOfBoundsException(index + " >= " +  
  64.                          elementCount);  
  65. }  
  66. else if (index < 0) {  
  67.     throw new ArrayIndexOutOfBoundsException(index);  
  68. }  
  69. int j = elementCount - index - 1;  // 数组中index以后的元素个数  
  70. if (j > 0) {  
  71.     System.arraycopy(elementData, index + 1, elementData, index, j);   // 数组中index以后的元素,整体前移,(这个方法挺有用的!!)  
  72. }  
  73. elementCount--;  
  74. elementData[elementCount] = null; /* to let gc do its work */  
  75.    }  

从上面的代码我们可以看出 Vector每次只删除最靠前的那个相符的变量。

下面我们再看一下 Vector类的 equals(Object o)方法的源代码:

 

[java]  view plain copy
 
 
  1.    /** 
  2.     * Compares the specified Object with this Vector for equality.  Returns 
  3.     * true if and only if the specified Object is also a List, both Lists 
  4.     * have the same size, and all corresponding pairs of elements in the two 
  5.     * Lists are <em>equal</em>.  (Two elements {@code e1} and 
  6.     * {@code e2} are <em>equal</em> if {@code (e1==null ? e2==null : 
  7.     * e1.equals(e2))}.)  In other words, two Lists are defined to be 
  8.     * equal if they contain the same elements in the same order. 
  9.     * 
  10.     * @param o the Object to be compared for equality with this Vector 
  11.     * @return true if the specified Object is equal to this Vector 
  12.     */  
  13.    public synchronized boolean equals(Object o) {  
  14.        return super.equals(o);   //他是调用的父类AbstractList的equals  
  15.    }  
  16.   
  17.   
  18.    /** 
  19.     * Compares the specified object with this list for equality.  Returns 
  20.     * {@code true} if and only if the specified object is also a list, both 
  21.     * lists have the same size, and all corresponding pairs of elements in 
  22.     * the two lists are <i>equal</i>.  (Two elements {@code e1} and 
  23.     * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null : 
  24.     * e1.equals(e2))}.)  In other words, two lists are defined to be 
  25.     * equal if they contain the same elements in the same order.<p> 
  26.     * 
  27.     * This implementation first checks if the specified object is this 
  28.     * list. If so, it returns {@code true}; if not, it checks if the 
  29.     * specified object is a list. If not, it returns {@code false}; if so, 
  30.     * it iterates over both lists, comparing corresponding pairs of elements. 
  31.     * If any comparison returns {@code false}, this method returns 
  32.     * {@code false}.  If either iterator runs out of elements before the 
  33.     * other it returns {@code false} (as the lists are of unequal length); 
  34.     * otherwise it returns {@code true} when the iterations complete. 
  35.     * 
  36.     * @param o the object to be compared for equality with this list 
  37.     * @return {@code true} if the specified object is equal to this list 
  38.     */  
  39.    public boolean equals(Object o) {  
  40. if (o == this)  
  41.     return true;  
  42. if (!(o instanceof List))  
  43.     return false;  
  44.   
  45. ListIterator<E> e1 = listIterator();  
  46. ListIterator e2 = ((List) o).listIterator();  
  47. while(e1.hasNext() && e2.hasNext()) {  
  48.     E o1 = e1.next();  
  49.     Object o2 = e2.next();  
  50.     if (!(o1==null ? o2==null : o1.equals(o2)))   //判断了三次  
  51.                  //这个方法挺不错的,应该比if(!(null==o1&&null==o2)||(null!=o1&&o1.equals(o2)))(大于等于三次判断)  
  52.     return false;  
  53. }  
  54. return !(e1.hasNext() || e2.hasNext());  //长度是否一致  
  55.    }  

下面我们再看一下 Vector类的 hashCode()方法的源代码:

 

 

[java]  view plain copy
 
 
  1.     /** 
  2.      * Returns the hash code value for this Vector. 
  3.      */  
  4.     public synchronized int hashCode() {  
  5.         return super.hashCode();   //他也是调用的父类AbstractList的hashCode  
  6.     }  
  7.   
  8. /** 
  9.      * Returns the hash code value for this list. 
  10.      * 
  11.      * <p>This implementation uses exactly the code that is used to define the 
  12.      * list hash function in the documentation for the {@link List#hashCode} 
  13.      * method. 
  14.      * 
  15.      * @return the hash code value for this list 
  16.      */  
  17.     public int hashCode() {  
  18.     int hashCode = 1;  
  19.     Iterator<E> i = iterator();  
  20.     while (i.hasNext()) {  
  21.         E obj = i.next();  
  22.         hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());  
  23.            // 在这里用obj,比用i.next()效率高一倍(一直没明白他这为什么用31)  
  24.     }  
  25.     return hashCode;  
  26.     }  

 

 
0

 

Vector的底层也是使用数组实现的,而且继承了AbstractList,实现了List接口,看着Vector和ArrayList很像:底层都是用数组实现,都继承了AbstractList,实现了List接口。所以搜了下看看Vector和ArrayList有什么区别。

  
    在The Java Programming Language (Addison-Wesley, June 2000) 中Ken Arnold, James Gosling, 和 David Holmes 是这样描述Vector的,它是更ArrayList类似的一个东西,所以从API的观点来看,它们俩是很相似的。但是,它们之间还是有些微的差别的。
 
     1. 同步性
 
    Vectors是可同步化的,意思就是说,任何操作Vector的内容的方法都是线程安全的,相反的,另一方面,ArrayList是不可同步化的,所以也不是线程安全的。如果你知道了这些的话,你就会发现,Vector的同步会让它在性能发方面有一些小问题。所以,如果你不需要线程安全的话,那么就使用ArrayList吧。为什么要为没有必要的同步付出代价呢?
 
     2. 数据增长
 
    实际上,不管是ArrayList还是Vector,在它们内部都是使用一个 数组来保存数据的。开发过程中,在使用它们任何一个的时候,你都需要记住这一点。你在往一个ArrayList或者Vector里插入一个元素的时候,如果内部数组空间不够了,ArrayList或者Vector就要扩展它的大小。Vector在默认情况下是增长一倍的大小,而ArrayList增加50%的大小。只要你合理的使用这些类,你就可以结束你在增加新的元素的时候所付出的性能代价。设置初始化容量为你编程过程中所能用到的最大的容量总是最好的办法。精确的指定容量,你可以避免以后改变内部Array容量,所要付出的代价。如果你并不知道到底有多少个数据,当是你知道数据的增长率,Vector确实有一点点优势,因为你可以指定增加值(作者说的方法应该是setSize(int newSize) Sets the size of this vector.)。
 
     3. 查询,插入,删除对象的效率
 
    ArrayList和Vector在从指定位置取得元素,从容器的末尾增加和删除元素都非常的有效,所有的这些操作都能在一个常数级的时间O(1)内完成。但是从一个其他的位置增加和删除一个元素就显得颇为费时,差不多需要的时间为O(n-i),这里的n代表元素个数,i代表要增加和删除的元素所在的位置。这些操作需花费更多的时间,因为你需要挨个移动i和更高位置的元素。那么,以上这些到底说明了什么呢?
  
  这意味着,如果你取得一个元素,或者从数组末尾增加或删除一个元素的话,随便你使用Vector和ArrayList。如果你想要对数组内容做其他操作的话,那么就为自己好另一个容器吧。比如说,LinkedList可以在常数级时间(O1)内为任意一个位置的元素增加和删除。
   (这个涉及到ArrayList和LinkedList的实现不同,一个是数组,一个是链表了,这个以后再写一篇博客说说。)
 
    最后,Practical Java (Addison-Wesley, Feb. 2000) Peter Haggar 里的“实践41“建议你使用一个普通的原始的数组来代替Vector和ArrayListe,特别是对效率优先的代码来说。通过使用数组(array),你可以避免同步,额外的方法调用,非理想化的大小改变。你付出的只是额外的开发时间。
 
    看来常用的还是ArrayList,只有在线程安全时才会去使用Vector