Vector和Stack源碼分析/List集合的總結

　　　　序言

　　　　　　　　這篇文章算是在這list接口下的集合的最後一篇了，前面ArrayList、LinkedList都已經講解完了，剩下就Vector和Vector的子類Stack啦。繼續努力。一步一個腳印，

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　--WZY

擴充

　　　　學習vector，需要一些多線程的知識，這裡比較雜，主要講解一下等會會用到的

　　　　1、鎖機制：對象鎖、方法鎖、類鎖

　　　　　　　　　　對象鎖就是方法鎖：就是在一個類中的方法上加上synchronized關鍵字，這就是給這個方法加鎖了。

　　　　　　　　　　類鎖：鎖的是整個類，當有多個線程來聲明這個類的對象的時候将會被阻塞，直到擁有這個類鎖的對象被銷毀或者主動釋放了類鎖。這個時候在被阻塞住的線程被挑選出一個占有該類鎖，聲明該類的對象。其他線程繼續被阻塞住。例如：在類A上有關鍵字synchronized，那麼就是給類A加了類鎖，線程1第一個聲明此類的執行個體，則線程1拿到了該類鎖，線程2在想聲明類A的對象，就會被阻塞。

　　　　2、在本文中，使用的是方法鎖。

　　　　3、每個對象隻有一把鎖，有線程A，線程B，還有一個集合C類，線程A操作C拿到了集合中的鎖(在集合C中有用synchronized關鍵字修飾的)，并且還沒有執行完，那麼線程A就不會釋放鎖，當輪到線程B去操作集合C中的方法時 ，發現鎖被人拿走了，是以線程B隻能等待那個拿到鎖的線程使用完，然後才能拿到鎖進行相應的操作。

　　　　　　這裡隻是簡單的介紹了一種鎖，這本篇文章中夠用了，如果覺得不夠，可以先去百度，或者查查關于多線程鎖的問題

一、初始Vector(檢視API文檔)　　　　　　　　

　　　　　　　　　　　　　

　　　　　　　　截圖一張供大家參考，通過閱讀api，我們可以知道以下幾點

　　　　　　　　　　1、Vector是一個可變化長度的數組

　　　　　　　　　　2、Vector增加長度通過的是capacity和capacityIncrement這兩個變量，目前還不知道如何實作自動擴增的，等會源碼分析

　　　　　　　　　　3、Vector也可以獲得iterator和listIterator這兩個疊代器，并且他們發生的是fail-fast，而不是fail-safe，注意這裡，不要覺得這個vector是線程安全就搞錯了，具體分析在下面會說

　　　　　　　　　　4、Vector是一個線程安全的類，如果使用需要線程安全就使用Vector，如果不需要，就使用arrayList

　　　　　　　　　　5、Vector和ArrayList很類似，就少許的不一樣，從它繼承的類和實作的接口來看，跟arrayList一模一樣。

　　　　現在的版本已經是jdk1.7，還有更高的jdk1.8了，在開發中，建議不用vector，原因在文章的結束會有解釋，如果需要線程安全的集合類直接用java.util.concurrent包下的類。

二、Vector的繼承結構

　　　　　　　　　發兩張圖來壓壓驚，這個就不用過多的解釋了吧，跟那個ArrayList的一模一樣，如果不明白，可以去那裡看清楚哦。

　　　　　　　　

http://www.cnblogs.com/whgk/p/6079212.html http://www.cnblogs.com/whgk/p/6081526.html#3560719

　　　　　　　　　

　　　　　　　　　　

二、構造方法

　　　　　　一共有四個構造方法。最後兩個構造方法是collection Framwork的規範要寫的構造方法。

　　　　　　　　　　構造方法做的事：

　　　　　　　　　　　　　　1、初始化存儲元素的容器，也就是數組，elementData，

　　　　　　　　　　　　　　2、初始化capacityIncrement的大小，預設是0，這個的作用就是擴充數組的時候，增長的大小，為0則每次擴充2倍

　　　　　　

