Java中的Map & CAS & AQS
Java中的Map
1.基本介紹和api使用就免了
Java中的Map是一種用于存儲鍵值對（Key-Value）的接口，屬于java.util包，是集合框架的重要組成部分。
2.HashMap
從圖中的關系可以看出這些類間關系了。
①基本分析
HashMap的一些屬性
// 默認容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/*最大容量*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**負載因子*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/*使用樹而不是列表的bin計數閾值。當向至少有這么多節點的桶中添加元素時，桶將轉換為樹。該值必須大于2，并且應該至少為8，*/
static final int TREEIFY_THRESHOLD = 8;
//HashMap紅黑樹退化成鏈表的臨界值
static final int UNTREEIFY_THRESHOLD = 6;
//HashMap鏈表升級成紅黑樹第二個條件：HashMap數組(桶)的長度大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;
/* ---------------- Fields -------------- */
/*實際的鍵值對。在分配時，長度總是2的冪。*/
transient Node<K,V>[] table;
/*保存緩存的entrySet（*/
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
靜態內部類Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // hash值
final K key; //
V value;
Node<K,V> next; // 下一個元素
}
這個靜態內部類很簡單吧。
public V put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 計算hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1.如果此時的table還沒有初始化，就執行resize()操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.如果【計算的hash映射的位置沒有元素】，就直接把元素放在上面
// p是hash計算的下標所在位置的元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 3.【如果有沖突！！！！！！】
else {
Node<K,V> e; K k;
// 【3.1】 如果p元素的hash值和put進來的hash相等，并且equals也相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 【3.2】3.1如果是false，如果p是樹節點類型的
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 【3.3】如果是普通節點類型
// 下面可以看出是鏈表的尾插法！
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表上元素數量如果快要達到閾值了，就轉換為樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果鏈表上的節點與要插入的完全相同，就跳過
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 這里可以看到，如果存在一模一樣的，新值會替換到舊值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent傳過來的是false
if (!onlyIfAbsent || oldValue == null)
e.value = value; // 如果不存在一模一樣的，那么這句話執不執行都一樣了
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize(); // 擴容
afterNodeInsertion(evict);
return null;
}
擴容機制resize();
HashMap 的擴容機制是為了在元素數量增加時，維持合理的負載因子，減少哈希沖突，從而保證 HashMap 的性能。
new了一個HashMap對象的時候，第一次put才會去初始化tab的Node數組，這時就會 負載因子 * 容量。【延遲初始化，嘿嘿嘿】
- 容量（Capacity）：指 HashMap 內部數組的大小。初始容量默認為 16，并且必須是 2 的冪次方。
- 負載因子（Load Factor）：衡量 HashMap 滿的程度，默認為 0.75。它表示當 HashMap 中的元素數量達到容量的
負載因子 * 容量時，就會觸發擴容。 - 閾值（Threshold）：等于
負載因子 * 容量。當 HashMap 中的元素數量達到閾值時，就會進行擴容。
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
threshold = newThr;
擴容過程
- 創建新數組：擴容時，會創建一個新的數組，新數組的容量是原數組容量的 2 倍。例如，原數組容量為 16，擴容后新數組容量為 32。
- 重新計算哈希值和索引：將原數組中的所有鍵值對重新計算哈希值，并根據新數組的容量重新確定它們在新數組中的索引位置。這是因為數組容量變化后，
hash & (length - 1)的結果會改變。- 遷移元素：遍歷原數組，將每個桶（bucket，即數組中的每個位置）中的元素重新插入到新數組的相應位置。如果桶中只有一個元素，直接計算新索引插入即可。如果桶中是鏈表結構（JDK 1.7 及之前）或紅黑樹結構（JDK 1.8 及之后，當鏈表長度大于 8 且數組容量大于 64 時會轉換為紅黑樹），則需要對鏈表或紅黑樹中的每個元素重新計算索引并插入到新數組對應位置。
final Node<K,V>[] resize() {
......
// 創建新數組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
// 重新計算hash
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 元素遷移【可以理解為我不想接著看源碼了】
........
}
}
}
}
return newTab;
}
V get(Object key)獲取元素
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1.判空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 2.1如果hash第一個位置就是的
return first;
if ((e = first.next) != null) {
// 2.1 找樹，找鏈表,很簡單嘛
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
通過源碼可以看出，對于key為null，計算hash的時候返回就是0，
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
value = null，那就無所謂了。
Map<String, String> m = new HashMap<>(10);
m.put("a", "a");
m.put(null, "b");
m.put(null, "c");
m.put("c", null);
m.get("a");
String s = m.get(null);
System.out.println(s);
②一些問題
為什么HashMap的Node數組長度必須是2的n次冪？
在計算存入結點下標時，會利用 key 的 hsah 值進行取余操作，而計算機計算時，并沒有取余等運算，會將取余轉化為其他運算。
/*
具體公式為 index = hash & (length - 1)，這里length是 HashMap 的長度。
如果length是 2 的次冪，那么length - 1的二進制形式就是所有位都為 1。
例如，若length為 16（二進制10000），length - 1就是 15（二進制01111）。
這樣做使得hash & (length - 1)等價于hash % length，但按位與運算比取模運算效率更高。
舉例子：hash=20 length=16 h % l = 4 <==> 20&15 = 4
*/
HashMap不是有一個構造函數可以指定初始容量嗎？我給一個不是2的n次冪你不就炸了？
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 求第一個大于cap的二次冪
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; // 【無符號右移，最高位補0】
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
看得懂不？
Map<String, String> m = new HashMap<>(10);
// new的時候 threshold = 16
// 在第一次put的時候，resize()，實際底層Node是16的長度，threshold = 16 * 0.75 = 12
/*
假設給定的初始值是10(1010)【非二次冪】
n = 10 - 1 = 9 (1001)
n |= n >>> 1 ====> 1001 | 0100 = 1101
n |= n >>> 2 ====> 1101 | 0011 = 1111
.....（同理）
最后 n = 1111
n+1 = 10000(第一個大于n的二次冪)
*/
你傳任你傳，我自有辦法變成二次冪！！！
3.HashTable
HashTable 是 Java 中的一個古老的鍵值對存儲類，它是線程安全的，但現在已經不常用了。
Hashtable采用 “數組 + 鏈表” 的結構來存儲鍵值對 。它內部維護了一個Entry類型的數組table，數組的每個元素都是一個鏈表的頭節點。當有新的鍵值對要插入時，會根據鍵的哈希值計算出在數組中的索引位置，然后將鍵值對插入到對應索引位置的鏈表中。如果發生哈希沖突（即不同的鍵計算出了相同的索引），則通過鏈表來解決沖突，新的鍵值對會被添加到鏈表的頭部。
Hashtable通過synchronized關鍵字來保證線程安全。幾乎所有對Hashtable進行修改（如put、remove等）和部分讀取（如get）操作的方法都被synchronized修飾。這意味著在任何時刻，只能有一個線程能夠訪問Hashtable的這些同步方法，從而避免了多線程環境下的數據不一致問題。
public synchronized V put(K key, V value) {
// 檢查鍵是否為null，不允許null鍵
if (key == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
// 遍歷鏈表查找鍵或插入新鍵值對
for (Entry<K, V> e = (Entry<K, V>) tab[index]; e!= null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// 擴容
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 創建新的Entry并插入鏈表頭部
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
看了源碼，不允許 null 鍵值：Hashtable不允許使用null作為鍵或值。如果嘗試插入null鍵或null值，會拋出NullPointerException。這在某些場景下不夠靈活，相比之下，HashMap允許一個null鍵和多個null值。
import java.util.Hashtable;
public class HashTableExample {
public static void main(String[] args) {
Hashtable<String, Integer> hashtable = new Hashtable<>();
// 添加鍵值對
hashtable.put("one", 1);
hashtable.put("two", 2);
hashtable.put("three", 3);
//hashtable.put(null, 444); // ============== no！！
// 獲取值
System.out.println(hashtable.get("two")); // 輸出: 2
// 遍歷
for (String key : hashtable.keySet()) {
System.out.println(key + ": " + hashtable.get(key));
}
}
}
4.TreeMap
TreeMap是 Java 集合框架中Map接口的一個實現類，它基于紅黑樹（一種自平衡的二叉搜索樹）來實現鍵值對的存儲和操作。這使得TreeMap在插入、刪除和查找操作上都具有較好的性能，時間復雜度為 O (log n)，其中 n 是TreeMap中鍵值對的數量。
TreeMap的一個重要特點是它會對鍵進行排序。排序方式有兩種：
- 自然排序：如果鍵的類型實現了
Comparable接口，TreeMap會按照鍵的自然順序進行排序。例如，如果鍵是Integer類型，那么TreeMap會按照數字大小對鍵進行升序排列；如果鍵是String類型，則會按照字典序進行排序。【默認自然升序】 - 定制排序：可以在創建
TreeMap時傳入一個Comparator接口的實現類，通過該比較器來定義鍵的排序規則。這使得TreeMap可以對不具備自然排序能力的對象進行排序，或者按照自定義的規則對可自然排序的對象進行排序。
看源碼得知，key不能為null！！！
如果是自定義key的類型。
- 要么Key對象實現
Comparable接口，定義排序邏輯
public void testTreeMap() {
Map<Student, String> m = new TreeMap<>((o1, o2) -> {
if (o1.getAge() == o2.getAge()) return 0;
return o1.getAge() > o2.getAge() ? -1 : 1; // 返回1,排后面兒去， -1排前面
});
m.put(new Student("a", 10), "a");
m.put(new Student("b", 2), "b");
m.put(new Student("c", 15), "c");
System.out.println(m); // c, a, b
}
- 要么傳入
Comparator接口的實現類，里面定義排序邏輯
public class Student implements Comparable<Student>{
private String name;
private int age;
@Override
public int compareTo(Student o) {
if (this.getAge() == o.getAge()) return 0;
return this.getAge() > o.getAge() ? 1 : -1;
}
}
public static void testTreeMap() {
Map<Student, String> m = new TreeMap<>();
m.put(new Student("a", 10), "a");
m.put(new Student("b", 2), "b");
m.put(new Student("c", 15), "c");
System.out.println(m); // b, a, c
}
5.juc的Map
說實話，寫到這兒有點累了。。。
①synchronizedMap
synchronizedMap 是 Java 中通過 Collections 工具類提供的一個線程安全的 Map 實現，用于將普通的 Map（如 HashMap）包裝成一個線程安全的版本。它的核心思想是通過 同步鎖（synchronized） 保證多線程環境下的安全性
Collections.synchronizedMap() 方法返回一個包裝類，其內部通過 同步代碼塊（synchronized） 對原始 Map 的所有操作進行加鎖。這個里面的同步安全集合類實現原理都類似啊。
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
// 內部類
static class SynchronizedMap<K,V> implements Map<K,V> {
private final Map<K,V> m; // 被包裝的原始 Map
final Object mutex; // 同步鎖對象
public V put(K key, V value) {
synchronized (mutex) { // 所有操作加鎖
return m.put(key, value);
}
}
public int size() {
synchronized (mutex) {return m.size();}
}
public boolean isEmpty() {
synchronized (mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
synchronized (mutex) {return m.containsKey(key);}
}
public boolean containsValue(Object value) {
synchronized (mutex) {return m.containsValue(value);}
}
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}
...........................
// 其他方法也通過 synchronized 同步
} // 實現原理是不是簡單粗暴
- 與
Hashtable相比：Collections.synchronizedMap可以基于任何Map實現類（如HashMap、TreeMap）創建線程安全的Map，而Hashtable本身是一個特定的線程安全Map實現類，并且Hashtable不允許null鍵和null值，Collections.synchronizedMap基于的HashMap允許null鍵和null值（如果基于TreeMap則不允許null鍵）。兩者在同步機制上類似，都是基于synchronized關鍵字，但Collections.synchronizedMap更靈活。 - 與
ConcurrentHashMap相比：ConcurrentHashMap在高并發環境下性能更好。ConcurrentHashMap在 Java 7 及之前采用分段鎖機制，Java 8 及之后采用 CAS 和synchronized相結合的方式，允許多個線程同時進行讀操作，部分線程進行寫操作，而Collections.synchronizedMap同一時間只能有一個線程進行操作。所以在高并發場景下，ConcurrentHashMap更適合。
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class SynchronizedMapExample {
public static void main(String[] args) {
// 創建一個普通 HashMap
Map<String, Integer> map = new HashMap<>();
// 包裝為線程安全的 Map
Map<String, Integer> syncMap = Collections.synchronizedMap(map);
// 多線程操作
Runnable task = () -> {
for (int i = 0; i < 1000; i++) {
syncMap.put(Thread.currentThread().getName() + i, i);
}
};
Thread t1 = new Thread(task);
Thread t2 = new Thread(task);
t1.start();
t2.start();
try {
t1.join();
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Map size: " + syncMap.size()); // 輸出: 2000
}
}
②ConcurrentHashMap
見后續并發相關文章
③ConcurrentSkipListMap
見后續并發相關文章。
6.補充知識點簡介
原本是想在寫完ConcurrentHashMap后，把cas補上，誰知道先寫了cas，aqs。。。。
①CAS
CAS 通常指 “Compare and Swap”（比較并交換） ，這是一種用于實現多線程同步的原子操作
他的主要機制：CAS 操作涉及三個操作數，分別是內存位置（V）、預期原值（A）和新值（B） 。當執行 CAS 操作時，它會先檢查 V 處的值是否等于 A。如果相等，就將 V 處的值更新為 B；如果不相等，就不進行任何操作。整個操作是原子的，在多線程環境下能保證數據一致性。CAS是一個無鎖機制的操作，底層是通過Unsafe類使用native本地方法進行的CAS操作，但是在操作系統層面，在操作系統層面，CAS還是會加鎖的，通過加鎖的方式鎖定總線，避免其他CPU訪問共享變量。
Unsafe類
Unsafe類是JDK提供的一個不安全的類，它提供了一些底層的操作，包括內存操作、線程調度、對象實例化等。它的作用是讓Java可以在底層直接操作內存，從而提高程序的效率。CAS操作是基于底層硬件支持的原子性指令來實現的，所以它可以保證操作的原子性和線程安全性，同時也可以避免使用鎖帶來的性能開銷。
在 Unsafe 類中，提供了compareAndSwapObject、compareAndSwapInt、compareAndSwapLong方法來實現的對Object、int、long類型的 CAS 操作
public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);
參數說明
| 參數 | 類型 | 說明 |
|---|---|---|
o |
Object | 目標對象（包含需要修改的字段的實例）。 |
offset |
long | 目標字段在對象內存中的偏移量（通過 Unsafe.objectFieldOffset 獲取）。 |
expected |
int | 期望的字段當前值（用于比較）。 |
x |
int | 要更新的新值。 |
offset獲取，在AtomicInteger源碼中可以看出。
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;
舉個例子：假設有一個共享變量 count，初始值為 0。線程 1 想要將 count 的值加 1。它會使用 CAS 操作，預期原值 A 為 0，新值 B 為 1。如果此時內存中 count 的值確實為 0（即與預期原值相等），那么就會將 count 更新為 1。。若在這期間，線程 2 也對 count 進行了操作，使得 count 的值變為 1，那么線程 1 的 CAS 操作就不會成功，因為此時內存中的值（1）與預期原值（0）不相等。
在我大Java中，肯定有其身影。原子類：Java 的java.util.concurrent.atomic包中，很多原子類（如AtomicInteger、AtomicLong等）就是基于 CAS 實現的。
private static void testAtomicInteger() {
AtomicInteger atomicInteger = new AtomicInteger(1);
atomicInteger.getAndSet(20);
System.out.println(atomicInteger.get());
}
自旋鎖：(死循環?) 基于 CAS 可以實現自旋鎖。自旋鎖是一種非阻塞鎖，線程在獲取鎖失敗時，不會進入阻塞狀態，而是不斷嘗試獲取鎖（即自旋），直到獲取到鎖為止。
public class SpinLock {
private AtomicReference<Thread> owner = new AtomicReference<>();
public void lock() {
Thread current = Thread.currentThread();
while (!owner.compareAndSet(null, current)) {
// 自旋等待
}
}
public void unlock() {
Thread current = Thread.currentThread();
owner.compareAndSet(current, null);
}
}
存在的問題：
- 其實可以很明顯的看出他的問題嚯。在基于 CAS 實現的自旋鎖中，當一個線程嘗試獲取鎖失敗時，它會在一個循環中不斷重試，即自旋。如果自旋時間過長，會浪費大量的 CPU 資源，降低系統整體性能。假設有多個線程競爭一個資源，并且持有鎖的線程執行時間較長。那么其他競爭線程會持續自旋等待獲取鎖，在這個過程中，它們不斷消耗 CPU 資源，卻沒有實際的工作進展。如果自旋的線程數量較多，會導致 CPU 使用率急劇上升，影響整個系統的響應速度.針對這個。我們可以
- 自適應自旋：自旋時間不再固定，而是根據前一次在同一個鎖上的自旋時間以及鎖的擁有者的狀態來調整。例如，如果前一次自旋成功獲取到鎖，那么下一次自旋時間可以適當延長；如果自旋多次都未能獲取到鎖，那么可以減少自旋時間甚至不再自旋，直接進入阻塞狀態。
- 設置自旋次數上限：給自旋設置一個最大次數，當自旋次數達到上限后，線程就不再自旋，而是進入阻塞狀態。這樣可以避免線程無限制地自旋，減少 CPU 資源的浪費。
-
第二，只能保證一個共享變量的原子操作。CAS 操作只能對單個共享變量進行原子更新。如果需要對多個共享變量進行原子操作，單純使用 CAS 無法滿足需求。針對這個問題，我們可以將多個變量合并成一個：如果多個變量之間存在一定的邏輯關系，可以將它們合并成一個對象，然后對這個對象使用
AtomicReference來保證原子性操作。例如，將x和y封裝在一個自定義類中，然后使用AtomicReference<CustomClass>來操作這個類的實例。 -
第三，ABA 問題：CAS 操作在檢查值是否為預期值 A 時，如果值在檢查和更新之間經歷了從 A 變為 B 再變回 A 的過程，CAS 操作依然會認為值沒有改變而成功執行更新。但實際上，這個值已經發生了變化，可能會導致一些隱藏的錯誤。針對這個問題。
- 使用版本號：在每次數據更新時，版本號加 1。這樣即使值變回原來的樣子，但版本號已經改變，CAS 操作會失敗。例如，在 Java 的
AtomicStampedReference類中，就通過維護一個 “戳”（stamp）來解決 ABA 問題。每次更新數據時，不僅更新數據值，也更新戳。在進行 CAS 操作時，同時比較數據值和戳，只有兩者都匹配才執行更新。- 使用時間戳：類似于版本號，通過記錄數據的修改時間來標記數據的變化。每次更新數據時更新時間戳，在進行 CAS 操作時比較時間戳，若時間戳不一致則不執行更新。
②AQS
- 公平鎖和非公平鎖
公平鎖是指在鎖的競爭中，按照請求鎖的先后順序來分配鎖，即先請求鎖的線程會先獲得鎖。這就像排隊一樣，先來的人先得到服務。
優點：公平鎖保證了線程獲取鎖的公平性，避免了線程饑餓（某個線程長時間無法獲取鎖）的問題。
缺點：由于需要維護等待隊列和按照順序喚醒線程，公平鎖的實現開銷較大，性能相對較低。特別是在高并發場景下，頻繁的線程切換會導致系統開銷增加。
private static ReentrantLock fairLock = new ReentrantLock(true); // 公平鎖
public static void main(String[] args) {
Thread[] threads = new Thread[5];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(() -> {
fairLock.lock();
try {
System.out.println(Thread.currentThread().getName() + " 獲得了鎖");
// 模擬業務邏輯
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
fairLock.unlock();
}
});
threads[i].start();
}
}
//多個線程競爭鎖時，會按照請求鎖的先后順序依次獲得鎖。
非公平鎖在鎖可用時，不考慮等待隊列中線程的等待順序，任何一個線程都有機會競爭并獲得鎖。也就是說，新請求鎖的線程可能會在等待隊列中的線程之前獲得鎖。
優點：非公平鎖的實現開銷相對較小，因為它不需要嚴格按照順序喚醒線程。在高并發場景下，由于減少了線程切換的開銷，性能通常比公平鎖更好。
缺點：非公平鎖可能導致部分線程長時間無法獲得鎖，即線程饑餓問題。特別是在有大量線程頻繁請求鎖的情況下，一些新線程可能會不斷搶占鎖，使得等待隊列中的線程長時間得不到執行機會。
private static ReentrantLock unfairLock = new ReentrantLock(false); // false
public static void main(String[] args) {
Thread[] threads = new Thread[5];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(() -> {
unfairLock.lock();
try {
System.out.println(Thread.currentThread().getName() + " 獲得了鎖");
// 模擬業務邏輯
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
unfairLock.unlock();
}
});
threads[i].start();
}
}
- aqs基本介紹
AQS 即 AbstractQueuedSynchronizer【抽象隊列同步器】，是 Java 并發包中很多同步器實現的基礎框架，如ReentrantLock、Semaphore、CountDownLatch等。AQS作為一個抽象類，通常是通過繼承來使用的。它本身是沒有同步接口的，只是定義了同步狀態和同步獲取和同步釋放的方法。
主要用途： 用于構建鎖和同步器，它提供了一種在多線程環境下管理同步狀態（state）、線程排隊等待以及線程喚醒的機制。
public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer
implements java.io.Serializable {
// 內部類Node
static final class Node {
.....
volatile Node prev;
volatile Node next;
volatile Thread thread;
}
// 維護了一個邏輯上的基于雙向鏈表的隊列
private transient volatile Node head;
private transient volatile Node tail;
// The synchronization state.
private volatile int state;
.......
}
從上面可以看到，雙向鏈表有兩個指針，一個指針指向前置節點，一個指針指向后繼節點。這是一個虛擬的雙向隊列，用于存放等待獲取同步狀態的線程。隊列節點（Node）包含了線程引用、等待狀態等信息。當一個線程無法獲取同步狀態時，它會被封裝成一個Node加入到隊列尾部，并進入等待狀態。當同步狀態可用時，隊列頭部的線程會被喚醒嘗試獲取同步狀態。
AQS使用一個volatile的int類型的成員變量state來表示同步狀態，通過CAS修改同步狀態的值。當線程調用 lock 方法時 ，如果 state=0，說明沒有任何線程占有共享資源的鎖，可以獲得鎖并將 state加1。如果 state不為0，則說明有線程目前正在使用共享變量，其他線程必須加入同步隊列進行等待。我們開發者只需關注具體同步邏輯（如獲取和釋放同步狀態的條件），而無需關注線程排隊、等待和喚醒等底層細節。
為啥是雙向鏈表嘞？
- 找前驅的便利
首先，AQS節點有CANCELLED、SIGNAL、CONDITION等狀態，處理這些狀態時需頻繁調整節點鏈接。線程可能因中斷或超時被取消排隊，需從隊列中移除，這個時候雙向操作靈活性，將節點從隊列中移除時，需同時更新前驅節點的next和后繼節點的prev，雙向鏈表更容易定位到前驅結點。雙向鏈表通過prev指針可直接定位前驅節點，調整指針即可完成刪除；單向鏈表需遍歷查找前驅節點，時間復雜度為O(n)。
雙向鏈表在面對各種異常情況（如節點突然取消等待、線程意外中斷等）時，能更好地保證鏈表結構的完整性和一致性。因為雙向鏈表的結構特點使得在任何節點出現問題時，都能方便地從前后兩個方向對鏈表進行調整。
沒有競爭到鎖的線程加入到阻塞隊列，并且阻塞等待的前提是，當前線程所在節點的前置節點是正常狀態，這樣設計是為了避免鏈表中存在異常線程導致無法喚醒后續線程的問題。所以，線程阻塞之前需要判斷前置節點的狀態，如果沒有指針指向前置節點，就需要從 Head 節點開始遍歷，性能非常低。
- aqs類分析
public abstract class AbstractQueuedSynchronizer
extends AbstractOwnableSynchronizer implements java.io.Serializable {
private static final long serialVersionUID = 7373984972572414691L;
// 內部類
static final class Node { ... }
// 維護了一個邏輯上的基于雙向鏈表的隊列
private transient volatile Node head;
private transient volatile Node tail;
// The synchronization state.
private volatile int state; // get set方法略去
// 這里用到了cas
protected final boolean compareAndSetState(int expect, int update) {
return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
//......
// ======================【重要的方法 [子類去實現]】#####！！！！
// 嘗試以獨占模式獲取。該方法應該查詢對象的狀態是否允許以獨占模式獲取它，如果允許則獲取它。
protected boolean tryAcquire(int arg) {
throw new UnsupportedOperationException();
}
// 嘗試以獨占模式釋放
protected boolean tryRelease(int arg) {
throw new UnsupportedOperationException();
}
// 在共享模式下嘗試獲取。該方法應該查詢對象的狀態是否允許以共享模式獲取它，如果允許則獲取它。
//此方法總是由執行acquire的線程調用。
//如果此方法報告失敗，則acquire方法可能會將線程（如果尚未排隊）放入隊列，直到其他線程發出釋放信號為止。
protected int tryAcquireShared(int arg) {
throw new UnsupportedOperationException();
}
// 同理
protected boolean tryReleaseShared(int arg) {
throw new UnsupportedOperationException();
}
// 如果獨占同步，則為True;否則 false
protected boolean isHeldExclusively() {
throw new UnsupportedOperationException();
}
// ==================
// 重要的模板方法 ,子類可見，但是不允許重寫
//====================
//============================================= 獨占式
/*
acquire 方法構成了獲取獨占式同步狀態的算法骨架。
它首先調用 tryAcquire(arg) 嘗試獲取同步狀態，這個方法是抽象的，需要子類去實現，以定義具體的獲取同步狀態邏輯。
如果 tryAcquire(arg) 返回 false，表示獲取失敗，則通過 addWaiter(Node.EXCLUSIVE) 將當前線程封裝成節點加入等待隊列，然后調用 acquireQueued(addWaiter(Node.EXCLUSIVE), arg) 方法在隊列中等待獲取同步狀態。
selfInterrupt() 方法用于在必要時設置線程的中斷狀態。
*/
public final void acquire(int arg) {
// 獨占式獲取同步狀態，如果獲取失敗則進入等待隊列。
// 首先調用tryAcquire(arg)方法嘗試獲取同步狀態，該方法需要子類實現。如果獲取成功，acquire方法直接返回。
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
// 獨占式獲取同步狀態，在獲取過程中可以響應中斷
public final void acquireInterruptibly(int arg)
throws InterruptedException {
if (Thread.interrupted()) // 首先檢查當前線程是否已被中斷
throw new InterruptedException();
if (!tryAcquire(arg))
//如果tryAcquire(arg)返回false，則通過addWaiter(Node.EXCLUSIVE)方法
//將當前線程封裝成一個"獨占式節點"并添加到等待隊列尾部。
doAcquireInterruptibly(arg); // 這個方法里面
}
/*
在等待隊列中循環等待獲取同步狀態，每次循環會計算剩余時間nanosTimeout = deadline - System.nanoTime()。
如果剩余時間小于等于 0，則返回false表示獲取超時。如果在等待過程中獲取到同步狀態，則返回true。
*/
public final boolean tryAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {
if (Thread.interrupted())
throw new InterruptedException();
return tryAcquire(arg) ||
doAcquireNanos(arg, nanosTimeout);
}
// 獨占式釋放同步狀態，并喚醒等待隊列中的一個線程。
public final boolean release(int arg) {
// 首先調用tryRelease(arg)方法嘗試釋放同步狀態，該方法需要子類實現。
// 如果釋放成功（tryRelease(arg)返回true），則進入下一步。
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
// 通過unparkSuccessor(Node node)方法喚醒等待隊列中第一個處于等待狀態且能夠被喚醒的線程。
// 如果沒有這樣的線程，則不進行任何操作。
unparkSuccessor(h);
return true;
}
return false;
}
//============================================= 共享式
// 共享式獲取同步狀態，如果獲取失敗則進入等待隊列。
public final void acquireShared(int arg) {
// 首先調用tryAcquireShared(arg)方法嘗試獲取同步狀態，該方法需要子類實現。
// 如果返回值大于等于 0，表示獲取成功，acquireShared方法直接返回。
if (tryAcquireShared(arg) < 0)
// doAcquireShared(int arg)方法，使當前線程在等待隊列中自旋等待獲取同步狀態。
doAcquireShared(arg);
}
// 共享式獲取同步狀態，在獲取過程中可以響應中斷。
public final void acquireSharedInterruptibly(int arg)
throws InterruptedException {
if (Thread.interrupted())
throw new InterruptedException();
if (tryAcquireShared(arg) < 0)
// 如果tryAcquireShared(arg)返回值小于 0，表示獲取失敗，
// 則通過addWaiter(Node.SHARED)方法將當前線程封裝成一個"共享式節點"并添加到等待隊列尾部。
doAcquireSharedInterruptibly(arg);
}
public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)
throws InterruptedException {
if (Thread.interrupted())
throw new InterruptedException();
return tryAcquireShared(arg) >= 0 ||
doAcquireSharedNanos(arg, nanosTimeout);
}
// 共享式釋放同步狀態，并喚醒等待隊列中的其他線程。
public final boolean releaseShared(int arg) {
// 調用tryReleaseShared(arg)方法嘗試釋放同步狀態，該方法需要子類實現。
// 如果釋放成功（tryReleaseShared(arg)返回true），則進入下一步。
if (tryReleaseShared(arg)) {
// 同理。通過doReleaseShared()方法喚醒等待隊列中所有處于等待狀態且能夠被喚醒的"共享式節點"對應的線程。
doReleaseShared();
return true;
}
return false;
}
//.........
}
通過上面的分析得知，aqs提供給我們的提供的模板方法主要分為三類：【模板方法的設計模式】
- 獨占式地獲取和釋放鎖；
- 共享式地獲取和釋放鎖；
- 查詢
AQS的同步隊列中正在等待的線程情況；
這里順便說一下獨占鎖【排它鎖、寫鎖】和共享鎖【讀鎖】
獨占鎖：也叫排他鎖，即鎖只能由一個線程獲取，若一個線程獲取了鎖，則其他想要獲取鎖的線程只能等待，直到鎖被釋放。比如說寫鎖，對于寫操作，每次只能由一個線程進行，若多個線程同時進行寫操作，將很可能出現線程安全問題；
共享鎖：鎖可以由多個線程同時獲取，鎖被獲取一次，則鎖的計數器+1。比較典型的就是讀鎖，讀操作并不會產生副作用，所以可以允許多個線程同時對數據進行讀操作，而不會有線程安全問題，當然，前提是這個過程中沒有線程在進行寫操作；
經過對AQS的源碼分析，下面幾個方法需要在子類中去實現。
// tryAcquire的作用就是嘗試修改state值，也就是獲取鎖，若修改成功，則返回true，否則返回false
protected boolean tryAcquire(int arg) {
throw new UnsupportedOperationException();
}
protected boolean tryRelease(int arg) {
throw new UnsupportedOperationException();
}
protected int tryAcquireShared(int arg) {
throw new UnsupportedOperationException();
}
protected boolean tryReleaseShared(int arg) {
throw new UnsupportedOperationException();
}
protected boolean isHeldExclusively() {
throw new UnsupportedOperationException();
}
浙公網安備 33010602011771號