Java中的Map & CAS & AQS

Java中的Map

1.基本介绍和api使用就免了

Java中的Map是一种用于存储键值对（Key-Value）的接口，属于java.util包，是集合框架的重要组成部分。
2.HashMap

从图中的关系可以看出这些类间关系了。
①基本分析

HashMap的一些属性

1. // 默认容量 16
2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
3. /*最大容量*/
4. static final int MAXIMUM_CAPACITY = 1 << 30;
5. /**负载因子*/
6. static final float DEFAULT_LOAD_FACTOR = 0.75f;
7. /*使用树而不是列表的bin计数阈值。当向至少有这么多节点的桶中添加元素时，桶将转换为树。该值必须大于2，并且应该至少为8，*/
8. static final int TREEIFY_THRESHOLD = 8;
9. //HashMap红黑树退化成链表的临界值
10. static final int UNTREEIFY_THRESHOLD = 6;
11. //HashMap链表升级成红黑树第二个条件：HashMap数组(桶)的长度大于等于64
12. static final int MIN_TREEIFY_CAPACITY = 64;
13. /* ---------------- Fields -------------- */
14. /*实际的键值对。在分配时，长度总是2的幂。*/
15. transient Node<K,V>[] table;
16. /*保存缓存的entrySet（*/
17. transient Set<Map.Entry<K,V>> entrySet;
18. transient int size;
20. transient int modCount;
21. int threshold;
22. final float loadFactor;

复制代码

扩容机制resize();

HashMap 的扩容机制是为了在元素数量增加时，维持合理的负载因子，减少哈希冲突，从而保证 HashMap 的性能。
new了一个HashMap对象的时候，第一次put才会去初始化tab的Node数组，这时就会 负载因子 * 容量。【延迟初始化，嘿嘿嘿】

• 容量（Capacity）：指 HashMap 内部数组的大小。初始容量默认为 16，并且必须是 2 的幂次方。
  
• 负载因子（Load Factor）：衡量 HashMap 满的程度，默认为 0.75。它表示当 HashMap 中的元素数量达到容量的负载因子 * 容量时，就会触发扩容。
  
• 阈值（Threshold）：等于负载因子 * 容量。当 HashMap 中的元素数量达到阈值时，就会进行扩容。
  

1. static class Node<K,V> implements Map.Entry<K,V> {
2.     final int hash; // hash值
3.     final K key; //
4.     V value;
5.     Node<K,V> next; // 下一个元素
6. }

复制代码

扩容过程

• 创建新数组：扩容时，会创建一个新的数组，新数组的容量是原数组容量的 2 倍。例如，原数组容量为 16，扩容后新数组容量为 32。
  
• 重新计算哈希值和索引：将原数组中的所有键值对重新计算哈希值，并根据新数组的容量重新确定它们在新数组中的索引位置。这是因为数组容量变化后，hash & (length - 1)的结果会改变。
  
• 迁移元素：遍历原数组，将每个桶（bucket，即数组中的每个位置）中的元素重新插入到新数组的相应位置。如果桶中只有一个元素，直接计算新索引插入即可。如果桶中是链表结构（JDK 1.7 及之前）或红黑树结构（JDK 1.8 及之后，当链表长度大于 8 且数组容量大于 64 时会转换为红黑树），则需要对链表或红黑树中的每个元素重新计算索引并插入到新数组对应位置。
  