　　　　　　Vector()：空構造

/**

* Constructs an empty vector so that its internal data array
 * has size {@code 10} and its standard capacity increment is
 * zero.
 */           

//看注釋，這個是一個空的Vector構造方法，是以讓他使用内置的數組，這裡還不知道什麼是内置的數組，看它調用了自身另外一個帶一個參數的構造器

public Vector() {
    this(10);
}

           

　　　　　　Vector(int)

/**
 * 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
 */           

//注釋說，給空的cector構造器用和帶有一個特定初始化容量用的，并且又調用了另外一個帶兩個參數的構造器，并且給容量增長值(capacityIncrement=0)為0，檢視vector中的變量可以發現capacityIncrement是一個成員變量

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

           

　　　　　　Vector(int，int)

* 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
 */           

//建構一個有特定的初始化容量和容量增長值的空的Vector，

public Vector(int initialCapacity, int capacityIncrement) {
    super();//調用父類的構造，是個空構造
    if (initialCapacity < 0)//小于0，會報非法參數異常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];//elementData是一個成員變量數組，初始化它，并給它初始化長度。預設就是10，除非自己給值。
    this.capacityIncrement = capacityIncrement;//capacityIncrement的意思是如果要擴增數組，每次增長該值，如果該值為0，那數組就變為兩倍的原長度，這個之後會分析到
}

           

　　　　　　Vector(Collection<? extends E> c)

　　　　　　　　之前對于這個隻知道他的作用，但是原理不清楚，但是通過最近看資料結構與算法分析(java語言)這本書，知道了原來這個是叫做“帶有限制的通配符”，現在就來講一講為什麼需要這樣做(Collection<? enxtends E>)？

　　　　　　　　　　1、涉及到一個名詞"協變"，先說一下數組是協變的，什麼意思呢？舉個例子：Employee extends People、那麼People p = new Employee()；這個是可以得，那麼我們就想，如果是People[] p = new Employee[5];是否可以呢，答案是可以得，原因就是數組是協變得，但是這會出現一個問題，就是如果Student extends People，那麼People[] P = new Employee[5]；然後P[0] = new Student(..)； 這樣的情況編譯可以通過，但運作時就會報ArrayStoreException異常。這個例子就說明什麼是協變，協變就是類型相容，上面的Employee數組類型和People數組類型相容，是以那樣編譯時能通過，不會報錯。

　　　　　　　　　　2、上面通過數組的例子講解了“協變”，數組可以那樣轉換，那集合呢，如果一個方法的參數是collection，那我們能不能傳一個collection的集合進去呢？大難是否定的，因為泛型集合不是協變得，也就是說它不能類型相容，但是實際中，我們又需要讓它們類型相容，那怎麼辦呢，在jdk5中，就開始使用通配符來解決這個問題，就是通過collection<? extends People> 這樣的形式來解決，當你傳入的集合是People的子類時，那麼就可以協變。

　　　　　　　　　　通過上面的講解，我們就可以知道，這個構造方法中的參數的意思是什麼了？目的就是為了讓泛型E的子類能夠傳進來，并且轉換為泛型為E的集合來用，是以說注釋中說什麼傳回一個集合的iterator，就是這個意思。

/**
 * Constructs a vector containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this
 *       vector
 * @throws NullPointerException if the specified collection is null
 * @since   1.2
 */           

//将集合c變為Vector，傳回Vector的疊代器。

public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}



           

三、常用方法

　　　　　　增删改查方法

　　　　　　add()

　　

/**
 * 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
 */           

//就是在vector中的末尾追加元素。但是看方法，synchronized，明白了為什麼vector是線程安全的，因為在方法前面加了synchronized關鍵字，給該方法加鎖了，哪個線程先調用它，其它線程就得等着，如果不清楚的就去看看多線程的知識，到後面我也會一一總結的。

public synchronized boolean add(E e) {
    modCount++;           

//通過arrayList的源碼分析經驗，這個方法應該是在增加元素前，檢查容量是否夠用

ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}           

