Jacky's blog
Jacky
2023-08-09
目录

collections

# Deque

定义 (opens new window)

一、常用方法
  • poll: Retrieves and removes the head of the queue represented by this deque, 返回值可为空
  • pollFirst: 同上
  • pollLast
  • peek: Retrieves, but does not remove, the head of the queue represented by this deque. 返回值可为空
  • peekFirst: 同上
  • peekLast
  • add: 在队尾插入, 如果空间不足会异常
  • addFirst: 在队首插入, 如果空间不足会异常
  • addLast: 同 add
  • offer: 在队尾插入. 有空间返回 true, 否则返回 false。 在 capacity-restricted deque 场景下, 比 add 会好用
  • offerFirst: 在队首插入
  • offerLast: 同 offer
  • remove: Retrieves and removes the head of the queue represented by this deque. 如果为空会抛出 NoSuchElementException 异常
  • removeFist: 同上
  • removeLast
  • pop: Pops an element from the stack represented by this deque. In other words, removes and returns the first element of this deque. 同 removeFirst、remove.
  • push: Pushes an element onto the stack represented by this deque (in other words, at the head of this deque)。 如果无空间, 会抛出 IllegalStateException 异常

经常可以看到 push 和 pop 配套使用, 实现 FIFO

# ArrayDeque

Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. This class is likely to be faster than {java.util.Stack} when used as a stack, and faster than LinkedList when used as a queue. 源码链接 (opens new window)

# ConcurrentHashMap

ConcurrentHashMap 是 Java 中的一个线程安全的哈希表实现，它通过一些巧妙的技术来保证多线程环境下的高效性和线程安全。我们可以从 putVal 方法中详细分析它是如何通过锁、CAS（Compare-and-Swap）以及分段锁等技术来保证线程安全的。

  1. CAS（Compare-And-Swap）
  • 在 ConcurrentHashMap 中，许多操作使用了 CAS 来实现无锁操作。例如，在以下代码中：
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
    break;  // no lock when adding to empty bin
1
2

CAS操作：casTabAt 是一个 CAS 操作，它尝试将 tab[i] 的值从 null 更新为新的 Node<K,V>。CAS 是一种无锁原子操作，它会在预期值与当前值相等时将值更新，否则不做任何修改。这样可以避免锁的使用，提高性能。

  1. 分段锁（Segment Locking）

ConcurrentHashMap 内部使用多个分段（bucket）来存储键值对。每个段都可以独立地加锁，这样多个线程可以并发地操作不同的段，减少了锁的粒度，从而提高了并发性能。

在 putVal 中，如果碰到一个已经存在的节点，它会对该节点加锁：

synchronized (f) {
    // 操作节点
}
1
2
3
  • 分段锁机制：当多个线程访问不同的段时，它们不会互相阻塞，但如果多个线程访问同一个段，操作就需要加锁来保证一致性。这是一个经典的分段锁机制，保证了在并发情况下仍能保证数据一致性。
  1. 链表与树结构的转换

当发生哈希冲突时，ConcurrentHashMap 使用链表来存储多个键值对。为了进一步提高性能，当链表长度达到一定阈值时，会将链表转换为红黑树：

if (binCount >= TREEIFY_THRESHOLD)
    treeifyBin(tab, i);
1
2
  • 链表到树的转换：这可以避免当桶中的元素非常多时，链表查找的性能下降。红黑树的查找时间复杂度是 O(log n)，比链表的 O(n) 更高效。
  1. 节点迁移（帮助迁移）

在某些情况下，ConcurrentHashMap 会发生扩容。当一个桶中的元素数量过多时，可能会触发表的扩容（rehashing）。此时，ConcurrentHashMap 采用一种 帮助迁移 的机制来保证扩容的过程中不阻塞其他线程：

else if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f);
1
2
  • 帮助迁移：如果一个桶中的节点正在迁移到新的位置（即发生扩容），ConcurrentHashMap 会帮助迁移操作完成，而不是简单地阻塞其他线程。
  1. 节点类型的处理

ConcurrentHashMap 中的节点（Node）可能有不同的类型，例如普通的链表节点、树节点（TreeBin）和预留节点（ReservationNode）。在进行 put 操作时，代码会根据节点的类型进行不同的处理：

  • 链表节点：在 putVal 方法中，如果发现某个节点是链表节点，则直接在链表中查找并插入新节点。
  • 树节点：如果节点是 TreeBin，则会通过树的方式进行插入。
  • 预留节点：ReservationNode 用于防止递归更新，避免操作中的死锁或递归。
  1. 扩容（Rehashing）

ConcurrentHashMap 会在桶的数量达到一定阈值时进行扩容。这种扩容是渐进的（延迟扩容），意味着扩容操作会分步进行，尽量避免一次性锁住整个表。

else if (f.hash == MOVED)
    tab = helpTransfer(tab, f);
1
2

扩容时，ConcurrentHashMap 会启动 helpTransfer 来帮助迁移节点。

总结

ConcurrentHashMap 的线程安全实现依赖于以下技术：

  1. CAS操作：通过无锁的原子操作（CAS）保证操作的原子性，提高并发性能。
  2. 分段锁：使用分段锁来减小锁粒度，允许多个线程并发操作不同段的数据。
  3. 链表和树的转换：当链表过长时，将其转换为红黑树，优化查找性能。
  4. 帮助迁移：在扩容过程中，采用帮助迁移机制，避免阻塞。
  5. 节点类型处理：不同类型的节点（链表、树、预留节点）采用不同的处理方式，确保高效的操作。