1. public V put(K key, V value) {
2.     return putVal(hash(key), key, value, false, true);
3. }
5. // 计算hash值
6. static final int hash(Object key) {
7.     int h;
8.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
9. }
11. // putVal
12. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
13.                    boolean evict) {
14.     Node<K,V>[] tab; Node<K,V> p; int n, i;
15.     // 1.如果此时的table还没有初始化，就执行resize()操作
16.     if ((tab = table) == null || (n = tab.length) == 0)
17.         n = (tab = resize()).length;
18.     // 2.如果【计算的hash映射的位置没有元素】，就直接把元素放在上面
19.     // p是hash计算的下标所在位置的元素
20.     if ((p = tab[i = (n - 1) & hash]) == null)
21.         tab[i] = newNode(hash, key, value, null);
22.     // 3.【如果有冲突！！！！！！】
23.     else {
24.         Node<K,V> e; K k;
25.         // 【3.1】 如果p元素的hash值和put进来的hash相等，并且equals也相等
26.         if (p.hash == hash &&
27.             ((k = p.key) == key || (key != null && key.equals(k))))
28.             e = p;
29.         // 【3.2】3.1如果是false，如果p是树节点类型的
30.         else if (p instanceof TreeNode)
31.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
32.         // 【3.3】如果是普通节点类型
33.         // 下面可以看出是链表的尾插法！
34.         else {
35.             for (int binCount = 0; ; ++binCount) {
36.                 if ((e = p.next) == null) {
37.                     p.next = newNode(hash, key, value, null);
38.                     // 链表上元素数量如果快要达到阈值了，就转换为树
39.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
40.                         treeifyBin(tab, hash);
41.                     break;
42.                 }
43.                 // 如果链表上的节点与要插入的完全相同，就跳过
44.                 if (e.hash == hash &&
45.                     ((k = e.key) == key || (key != null && key.equals(k))))
46.                     break;
47.                 p = e;
48.             }
49.         }
50.         // 这里可以看到，如果存在一模一样的，新值会替换到旧值。
51.         if (e != null) { // existing mapping for key
52.             V oldValue = e.value;
53.             // onlyIfAbsent传过来的是false
54.             if (!onlyIfAbsent || oldValue == null)
55.                 e.value = value; // 如果不存在一模一样的，那么这句话执不执行都一样了
56.             afterNodeAccess(e);
57.             return oldValue;
58.         }
59.     }
60.     ++modCount;
61.     if (++size > threshold)
62.         resize(); // 扩容
63.     afterNodeInsertion(evict);
64.     return null;
65. }

复制代码

V get(Object key)获取元素

1. newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
2. threshold = newThr;

复制代码

通过源码可以看出，对于key为null，计算hash的时候返回就是0，

1. final Node<K,V>[] resize() {
2.    ......
3.     // 创建新数组
4.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
5.     table = newTab;
6.     if (oldTab != null) {
7.         for (int j = 0; j < oldCap; ++j) {
8.             Node<K,V> e;
9.             if ((e = oldTab[j]) != null) {
10.                 oldTab[j] = null;
11.                 if (e.next == null)
12.                     // 重新计算hash
13.                     newTab[e.hash & (newCap - 1)] = e;
14.                 else if (e instanceof TreeNode)
15.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
16.                 else { // preserve order
17.                     // 元素迁移【可以理解为我不想接着看源码了】
18.                     ........
19.                 }
20.             }
21.         }
22.     }
23.     return newTab;
24. }

复制代码

value = null，那就无所谓了。

1. public V get(Object key) {
2.     Node<K,V> e;
3.     return (e = getNode(hash(key), key)) == null ? null : e.value;
4. }
6. final Node<K,V> getNode(int hash, Object key) {
7.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
8.     // 1.判空
9.     if ((tab = table) != null && (n = tab.length) > 0 &&
10.         (first = tab[(n - 1) & hash]) != null) {
11.         if (first.hash == hash && // always check first node
12.             ((k = first.key) == key || (key != null && key.equals(k))))
13.             // 2.1如果hash第一个位置就是的
14.             return first;
15.         if ((e = first.next) != null) {
16.             // 2.1 找树，找链表,很简单嘛
17.             if (first instanceof TreeNode)
18.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
19.             do {
20.                 if (e.hash == hash &&
21.                     ((k = e.key) == key || (key != null && key.equals(k))))
22.                     return e;
23.             } while ((e = e.next) != null);
24.         }
25.     }
26.     return null;
27. }

复制代码

②一些问题

为什么HashMap的Node数组长度必须是2的n次幂？
在计算存入结点下标时，会利用 key 的 hsah 值进行取余操作，而计算机计算时，并没有取余等运算，会将取余转化为其他运算。

