線程安全集合類

ArrayList、Queue、HsahMap… 都是線程不安全的

Vector、Stack、Hashtable 都是線程安全的（內置了 synchronized），實際上這幾個東西并不推薦使用

• 因為這幾個都是無腦加 synchronized，無論如何都要加鎖，哪怕單線程也要加鎖，不科學。很有可能出現阻塞，可能會使程序效率大打折扣
• 編譯器的“鎖消除”并不能 100%解決問題，只能把十拿九穩的地方進行優化，有些代碼是鎖消除機制摸不透的

解決方案

多線程環境使用順序表

1. 自己加鎖

• 給 ArrayList 套了個殼。ArrayList 各種操作本身不帶鎖，通過上述套殼之后，得到了新的對象，新的對象里面的關鍵方法都是帶有鎖的

---

3. 使用 CopyOnWriteArrayList

這里面主要用到了“寫實拷貝”

• 線程安全問題，在多個線程修改同一個數據的時候會觸發

• 把順序表復制一份，修改新的順序表內容，然后修改引用的指向，這樣就不會有線程安全問題
  • “修改引用指向”這個操作是原子的，不需要加鎖

這種操作有很大的局限性

1. 修改不能太頻繁（復制開銷很大）
2. 順序表也不應該太大

一般在服務器加載配置文件的時候，就要把配置文件的內容解析出來，放到內存的數據結構中（順序表/哈希表…）

• 服務器的修改頻率很低
• 配置文件一般體積都不大（幾 kb）

多線程環境使用隊列

1. 自己加鎖
2. BlockingQueue（線程安全的）

多線程環境使用哈希表

HashMap 肯定不行，它是線程不安全的。更靠譜的是 Hashtable，其在一些關鍵方法上添加了 synchornized，但這個不好用

• 他倆區別就是有無 synchornized

后來標準庫又引入了一個更好的解決方案：ConcurrentHashMap

ConcurrentHashMap

改進：

1. 縮小鎖的粒度

• Hashtable 是直接在方法上使用 synchornized，相當于是對 this 加鎖，整個哈希表就只有這一把鎖，此時，嘗試修改兩個不同鏈表上的元素，都會觸發鎖沖突（Hashtable 底層實現是數組+鏈表）

• 鎖的粒度很大，是一個全局鎖，同一時刻只能有一個線程訪問整個哈希表。

• 仔細觀察就可以發現，如果修改兩個不同鏈表上的元素，不涉及到線程安全問題（修改不同變量）

  • 如果修改的是同一個鏈表上的元素，就可能涉及到線程安全問題
  • 比如這倆變量在鏈表上的位置是相鄰的，操作引用的時候，就可能涉及到操作同一個引用

• 此時，針對同一個鏈表操作，再加鎖；針對不同鏈表操作，就不必加鎖了（不要產生鎖沖突）

---

ConcurrentHashMap 就是把鎖變小了，給每一個鏈表都發了一個鎖

• 弄出了這么多鎖，會付出更多空間的代價嗎？
  • 不會；Java 中，任何一個對象都可以直接作為鎖對象。本身哈希表中就得有數組，數組的元素都是已經存在的（每個鏈表的頭結點），此時，只要使用數組元素（鏈表頭結點）作為加鎖的對象即可

• 每個鏈表就是構成桶的一個木板。所謂“鎖桶”，就是針對每個木板（每個鏈表）分別加鎖的

在 Java 1.7 及其之前，ConcurrentHashMap 是通過“分段鎖”來實現的

• 給若干個鏈表分配一把鎖
• 這種設定，不太合適，實現更復雜，效率也不夠高，還要引入額外的空間開銷（重新定義鎖）
  從 Java 8 開始，這里的設定就變成每個鏈表一把鎖了

2. 充分使用 CAS

充分使用 CAS 原子操作，減少了一些加鎖

• 比如，針對哈希表元素個數的維護

synchornized 里面不是剛開始是偏向鎖或者輕量級鎖，速度很快嗎？

• synchornized 有可能成為重量級鎖，并且是否升級了不可控

3. 針對擴容操作

擴容是一個重量操作

0.75 是負載因子默認的擴容閾值，不是負載因子本體

• 負載因子是你算出來的數
• 拿著實際的元素個數/數組長度（桶的個數）算出來的數值，這個值可能是 0.1，可能是 0.5 可能是 1，可能是 10
• 然后我們拿著這個值和擴容閾值進行比較，看看是否需要擴容

負載因子：描述了每個桶上面平均有多少個元素

• 此時桶上的鏈表的元素不應該太長，才能保證遍歷的時間復雜度為 $O(1)$

如果太長：

1. 變成樹（長度不平均的情況）
2. 擴容
   • 創建一個更大的數組，把舊的 Hash 表的元素都給搬運到（刪除/插入）到新的數組上
   • 如果 hash 表本身元素非常多，這里的擴容操作就會消耗很長時間
   • hash 表平時都很快，突然間某個操作就變慢了，過一會又快了（表現不穩定，壞事）
   • 我們無法控制何時觸發擴容，一旦觸發擴容，就會導致這次操作非常耗時（用戶直觀感受：卡頓）

---

HashMap 的擴容操作是一把梭哈，在某一次插入元素操作中，整體完成擴容（就會卡頓，耗時）

ConcurrentHashMap 的策略是“化整為零，螞蟻搬家”

• 每次只搬運一部分元素
• 假設有 1kw 個元素，此時擴容的時候，每次插入/查找/刪除，都會搬運一部分元素（每次搬運 5k 個元素），一共花 2k 次搬完（花的時間更長，但是值得）
• 確保每操作消耗的時間都不會很長，避免出現很卡的情況

在擴容過程中，同時存在兩份哈希表，一份是新的，一份是舊的

• 插入操作：直接往新的上插入
• 刪除操作：新的舊的都直接刪除
• 查找操作：新的舊的都要查詢一下