通过这些机制，ConcurrentHashMap 能够在高并发的情况下保证线程安全，同时避免了性能瓶颈

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 检查 key 或 value 是否为 null，如果为 null，则抛出 NullPointerException
    if (key == null || value == null) throw new NullPointerException();
    
    // 计算键的哈希值，并通过 spread() 方法打散哈希值
    int hash = spread(key.hashCode());
    int binCount = 0;  // 用于记录链表的长度

    // 循环遍历哈希表，直到插入或操作完成
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;

        // 如果哈希表为空或长度为 0，则初始化哈希表
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else {
            // 计算当前哈希值应该插入的位置
            i = (n - 1) & hash;
            
            // 获取当前桶中的第一个节点
            if ((f = tabAt(tab, i)) == null) {
                // 如果该位置为空，尝试通过 CAS 操作插入新的节点
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                    break;  // 如果 CAS 成功，跳出循环，不需要加锁
            }
            // 如果该位置正在发生扩容（节点移动），则执行帮助迁移
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                // 如果桶中已有元素，则进入锁定并插入操作
                V oldVal = null;
                synchronized (f) {  // 对当前桶的第一个节点加锁

                    // 检查桶的位置没有发生变化
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {  // 处理链表
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;

                                // 检查当前节点是否是目标节点
                                if (e.hash == hash && 
                                    ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;

                                    // 如果 not onlyIfAbsent，更新值
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }

                                // 查找链表中的下一个节点
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    // 如果到达链表末尾，插入新节点
                                    pred.next = new Node<K,V>(hash, key, value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {  // 处理红黑树
                            Node<K,V> p;
                            binCount = 2;
                            // 如果是 TreeBin 类型，插入到树中
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                        else if (f instanceof ReservationNode) {
                            // 如果是 ReservationNode，抛出异常
                            throw new IllegalStateException("Recursive update");
                        }
                    }
                }

                // 如果链表长度超过阈值，转化为红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);  // 将链表转换为红黑树
                    // 如果旧值存在，返回旧值
                    if (oldVal != null)
                        return oldVal;
                    break;  // 插入操作完成，跳出循环
                }
            }
        }
    }
    
    // 更新计数
    addCount(1L, binCount);
    return null;  // 返回 null 表示插入成功，没有找到旧值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

# 迭代器

迭代器好比C里面的指针。思考如下内容的输出

Map<Integer, Integer> map = new HashMap<>();
map.put(1, 10);
map.put(2, 20);
map.put(3, 40);
map.put(4, 40);
ConcurrentHashMap<Integer, Integer> map1 = new ConcurrentHashMap<>(map);
Iterator<Map.Entry<Integer, Integer>> iterator = map1.entrySet().iterator();
int i = 0;
while (iterator.hasNext()) {
    Map.Entry<Integer, Integer> value = iterator.next();
    i++;
    if (i == 2) {
        map1.put(5, 50);
    }
    Log.i("abc", "%d_%d", value.getKey(), value.getValue());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

OUT:

###1####1_10
###1####2_20
###1####3_40
###1####4_40
###1####5_50
1
2
3
4
5

# CopyOnWriteArraySet

CopyOnWriteArraySet 是 Java 中的一种集合实现,它基于 CopyOnWriteArrayList,通过在每次修改集合时创建集合的副本来实现线程安全。尽管这种实现提供了线程安全的优点,但也有一些显著的缺陷：

缺陷

  1. 内存消耗高: 每次修改集合(如添加或删除元素)时都会创建集合的完整副本。如果集合很大,那么这种复制行为会导致大量的内存消耗

  2. 性能低: 由于每次修改都涉及复制整个底层数组,对于修改操作(如 add、remove)来说,性能较低,尤其是当集合的大小较大时。这使得 CopyOnWriteArraySet 更适用于读取频繁、写操作很少的场景

  3. 数据一致性: 由于每次修改都涉及创建新副本,读取操作可能会访问到旧的数据副本,导致在高并发场景下数据的一致性变得不可预测。虽然这是可以接受的,因为它是设计上的一个特性,但在某些用例中可能不符合期望

  4. 无法实时反映修改: 读取操作是基于快照的,修改操作在写入后不会立即反映给所有读取线程,只有下次读取时才会看到修改。这可能会导致读取操作无法实时获取最新的数据

  5. 适用场景有限: CopyOnWriteArraySet 非常适合用于“读取多、写入少”的场景。如果应用程序需要频繁的修改操作,那么这种集合就不是一个理想的选择,使用其他线程安全集合(如 ConcurrentHashMap、ConcurrentSkipListSet)可能更合适

这些缺陷使得 CopyOnWriteArraySet 适合于读操作非常频繁而写操作非常少的情况,例如缓存或监听器注册表。如果在写操作频繁的场景中使用它,将会显著影响程序的性能和内存效率

#collection#queue#deque
上次更新: 2025/10/09, 23:53:03
UnSafe
Class

← Class→

最近更新
01
npx 使用指南
10-12
02
cursor
09-28
03
inspect
07-20
更多文章>
Theme by Vdoing | Copyright © 2019-2025 Jacky | MIT License