1. static final int hash(Object key) {
2.     int h;
3.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4. }

复制代码

HashMap不是有一个构造函数可以指定初始容量吗？我给一个不是2的n次幂你不就炸了？

1. Map<String, String> m = new HashMap<>(10);
2. m.put("a", "a");
3. m.put(null, "b");
4. m.put(null, "c");
5. m.put("c", null);
6. m.get("a");
7. String s = m.get(null);
8. System.out.println(s);

复制代码

看得懂不？

1. /*
2. 具体公式为 index = hash & (length - 1)，这里length是 HashMap 的长度。
3. 如果length是 2 的次幂，那么length - 1的二进制形式就是所有位都为 1。
4. 例如，若length为 16（二进制10000），length - 1就是 15（二进制01111）。
5. 这样做使得hash & (length - 1)等价于hash % length，但按位与运算比取模运算效率更高。
6. 举例子：hash=20 length=16   h % l = 4 <==> 20&15 = 4
7. */

复制代码

你传任你传，我自有办法变成二次幂！！！
3.HashTable

HashTable 是 Java 中的一个古老的键值对存储类，它是线程安全的，但现在已经不常用了。
Hashtable采用 “数组 + 链表” 的结构来存储键值对 。它内部维护了一个Entry类型的数组table，数组的每个元素都是一个链表的头节点。当有新的键值对要插入时，会根据键的哈希值计算出在数组中的索引位置，然后将键值对插入到对应索引位置的链表中。如果发生哈希冲突（即不同的键计算出了相同的索引），则通过链表来解决冲突，新的键值对会被添加到链表的头部。
Hashtable通过synchronized关键字来保证线程安全。几乎所有对Hashtable进行修改（如put、remove等）和部分读取（如get）操作的方法都被synchronized修饰。这意味着在任何时刻，只能有一个线程能够访问Hashtable的这些同步方法，从而避免了多线程环境下的数据不一致问题。

1. public HashMap(int initialCapacity) {
2.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
3. }
4. public HashMap(int initialCapacity, float loadFactor) {
5.     if (initialCapacity < 0)
6.         throw new IllegalArgumentException("Illegal initial capacity: " +
7.                                            initialCapacity);
8.     if (initialCapacity > MAXIMUM_CAPACITY)
9.         initialCapacity = MAXIMUM_CAPACITY;
10.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
11.         throw new IllegalArgumentException("Illegal load factor: " +
12.                                            loadFactor);
13.     this.loadFactor = loadFactor;
14.     this.threshold = tableSizeFor(initialCapacity);
15. }
16. // 求第一个大于cap的二次幂
17. static final int tableSizeFor(int cap) {
18.     int n = cap - 1;
19.     n |= n >>> 1; // 【无符号右移，最高位补0】
20.     n |= n >>> 2;
21.     n |= n >>> 4;
22.     n |= n >>> 8;
23.     n |= n >>> 16;
24.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
25. }

复制代码

看了源码，不允许 null 键值：Hashtable不允许使用null作为键或值。如果尝试插入null键或null值，会抛出NullPointerException。这在某些场景下不够灵活，相比之下，HashMap允许一个null键和多个null值。

1. Map<String, String> m = new HashMap<>(10);
2. // new的时候 threshold = 16
3. // 在第一次put的时候，resize()，实际底层Node是16的长度，threshold = 16 * 0.75 = 12
5. /*
6. 假设给定的初始值是10(1010)【非二次幂】
7. n = 10 - 1 = 9 (1001)
8. n |= n >>> 1   ====>  1001 | 0100 = 1101
9. n |= n >>> 2   ====>  1101 | 0011 = 1111
10. .....（同理）
11. 最后 n = 1111
12. n+1 = 10000(第一个大于n的二次幂)
13. */

复制代码

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接口，定义排序逻辑
  