　　　　　　ensureCapacityHelper(int)

/**
 * This implements the unsynchronized semantics of ensureCapacity.
 * Synchronized methods in this class can internally call this
 * method for ensuring capacity without incurring the cost of an
 * extra synchronization.
 *
 * @see #ensureCapacity(int)
 */           

//這裡注釋解釋，這個方法是異步(也就是能被多個線程同時通路)的，原因是為了讓同步方法都能調用到這個檢測容量的方法，比如add的同時，另一個線程調用了add的重載方法，那麼兩個都需要同時查詢容量夠不夠，是以這個就不需要用synchronized修飾了。因為不會發生線程不安全的問題

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)           

//容量不夠，就擴增，核心方法

grow(minCapacity);
}

           

　　　　　　grow(int)

//看一下這個方法，其實跟arrayList一樣，唯一的不同就是在擴增數組的方式不一樣，如果capacityIncrement不為0，那麼增長的長度就是capacityIncrement，如果為0，那麼擴增為2倍的原容量

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);
}

           

　　　　核心的東西就已經講完了，個人覺得，你看的懂arrayList，這個就很輕松，也就在每個方法上比arrayList多了一個synchronized。其他都一樣。看下面的方法等等，都市這樣，這裡就不帶着大家分析了。

四、Stack

　　　　　　現在來看看Vector的子類Stack，學過資料結構都知道，這個就是棧的意思。那麼該類就是跟棧的用法一樣了

　　　　　　通過檢視他的方法，和檢視api文檔，很容易就能知道他的特性。就幾個操作，出棧，入棧等，構造方法也是空的，用的還是數組，父類中的構造，跟父類一樣的擴增方式，并且它的方法也是同步的，是以也是線程安全

　　　　　　　

五、總結Vector和Stack

　　　　　　首先，通過Vector源碼分析，知道

　　　　　　1、Vector線程安全是因為他的方法都加了synchronized關鍵字

　　　　　　2、Vector的本質是一個數組，特點能是能夠自動擴增，擴增的方式跟capacityIncrement的值有關

　　　　　　3、它也會fail-fast，還有一個fail-safe兩個的差別在下面的list總結中會講到

　　　　　　Stack的總結

　　　　　　1、對棧的一些操作，後進先出

　　　　　　2、底層也是用數組實作的，因為繼承了Vector

　　　　　　3、也是線程安全的

　　　　　　　List接口下的常用類到這裡就已經結束了，現在總結一下（jdk1.7）

　　1、arrayList和LinkedList差別？

　　　　　　·arrayList底層是用數組實作的順序表，是随機存取類型，可自動擴增，并且在初始化時，數組的長度是0，隻有在增加元素時，長度才會增加。預設是10，不能無限擴增，有上限，在查詢操作的時候性能更好

　　　　　　·LinkedList底層是用連結清單來實作的，是一個雙向連結清單，注意這裡不是雙向循環連結清單,順序存取類型。在源碼中，似乎沒有元素個數的限制。應該能無限增加下去，直到記憶體滿了在進行删除，增加操作時性能更好。

　　　　　　·兩個都市線程不安全的，在iterator時，會發生fail-fast。

　　2、arrayList和Vector的差別？

　　　　　　·arrayList線程不安全，在用iterator，會發生fail-fast

　　　　　　·Vector線程安全，因為在方法前加了Synchronized關鍵字。也會發生fail-fast

　　3、fail-fast和fail-safe差別是什麼?什麼情況下會發生？

　　　　　　一句話，在在java.util下的集合都是發生fail-fast，而在java.util.concurrent下的發生的都是fail-safe

　　　　　　fail-fast：快速失敗，例如在arrayList中使用疊代器周遊時，有另外的線程對arrayList的存儲數組進行了改變，比如add、delete、等使之發生了結構上的改變，是以Iterator就會快速報一個

java.util.ConcurrentModificationException 異常，這就是快速失敗。

