一. 如何實(shí)現(xiàn)一個(gè)線程安全的數(shù)據(jù)結(jié)構(gòu)

1.餓漢模式

public class Singletan {
    private static Singletan instance = new Singletan();    
    public Singletan(){}    
    public static Singletan getInstance() {
        return instance;
    }
}

2.靜態(tài)內(nèi)部類

//加載內(nèi)部類SingletanHolder，從而實(shí)例化instance
public class Singletan {
    private static class SingletanHolder {
        private static final Singletan INSTANCE = new Singletan();
    }
    public Singletan(){}
    public static final Singletan getInstance() {
        return SingletanHolder.INSTANCE;
    }
}

3.CAS：Compare and Swap（比較和交換）

• 樂(lè)觀鎖，無(wú)鎖算法。CAS有3個(gè)參數(shù)：內(nèi)存值V、舊值A(chǔ)、要修改的新值B，當(dāng)且僅當(dāng)舊值 A 和內(nèi)存值 V 相同時(shí)，才將內(nèi)存值 V 修改為 B，否則會(huì)嘗試重新獲取 V 的當(dāng)前值，重新比較。
• 優(yōu)點(diǎn)：沒(méi)有線程切換和阻塞的額外開(kāi)銷，支持較大并行度。
• 缺點(diǎn)：①在并發(fā)量較高時(shí)，如果許多線程反復(fù)嘗試去更新一個(gè)變量，卻又一直更新失敗，會(huì)消耗很多CPU資源。②銀行取款 ABA 問(wèn)題，所以不僅要比較舊值和內(nèi)存值，還要比較變量的版本號(hào)是否一致，只有一致才進(jìn)行操作。

銀行取款A(yù)BA問(wèn)題：假如賬戶開(kāi)始有100元，在取款機(jī)上取走50，取款機(jī)出現(xiàn)問(wèn)題一共提交了兩次請(qǐng)求（線程1，線程2），第二次請(qǐng)求（線程2）在執(zhí)行時(shí)因?yàn)槟撤N原因被阻塞了，這時(shí)候有人往你的賬戶打了50元，線程2恢復(fù)了可執(zhí)行狀態(tài)，這個(gè)時(shí)候就會(huì)出現(xiàn)問(wèn)題，原本線程2應(yīng)該執(zhí)行失敗的，但是比較后仍然與舊值一致，這樣就造成了賬戶實(shí)際上扣款了兩次！

二.Java中滿足線程安全的數(shù)據(jù)結(jié)構(gòu)

所謂 線程安全 就是：一段操縱共享數(shù)據(jù)的代碼能夠保證在同一時(shí)間內(nèi)被多個(gè)線程執(zhí)行而仍然保持其正確性的，就被稱為是線程安全的。

線程安全是保證執(zhí)行業(yè)務(wù)邏輯正確的基本前提，為此在多線程開(kāi)發(fā)中，我們盡量采用能保證線程安全的數(shù)據(jù)結(jié)構(gòu)。

JDK已經(jīng)為大家準(zhǔn)備好了一批好用的線程安全容器類，可以大大減少開(kāi)發(fā)工作量，例如HashTable，ConcurrentHashMap，CopyOnWriteArrayList，CopyOnWriteArraySet，ConcurrentLinkedQueue，Vector，StringBuffer等。本文主要對(duì)這些數(shù)據(jù)結(jié)構(gòu)的功能及其常見(jiàn)使用場(chǎng)景進(jìn)行說(shuō)明與比較。

在這里插入圖片描述

1、HashTable

HashTable實(shí)現(xiàn)了Map接口，為此其本身也是一個(gè)散列表，它存儲(chǔ)的內(nèi)容是基于key-value的鍵值對(duì)映射。

HashTable中的key、value都不可以為null；具有無(wú)序特性；由于其方法函數(shù)都是同步的（采用synchronized修飾），不會(huì)出現(xiàn)兩個(gè)線程同時(shí)對(duì)數(shù)據(jù)進(jìn)行操作的情況，因此保證了線程安全性。

HashTable使用synchronized來(lái)修飾方法函數(shù)來(lái)保證線程安全，但是在多線程運(yùn)行環(huán)境下效率表現(xiàn)非常低下。因?yàn)楫?dāng)一個(gè)線程訪問(wèn)HashTable的同步方法時(shí)，其他線程也訪問(wèn)同步方法就會(huì)粗線阻塞狀態(tài)。比如當(dāng)一個(gè)線程在添加數(shù)據(jù)時(shí)候，另外一個(gè)線程即使執(zhí)行獲取其他數(shù)據(jù)的操作也必須被阻塞，大大降低了程序的運(yùn)行效率。

2、ConcurrentHashMap

我們知道HashMap是線程不安全的，ConcurrentHashMap是HashMap的線程安全版。

但是與HashTable相比，ConcurrentHashMap不僅保證了多線程運(yùn)行環(huán)境下的數(shù)據(jù)訪問(wèn)安全性，而且性能上有長(zhǎng)足的提升。

ConcurrentHashMap允許多個(gè)修改操作并發(fā)運(yùn)行，其原因在于使用了鎖分段技術(shù)：首先講Map存放的數(shù)據(jù)分成一段一段的存儲(chǔ)方式，然后給每一段數(shù)據(jù)分配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段的數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)。這樣就保證了每一把鎖只是用于鎖住一部分?jǐn)?shù)據(jù)，那么當(dāng)多線程訪問(wèn)Map里的不同數(shù)據(jù)段的數(shù)據(jù)時(shí)，線程間就不會(huì)存在鎖競(jìng)爭(zhēng)，從而可以有效提高并發(fā)訪問(wèn)效率。