1. public synchronized V put(K key, V value) {
2.     // 检查键是否为null，不允许null键
3.     if (key == null) {
4.         throw new NullPointerException();
5.     }
7.     Entry<?,?> tab[] = table;
8.     int hash = key.hashCode();
9.     int index = (hash & 0x7FFFFFFF) % tab.length;
10.     // 遍历链表查找键或插入新键值对
11.     for (Entry<K, V> e = (Entry<K, V>) tab[index]; e!= null; e = e.next) {
12.         if ((e.hash == hash) && e.key.equals(key)) {
13.             V old = e.value;
14.             e.value = value;
15.             return old;
16.         }
17.     }
18.     addEntry(hash, key, value, index);
19.     return null;
20. }
22. private void addEntry(int hash, K key, V value, int index) {
23.     modCount++;
24.     Entry<?,?> tab[] = table;
25.     if (count >= threshold) {
26.         // 扩容
27.         rehash();
29.         tab = table;
30.         hash = key.hashCode();
31.         index = (hash & 0x7FFFFFFF) % tab.length;
32.     }
33.      // 创建新的Entry并插入链表头部
34.     @SuppressWarnings("unchecked")
35.     Entry<K,V> e = (Entry<K,V>) tab[index];
36.     tab[index] = new Entry<>(hash, key, value, e);
37.     count++;
38. }

复制代码

• 要么传入Comparator接口的实现类，里面定义排序逻辑
  

1. import java.util.Hashtable;
3. public class HashTableExample {
4.     public static void main(String[] args) {
5.         Hashtable<String, Integer> hashtable = new Hashtable<>();
7.         // 添加键值对
8.         hashtable.put("one", 1);
9.         hashtable.put("two", 2);
10.         hashtable.put("three", 3);
11.         //hashtable.put(null, 444); // ============== no！！
13.         // 获取值
14.         System.out.println(hashtable.get("two")); // 输出: 2
16.         // 遍历
17.         for (String key : hashtable.keySet()) {
18.             System.out.println(key + ": " + hashtable.get(key));
19.         }
20.     }
21. }

复制代码

5.juc的Map

说实话，写到这儿有点累了。。。
①synchronizedMap

synchronizedMap 是 Java 中通过 Collections 工具类提供的一个线程安全的 Map 实现，用于将普通的 Map（如 HashMap）包装成一个线程安全的版本。它的核心思想是通过 同步锁（synchronized） 保证多线程环境下的安全性
Collections.synchronizedMap() 方法返回一个包装类，其内部通过 同步代码块（synchronized） 对原始 Map 的所有操作进行加锁。这个里面的同步安全集合类实现原理都类似啊。

1. public void testTreeMap() {
2.     Map<Student, String> m = new TreeMap<>((o1, o2) -> {
3.         if (o1.getAge() == o2.getAge()) return 0;
4.         return o1.getAge() > o2.getAge() ? -1 : 1; // 返回1,排后面儿去， -1排前面
5.     });
6.         m.put(new Student("a", 10), "a");
7.     m.put(new Student("b", 2), "b");
8.     m.put(new Student("c", 15), "c");
9.     System.out.println(m); // c, a, b
10. }

复制代码

• 与 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 更适合。
  

1. public class Student implements Comparable<Student>{
2.     private String name;
3.     private int age;
4.    
5.     @Override
6.     public int compareTo(Student o) {
7.         if (this.getAge() == o.getAge()) return 0;
8.         return this.getAge() > o.getAge() ? 1 : -1;
9.     }
10. }
12. public static void testTreeMap() {
13.     Map<Student, String> m = new TreeMap<>();
14.     m.put(new Student("a", 10), "a");
15.     m.put(new Student("b", 2), "b");
16.     m.put(new Student("c", 15), "c");
17.     System.out.println(m); // b, a, c
18. }

复制代码

②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类

