java-并發-同步容器

Java常用的容器有ArrayList、LinkedList、HashMap等等，這些容器都是非線程安全的。如果有多個線程并發地通路這些容器時，就會出現問題。在編寫程式時，必須要求程式員手動地在任何通路到這些容器的地方進行同步處理。

是以，Java提供了同步容器供使用者使用，Java庫本身就有多種線程安全的容器和同步工具。

1）Vector、Stack、HashTable

Vector實作了List接口，Vector實際上就是一個數組，和ArrayList類似，但是Vector中的方法都是synchronized方法，即進行了同步措施。

Stack也是一個同步容器，它的方法也用synchronized進行了同步，它實際上是繼承于Vector類。

HashTable實作了Map接口，它和HashMap很相似，但是HashTable進行了同步處理，而HashMap沒有。

2）Collections類中提供的靜态工廠方法建立的類

Collections類是一個工具提供類。在Collections類中提供了大量的方法，比如對集合或者容器進行排序、查找等操作。更重要的是，在它裡面提供了幾個靜态工廠方法來建立同步容器類。JDK1.2中加入的同步包裝類，這些類都是由Collections.synchronizedXXX工廠方法。同步容器都是線程安全的，但是對于複合操作，有些缺點。

①　疊代：在查覺到容器在疊代開始以後被修改，會抛出一個未檢查異常ConcurrentModificationException，為了避免這個異常，需要在疊代期間，持有一個容器鎖。但是鎖的缺點也很明顯，就是對性能的影響。

②　隐藏疊代器：StringBuilder的toString方法會通過疊代容器中的每個元素，另外容器的hashCode和equals方法也會間接地調用疊代。類似地，contailAll、removeAll、retainAll方法，以及容器作為參數的構造函數，都會對容器進行疊代。

③　缺少即加入等一些複合操作

getLast和deleteLast都是複合操作，由先前對原子性的分析可以判斷，這依然存線上程安全問題，有可能會抛出ArrayIndexOutOfBoundsException的異常。

解決辦法就是通過對這些複合操作加鎖，jdk1.5從同步容器的具體實作源碼可知，同步容器中的方法采用了synchronized進行了同步，那麼必然會影響到程式的執行性能。于是Java提供了性能更優并發容器。

Vector 是矢量隊列，它是JDK1.0版本添加的類。

1、繼承于AbstractList，實作了List, RandomAccess, Cloneable這些接口。繼承了AbstractList，實作了List；是以，它是一個隊列，支援相關的添加、删除、修改、周遊等功能。

2、實作了RandmoAccess接口，即提供了随機通路功能。RandmoAccess是java中用來被List實作，為List提供快速通路功能的。在Vector中，我們即可以通過元素的序号快速擷取元素對象；這就是快速随機通路。

3、Vector 實作了Cloneable接口，即實作clone()函數。它能被克隆。Vector不支援序列化，即沒有實作java.io.Serializable接口。

源碼

Vector實際上是通過一個數組去儲存資料的。當我們構造Vecotr時；若使用預設構造函數，則Vector的預設容量大小是10。

當Vector容量不足以容納全部元素時，Vector的容量會增加。若容量增加系數 >0，則将容量的值增加“容量增加系數”；否則，将容量大小增加一倍。Vector的克隆函數，即是将全部元素克隆到一個數組中。

4種周遊方式

Stack類繼承了Vector類，而Vector類繼承了AbstractList抽象類，實作了List接口，Cloneable接口，RandomAcces接口以及Serializable接口，需要指出的Vector内部還有兩個内部類ListItr和Itr，Itr在繼承Vector的同時實作了Iterator接口，而ListItr在繼承了Itr類的同時實作了ListIterator接口。

通過Stack類發現含有的方法有pop(),peek(),push(Object),search(Object),empty()方法，其他值的方法是從Vector類繼承而來，通過源碼可以發現Vector有幾個屬性值：

protected Object[] elementData ，

protected int elementCount ;

protected int capacityIncrement ;

private static final int MAX_ARRAY_SIZE = 2147483639 ;

通過這幾屬性我們可以發現，Stack底層是采用數組來實作的，elementData用于儲存Stack中的每個元素；

elementCount用于動态的儲存元素的個數，

capacityIncrement用來儲存Stack的容量（一般情況下應該是大于elementCount）；

MAX_ARRAY_SIZE 用于限制Stack能夠儲存的最大值數量。

Vector底層是一個數組，說明Stack的實作是通過數組來實作的，然後通過對數組的操作來模仿棧的各種功能。而且在源碼中Vector的很多方法都是synchronized 的，也就是說是線程安全，是以說在多線程中是可以安全使用的，不過這樣效率上肯定是會降低的

Hashtable同樣是基于哈希表實作的，同樣 每個元素是一個key-value對，其内部也是通過單連結清單解決沖突問題，容量不足（超過了閥值）時，同樣會自動增長。Hashtable也是JDK1.0引入的類，是線程安全的，能用于多線程環境中。Hashtable同樣 實作了Serializable接口，它支援序列化，實作了Cloneable接口，能被克隆 。

與HashMap的比較來總結。

1、二者的存儲結構和解決沖突的方法都是相同的。

2、HashTable在不指定容量的情況下的預設容量為11，而HashMap為16，Hashtable不要求底層數組的容量一定要為2的整數次幂，而HashMap則要求一定為2的整數次幂。

3、 Hashtable中key和value都不允許為null，而HashMap中key和value都允許為null（key隻能有一個為null，而value則可以有多個為null）。

但是如果在Hashtable中有類似put(null,null)的操作，編譯同樣可以通過，因為key和value都是Object類型，但運作時會抛出NullPointerException異常，這是JDK的規範規定的。

4、Hashtable擴容時，将容量變為原來的2倍加1，而HashMap擴容時，将容量變為原來的2倍。

5、Hashtable計算hash值，直接用key的hashCode()，HashMap重新計算了key的hash值，Hashtable在求hash值對應的位置索引時，用取模運算，而HashMap在求位置索引時，則用與運算，且這裡一般先用hash&0x7FFFFFFF後，再對length取模， &0x7FFFFFFF的目的是為了将負的hash值轉化為正值，因為hash值有可能為負數，而 &0x7FFFFFFF後，隻有符号外改變，而後面的位都不變。

不仔細的看，還以為這個類是線程安全的，因為putIfAbsent方法加了synchronized。不過細心的同學就會發現原來putIfAbsent方法和List并不是使用的同一個鎖對象，List使用的鎖對象并不是BadListHelper，而是list。假如A線程進入putIfAbsent方法，list這個鎖并沒有被擷取（A線程擷取的是 BadListHelper這個對象），是以其他線程還能夠獲得list鎖對象來改變list對象。boolean absent = !list.contains(x);當線程到這串代碼結束時，其他線程獲得list鎖對象，進而就能調用list的方法來改變list對象，這時候就可能導緻!list.contains(x)改變，即域absent并不是A線程得到的布爾類型。是以這個類并不是線程安全的。