Skip to content

Commit 9bdb5f6

Browse files
authored
更新《集合判空》的例子
使用 `ConcurrentLinkedQueue` 作为例子,并完善 `ConcurrentHashMap` 的相关表述。
1 parent 388f94d commit 9bdb5f6

File tree

1 file changed

+37
-14
lines changed

1 file changed

+37
-14
lines changed

docs/java/collection/java-collection-precautions-for-use.md

Lines changed: 37 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -15,35 +15,58 @@ tag:
1515

1616
> **判断所有集合内部的元素是否为空,使用 `isEmpty()` 方法,而不是 `size()==0` 的方式。**
1717
18-
这是因为 `isEmpty()` 方法的可读性更好,并且时间复杂度为 O(1)。
18+
这是因为 `isEmpty()` 方法的可读性更好,并且时间复杂度为 `O(1)`
1919

20-
绝大部分我们使用的集合的 `size()` 方法的时间复杂度也是 O(1),不过,也有很多复杂度不是 O(1) 的,比如 `java.util.concurrent` 包下的某些集合(`ConcurrentLinkedQueue``ConcurrentHashMap`...)。
20+
绝大部分我们使用的集合的 `size()` 方法的时间复杂度也是 `O(1)`,不过,也有很多复杂度不是 `O(1)` 的,比如 `java.util.concurrent` 包下的 `ConcurrentLinkedQueue``ConcurrentLinkedQueue``isEmpty()` 方法通过 `first()` 方法进行判断,其中 `first()` 方法返回的是队列中第一个值不为 `null` 的节点(节点值为`null`的原因是在迭代器中使用的逻辑删除)
2121

22-
下面是 `ConcurrentHashMap``size()` 方法和 `isEmpty()` 方法的源码。
22+
```java
23+
public boolean isEmpty() { return first() == null; }
24+
25+
Node<E> first() {
26+
restartFromHead:
27+
for (;;) {
28+
for (Node<E> h = head, p = h, q;;) {
29+
boolean hasItem = (p.item != null);
30+
if (hasItem || (q = p.next) == null) { // 当前节点值不为空 或 到达队尾
31+
updateHead(h, p); // 将head设置为p
32+
return hasItem ? p : null;
33+
}
34+
else if (p == q) continue restartFromHead;
35+
else p = q; // p = p.next
36+
}
37+
}
38+
}
39+
```
40+
41+
由于在插入与删除元素时,都会执行`updateHead(h, p)`方法,所以该方法的执行的时间复杂度可以近似为`O(1)`。而 `size()` 方法需要遍历整个链表,时间复杂度为`O(n)`
2342

2443
```java
2544
public int size() {
26-
long n = sumCount();
27-
return ((n < 0L) ? 0 :
28-
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
29-
(int)n);
45+
int count = 0;
46+
for (Node<E> p = first(); p != null; p = succ(p))
47+
if (p.item != null)
48+
if (++count == Integer.MAX_VALUE)
49+
break;
50+
return count;
3051
}
52+
```
53+
54+
此外,在`ConcurrentHashMap` 1.7 中 `size()` 方法和 `isEmpty()` 方法的时间复杂度也不太一样。`ConcurrentHashMap` 1.7 将元素数量存储在每个`Segment` 中,`size()` 方法需要统计每个 `Segment` 的数量,而 `isEmpty()` 只需要找到第一个不为空的 `Segment` 即可。但是在`ConcurrentHashMap` 1.8 中的 `size()` 方法和 `isEmpty()` 都需要调用 `sumCount()` 方法,其时间复杂度与 `Node` 数组的大小有关。下面是 `sumCount()` 方法的源码:
55+
56+
```java
3157
final long sumCount() {
3258
CounterCell[] as = counterCells; CounterCell a;
3359
long sum = baseCount;
34-
if (as != null) {
35-
for (int i = 0; i < as.length; ++i) {
60+
if (as != null)
61+
for (int i = 0; i < as.length; ++i)
3662
if ((a = as[i]) != null)
3763
sum += a.value;
38-
}
39-
}
4064
return sum;
4165
}
42-
public boolean isEmpty() {
43-
return sumCount() <= 0L; // ignore transient negative values
44-
}
4566
```
4667

68+
这是因为在并发的环境下,`ConcurrentHashMap` 将每个 `Node` 中节点的数量存储在 `CounterCell[]` 数组中。在 `ConcurrentHashMap` 1.7 中,将元素数量存储在每个`Segment` 中,`size()` 方法需要统计每个 `Segment` 的数量,而 `isEmpty()` 只需要找到第一个不为空的 `Segment` 即可。
69+
4770
## 集合转 Map
4871

4972
《阿里巴巴 Java 开发手册》的描述如下:

0 commit comments

Comments
 (0)