1. public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
2.     return new SynchronizedMap<>(m);
3. }
5. // 内部类
6. static class SynchronizedMap<K,V> implements Map<K,V> {
7.     private final Map<K,V> m;  // 被包装的原始 Map
8.     final Object mutex;        // 同步锁对象
10.     public V put(K key, V value) {
11.         synchronized (mutex) {  // 所有操作加锁
12.             return m.put(key, value);
13.         }
14.     }
15.     public int size() {
16.          synchronized (mutex) {return m.size();}
17.     }
18.     public boolean isEmpty() {
19.         synchronized (mutex) {return m.isEmpty();}
20.     }
21.     public boolean containsKey(Object key) {
22.         synchronized (mutex) {return m.containsKey(key);}
23.     }
24.     public boolean containsValue(Object value) {
25.         synchronized (mutex) {return m.containsValue(value);}
26.     }
27.     public V get(Object key) {
28.         synchronized (mutex) {return m.get(key);}
29.     }
31.     public V put(K key, V value) {
32.         synchronized (mutex) {return m.put(key, value);}
33.     }
34.     ...........................
35.     // 其他方法也通过 synchronized 同步
36. } // 实现原理是不是简单粗暴

复制代码

在 Unsafe 类中，提供了compareAndSwapObject、compareAndSwapInt、compareAndSwapLong方法来实现的对Object、int、long类型的 CAS 操作

1. import java.util.Collections;
2. import java.util.HashMap;
3. import java.util.Map;
5. public class SynchronizedMapExample {
6.     public static void main(String[] args) {
7.         // 创建一个普通 HashMap
8.         Map<String, Integer> map = new HashMap<>();
9.         // 包装为线程安全的 Map
10.         Map<String, Integer> syncMap = Collections.synchronizedMap(map);
11.         // 多线程操作
12.         Runnable task = () -> {
13.             for (int i = 0; i < 1000; i++) {
14.                 syncMap.put(Thread.currentThread().getName() + i, i);
15.             }
16.         };
17.         Thread t1 = new Thread(task);
18.         Thread t2 = new Thread(task);
19.         t1.start();
20.         t2.start();
21.         try {
22.             t1.join();
23.             t2.join();
24.         } catch (InterruptedException e) {
25.             e.printStackTrace();
26.         }
27.         System.out.println("Map size: " + syncMap.size()); // 输出: 2000
28.     }
29. }

复制代码

参数说明
参数类型说明oObject目标对象（包含需要修改的字段的实例）。offsetlong目标字段在对象内存中的偏移量（通过 Unsafe.objectFieldOffset 获取）。expectedint期望的字段当前值（用于比较）。xint要更新的新值。offset获取，在AtomicInteger源码中可以看出。

1. Unsafe类是JDK提供的一个不安全的类，它提供了一些底层的操作，包括内存操作、线程调度、对象实例化等。它的作用是让Java可以在底层直接操作内存，从而提高程序的效率。CAS操作是基于底层硬件支持的原子性指令来实现的，所以它可以保证操作的原子性和线程安全性，同时也可以避免使用锁带来的性能开销。

复制代码

举个例子：假设有一个共享变量 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 实现的。

1. public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);

复制代码

自旋锁：(死循环?) 基于 CAS 可以实现自旋锁。自旋锁是一种非阻塞锁，线程在获取锁失败时，不会进入阻塞状态，而是不断尝试获取锁（即自旋），直到获取到锁为止。

1. static {
2.     try {
3.         valueOffset = unsafe.objectFieldOffset
4.             (AtomicInteger.class.getDeclaredField("value"));
5.     } catch (Exception ex) { throw new Error(ex); }
6. }
7. private volatile int value;

复制代码

存在的问题：

• 其实可以很明显的看出他的问题嚯。在基于 CAS 实现的自旋锁中，当一个线程尝试获取锁失败时，它会在一个循环中不断重试，即自旋。如果自旋时间过长，会浪费大量的 CPU 资源，降低系统整体性能。假设有多个线程竞争一个资源，并且持有锁的线程执行时间较长。那么其他竞争线程会持续自旋等待获取锁，在这个过程中，它们不断消耗 CPU 资源，却没有实际的工作进展。如果自旋的线程数量较多，会导致 CPU 使用率急剧上升，影响整个系统的响应速度.针对这个。我们可以
  