　　　　　　fail-safe:安全失敗，在java.util.concurrent下的類，都是線程安全的類，他們在疊代的過程中，如果有線程進行結構的改變，不會報異常，而是正常周遊，這就是安全失敗。

　　　　　　　　　　　　1、為什麼在java.util.concurrent包下對集合有結構的改變，卻不會報異常？

　　　　　　　　　　　　　　　　這裡稍微解釋一下，在concurrent下的集合類增加元素的時候使用Arrays.copyOf()來拷貝副本，在副本上增加元素，如果有其他線程在此改變了集合的結構，那也是在副本上的改變，而不是影響到原集合，疊代器還是照常周遊，周遊完之後，改變原引用指向副本，是以總的一句話就是如果在次包下的類進行增加删除，就會出現一個副本。是以能防止fail-fast，這種機制并不會出錯，是以我們叫這種現象為fail-safe。

　　　　　　　　　　　　2、vector也是線程安全的，為什麼是fail-fast呢？

　　　　　　　　　　　　　　　　這裡搞清楚一個問題，并不是說線程安全的集合就不會報fail-fast，而是報fail-safe，你得搞清楚上面這個問題答案的原理，出現fail-safe是因為他們在實作增删的底層機制不一樣，就像上面說的，會有一個副本，而像arrayList、linekdList、verctor等，他們底層就是對着真正的引用進行操作，是以才會發生異常。

　　　　　　　　　　　　3、既然是線程安全的，為什麼在疊代的時候，還會有别的線程來改變其集合的結構呢(也就是對其删除和增加等操作)？

　　　　　　　　　　　　　　　　首先，我們疊代的時候，根本就沒用到集合中的删除、增加，查詢的操作，就拿vector來說，我們都沒有用那些加鎖的方法，也就是方法鎖放在那沒人拿，在疊代的過程中，有人拿了那把鎖，我們也沒有辦法，因為那把鎖就放在那邊，

　　　　　　　　　　　

　　　　　舉例來實作這兩種情況的出現

　　　　　　fail-fast

　　　　　　　　　　　　　　　

　　　　　　fail-safe

　　　　　　　　　　這裡就直接上截圖了，通過CopyOnWriteArrayList這個類來做實驗，不用管這個類的作用，但是他确實沒有報異常，并且還通過第二次列印，來驗證了上面我們說建立了副本的事情。别說你不知道怎麼驗證的，哈哈，那我解釋一下吧，原理是在添加操作時會建立副本，在副本上進行添加操作，等疊代器周遊結束後，會将原引用改為副本引用，是以我們在建立了一個list的疊代器，結果列印的就是123444了，證明了确實改變成為了副本引用，後面為什麼是三個4，原因是我們循環了3次，不久添加了3個4嗎。如果還感覺不爽的話，看下add的源碼

　　　

　　　　4、為什麼現在都不提倡使用vector了

　　　　　　　　　這裡推薦一個解答這個問題的答案，我也是借鑒它的回答來解答，因為我覺得這個答案更好。

　　　　　　　1、vector實作線程安全的方法是在每個操作方法上加鎖，這些鎖并不是必須要的，在實際開發中，一般都市通過鎖一系列的操作來實作線程安全，也就是說将需要同步的資源放一起加鎖來保證線程安全，

　　　　　　　2、如果多個Thread并發執行一個已經加鎖的方法，但是在該方法中，又有vector的存在，vector本身實作中已經加鎖了，那麼相當于鎖上又加鎖，會造成額外的開銷，

　　　　　　 3、就如上面第三個問題所說的，vector還有fail-fast的問題，也就是說它也無法保證周遊安全，在周遊時又得額外加鎖，又是額外的開銷，還不如直接用arrayList，然後再加鎖呢。

　　　　　　總結：Vector在你不需要進行線程安全的時候，也會給你加鎖，也就導緻了額外開銷，是以在jdk1.5之後就被棄用了，現在如果要用到線程安全的集合，都是從java.util.concurrent包下去拿相應的類。