上述的處理機(jī)制明顯區(qū)別于HashTable是給整體數(shù)據(jù)分配了一把鎖的處理方法。為此，在多線程環(huán)境下，常用ConcurrentHashMap在需要保證數(shù)據(jù)安全的場(chǎng)景中去替換HashMap，而不會(huì)去使用HashTable，同時(shí)在最新版的JDK中已經(jīng)推薦廢棄使用HashTable。

3、CopyOnWriteArrayList

CopyOnWriteArrayList實(shí)現(xiàn)了List接口，提供的數(shù)據(jù)更新操作都使用了ReentrantLock的lock()方法來(lái)加鎖，unlock()方法來(lái)解鎖。

當(dāng)增加元素的時(shí)候，首先使用Arrays.copyOf()來(lái)拷貝形成新的副本，在副本上增加元素，然后改變?cè)弥赶蚋北?。讀操作不需要加鎖，而寫操作類實(shí)現(xiàn)中對(duì)其進(jìn)行了加鎖。因此，CopyOnWriteArrayList類是一個(gè)線程安全的List接口的實(shí)現(xiàn)，在高并發(fā)的情況下，可以提供高性能的并發(fā)讀取，并且保證讀取的內(nèi)容一定是正確的，這對(duì)于讀操作遠(yuǎn)遠(yuǎn)多于寫操作的應(yīng)用非常適合（注意： 如上述更新操作會(huì)帶來(lái)較大的空間與性能開(kāi)銷，如果更新操太過(guò)頻繁，反而不太合適使用）。

4、CopyOnWriteArraySet

CopyOnWriteArraySet是對(duì)CopyOnWriteArrayList使用了裝飾模式后的具體實(shí)現(xiàn)。所以CopyOnWriteArrayList的實(shí)現(xiàn)機(jī)理適用于CopyOnWriteArraySet，此處不再贅述。

Java里的List和Set的之間的特性比較結(jié)論同樣適用于CopyOnWriteArrayList與CopyOnWriteArraySet之間的比較；此外，CopyOnWriteArrayList與CopyOnWriteArraySet都是線程安全的。

5、ConcurrentLinkedQueue

ConcurrentLinkedQueue可以被看作是一個(gè)線程安全的LinkedList，使用了非阻塞算法實(shí)現(xiàn)的一個(gè)高效、線程安全的并發(fā)隊(duì)列；其本質(zhì)是一個(gè)基于鏈接節(jié)點(diǎn)的無(wú)界線程安全隊(duì)列，它采用先進(jìn)先出的規(guī)則對(duì)節(jié)點(diǎn)進(jìn)行排序，當(dāng)添加一個(gè)元素時(shí)會(huì)添加到隊(duì)列的尾部；當(dāng)獲取一個(gè)元素時(shí)，會(huì)返回隊(duì)列頭部的元素。

ConcurrentLinkedQueue應(yīng)該算是在高并發(fā)環(huán)境中性能最好的隊(duì)列，沒(méi)有之一。

6、Vector

Vector通過(guò)數(shù)組保存數(shù)據(jù)，繼承了Abstract，實(shí)現(xiàn)了List；所以，其本質(zhì)上是一個(gè)隊(duì)列。

但是和ArrayList不同，Vector中的操作是線程安全的，它是利用synchronized同步鎖機(jī)制進(jìn)行實(shí)現(xiàn)，其實(shí)現(xiàn)方式與HashTable類似。

7、StringBuffer與StringBuilder

在Java里面，字符串操作應(yīng)該是最頻繁的操作了，為此有必要把StringBuffer與StringBuilder兩個(gè)方法類比較一下。

首先，對(duì)于頻繁的字符串拼接操作，是不推薦采用效率低下的“+”操作的。一般是采用StringBuffer與StringBuilder來(lái)實(shí)現(xiàn)上述功能。但是，這兩者也是有區(qū)別的：前者線程安全，后者不是線程安全的。

StringBuffer是通過(guò)對(duì)方法函數(shù)進(jìn)行synchronized修飾實(shí)現(xiàn)其線程安全特性，實(shí)現(xiàn)方式與HashTable、Vector類似。

總結(jié)：

1. HashTable是線程安全類；通過(guò)對(duì)其方法函數(shù)進(jìn)行synchronized修飾實(shí)現(xiàn)其特性，效率低下，目前已被jdk廢棄，不再推薦使用。
2. 在多線程環(huán)境下，我們常用ConcurrentHashMap在需要保證數(shù)據(jù)安全的場(chǎng)景中去替換HashMap；此外ConcurrentHashMap也有不錯(cuò)的性能表現(xiàn)
3. CopyOnWriteArrayList類是一個(gè)線程安全的List接口的實(shí)現(xiàn)，在高并發(fā)的情況下，可以提供高性能的并發(fā)讀取，并且保證讀取的內(nèi)容一定是正確的，這對(duì)于讀操作遠(yuǎn)遠(yuǎn)多于寫操作的應(yīng)用非常適合。
4. CopyOnWriteArraySet是對(duì)CopyOnWriteArrayList使用了裝飾模式后的具體實(shí)現(xiàn)，可理解為線程安全的Set。
5. ConcurrentLinkedQueue應(yīng)該算是在高并發(fā)環(huán)境中性能最好的隊(duì)列；在多線程的隊(duì)列應(yīng)用場(chǎng)景中，強(qiáng)烈推薦使用。
6. Vector中的操作是線程安全的，它是利用synchronized同步鎖機(jī)制進(jìn)行實(shí)現(xiàn)，其實(shí)現(xiàn)方式與HashTable類似。
7. StringBuffer與StringBuilder常用于字符串拼接；前者線程安全，后者不是線程安全的；在多線程環(huán)境中下，考慮數(shù)據(jù)安全使用前者，否則使用后者。