• 自适应自旋：自旋时间不再固定，而是根据前一次在同一个锁上的自旋时间以及锁的拥有者的状态来调整。例如，如果前一次自旋成功获取到锁，那么下一次自旋时间可以适当延长；如果自旋多次都未能获取到锁，那么可以减少自旋时间甚至不再自旋，直接进入阻塞状态。
  
• 设置自旋次数上限：给自旋设置一个最大次数，当自旋次数达到上限后，线程就不再自旋，而是进入阻塞状态。这样可以避免线程无限制地自旋，减少 CPU 资源的浪费。
  

• 第二，只能保证一个共享变量的原子操作。CAS 操作只能对单个共享变量进行原子更新。如果需要对多个共享变量进行原子操作，单纯使用 CAS 无法满足需求。针对这个问题，我们可以将多个变量合并成一个：如果多个变量之间存在一定的逻辑关系，可以将它们合并成一个对象，然后对这个对象使用AtomicReference来保证原子性操作。例如，将x和y封装在一个自定义类中，然后使用AtomicReference来操作这个类的实例。
  
• 第三，ABA 问题：CAS 操作在检查值是否为预期值 A 时，如果值在检查和更新之间经历了从 A 变为 B 再变回 A 的过程，CAS 操作依然会认为值没有改变而成功执行更新。但实际上，这个值已经发生了变化，可能会导致一些隐藏的错误。针对这个问题。
  

• 使用版本号：在每次数据更新时，版本号加 1。这样即使值变回原来的样子，但版本号已经改变，CAS 操作会失败。例如，在 Java 的AtomicStampedReference类中，就通过维护一个 “戳”（stamp）来解决 ABA 问题。每次更新数据时，不仅更新数据值，也更新戳。在进行 CAS 操作时，同时比较数据值和戳，只有两者都匹配才执行更新。
  
• 使用时间戳：类似于版本号，通过记录数据的修改时间来标记数据的变化。每次更新数据时更新时间戳，在进行 CAS 操作时比较时间戳，若时间戳不一致则不执行更新。
  

②AQS

- 公平锁和非公平锁

公平锁是指在锁的竞争中，按照请求锁的先后顺序来分配锁，即先请求锁的线程会先获得锁。这就像排队一样，先来的人先得到服务。
优点：公平锁保证了线程获取锁的公平性，避免了线程饥饿（某个线程长时间无法获取锁）的问题。
缺点：由于需要维护等待队列和按照顺序唤醒线程，公平锁的实现开销较大，性能相对较低。特别是在高并发场景下，频繁的线程切换会导致系统开销增加。

1. private static void testAtomicInteger() {
2.     AtomicInteger atomicInteger = new AtomicInteger(1);
3.     atomicInteger.getAndSet(20);
4.     System.out.println(atomicInteger.get());
5. }

复制代码

非公平锁在锁可用时，不考虑等待队列中线程的等待顺序，任何一个线程都有机会竞争并获得锁。也就是说，新请求锁的线程可能会在等待队列中的线程之前获得锁。
优点：非公平锁的实现开销相对较小，因为它不需要严格按照顺序唤醒线程。在高并发场景下，由于减少了线程切换的开销，性能通常比公平锁更好。
缺点：非公平锁可能导致部分线程长时间无法获得锁，即线程饥饿问题。特别是在有大量线程频繁请求锁的情况下，一些新线程可能会不断抢占锁，使得等待队列中的线程长时间得不到执行机会。

1. public class SpinLock {
2.     private AtomicReference<Thread> owner = new AtomicReference<>();
4.     public void lock() {
5.         Thread current = Thread.currentThread();
6.         while (!owner.compareAndSet(null, current)) {
7.             // 自旋等待
8.         }
9.     }
11.     public void unlock() {
12.         Thread current = Thread.currentThread();
13.         owner.compareAndSet(current, null);
14.     }
15. }

复制代码

- aqs基本介绍

AQS 即 AbstractQueuedSynchronizer【抽象队列同步器】，是 Java 并发包中很多同步器实现的基础框架，如ReentrantLock、Semaphore、CountDownLatch等。AQS作为一个抽象类，通常是通过继承来使用的。它本身是没有同步接口的，只是定义了同步状态和同步获取和同步释放的方法。
主要用途： 用于构建锁和同步器，它提供了一种在多线程环境下管理同步状态（state）、线程排队等待以及线程唤醒的机制。

1. private static ReentrantLock fairLock = new ReentrantLock(true); // 公平锁
2. public static void main(String[] args) {
3.     Thread[] threads = new Thread[5];
4.     for (int i = 0; i < threads.length; i++) {
5.         threads[i] = new Thread(() -> {
6.             fairLock.lock();
7.             try {
8.                 System.out.println(Thread.currentThread().getName() + " 获得了锁");
9.                 // 模拟业务逻辑
10.                 Thread.sleep(1000);
11.             } catch (InterruptedException e) {
12.                 e.printStackTrace();
13.             } finally {
14.                 fairLock.unlock();
15.             }
16.         });
17.         threads[i].start();
18.     }
19. }
20. //多个线程竞争锁时，会按照请求锁的先后顺序依次获得锁。

复制代码

从上面可以看到，双向链表有两个指针，一个指针指向前置节点，一个指针指向后继节点。这是一个虚拟的双向队列，用于存放等待获取同步状态的线程。队列节点（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类分析

1. private static ReentrantLock unfairLock = new ReentrantLock(false); // false
2. public static void main(String[] args) {
3.     Thread[] threads = new Thread[5];
4.     for (int i = 0; i < threads.length; i++) {
5.         threads[i] = new Thread(() -> {
6.             unfairLock.lock();
7.             try {
8.                 System.out.println(Thread.currentThread().getName() + " 获得了锁");
9.                 // 模拟业务逻辑
10.                 Thread.sleep(1000);
11.             } catch (InterruptedException e) {
12.                 e.printStackTrace();
13.             } finally {
14.                 unfairLock.unlock();
15.             }
16.         });
17.         threads[i].start();
18.     }
19. }

复制代码

通过上面的分析得知，aqs提供给我们的提供的模板方法主要分为三类：【模板方法的设计模式】

• 独占式地获取和释放锁；
  
• 共享式地获取和释放锁；
  
• 查询AQS的同步队列中正在等待的线程情况；
  

这里顺便说一下独占锁【排它锁、写锁】和共享锁【读锁】

独占锁：也叫排他锁，即锁只能由一个线程获取，若一个线程获取了锁，则其他想要获取锁的线程只能等待，直到锁被释放。比如说写锁，对于写操作，每次只能由一个线程进行，若多个线程同时进行写操作，将很可能出现线程安全问题；
共享锁：锁可以由多个线程同时获取，锁被获取一次，则锁的计数器+1。比较典型的就是读锁，读操作并不会产生副作用，所以可以允许多个线程同时对数据进行读操作，而不会有线程安全问题，当然，前提是这个过程中没有线程在进行写操作；

经过对AQS的源码分析，下面几个方法需要在子类中去实现。

1. public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer   
2.     implements java.io.Serializable {
3.     // 内部类Node
4.     static final class Node {
5.         .....
6.         volatile Node prev;
7.         volatile Node next;
8.         volatile Thread thread;
9.     }
10.     // 维护了一个逻辑上的基于双向链表的队列
11.     private transient volatile Node head;
12.     private transient volatile Node tail;
13.         // The synchronization state.
14.     private volatile int state;
15.     .......
16. }

复制代码

end. 参考

• https://blog.csdn.net/Aqting/article/details/129465893
  
• https://blog.csdn.net/qq_49217297/article/details/126304736
  
• https://www.cnblogs.com/tuyang1129/p/12368842.html
  
• https://topjavaer.cn/java/java-concurrent.html#什么是aqs 【aqs】
  
• https://blog.csdn.net/u010445301/article/details/125590758  【aqs】
  
• https://www.cnblogs.com/tuyang1129/p/12670014.html 【aqs】
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！