Java并发容器：ConcurrentSkipListMap/Set的跳跃表（Skip List）实现与并发控制
大家好，今天我们来深入探讨Java并发容器中的ConcurrentSkipListMap和ConcurrentSkipListSet，重点分析它们底层基于的跳跃表（Skip List）数据结构以及相关的并发控制机制。
1. 跳跃表（Skip List）概览
跳跃表是一种基于概率分布的有序数据结构，可以在平均O(log n)的时间复杂度内完成查找、插入和删除操作。它通过维护多个层级的链表，从而实现快速的查找。可以将其视为平衡树的一种替代方案，但实现起来相对简单。
1.1 跳跃表的基本结构
一个跳跃表由多个层级（level）的链表组成。
- 底层链表（Level 0）：包含所有元素，并且是有序的。
- 上层链表（Level 1, Level 2, …）：是底层链表的子集，用于加速查找过程。
每个节点包含一个key（键）和多个forward指针，forward指针指向该节点在对应层级上的下一个节点。最高层级的节点数量最少，使得查找可以快速到达目标节点附近。
1.2 跳跃表查找过程
查找一个元素时，从最高层级开始，沿着forward指针向右移动，直到找到大于等于目标key的节点。如果找到了大于目标key的节点，则向下移动到下一层级，继续查找。重复这个过程，直到到达底层链表，此时可以确定目标key是否存在。
例如，假设我们有以下跳跃表，要查找key = 30：
Level 3: [Start] --> [50] --> [End]
Level 2: [Start] --> [20] --> [50] --> [End]
Level 1: [Start] --> [10] --> [20] --> [30] --> [50] --> [End]
Level 0: [Start] --> [10] --> [20] --> [30] --> [40] --> [50] --> [End]查找过程如下：
- 从Level 3开始，
Start的forward指向50，50 > 30，向下移动到Level 2。 - 在Level 2，
Start的forward指向20，20 < 30，移动到20的forward，指向50，50 > 30，向下移动到Level 1。 - 在Level 1，
Start的forward指向10，10 < 30，移动到10的forward，指向20，20 < 30，移动到20的forward，指向30，30 == 30，查找成功。
1.3 跳跃表插入过程
插入一个元素时，首先需要随机决定该元素要占据的层级数。然后，从最高层级开始，找到每层级上应该插入的位置，并更新相应的forward指针。
例如，插入key = 25，假设随机生成的层级数为2：
Level 3: [Start] --> [50] --> [End]
Level 2: [Start] --> [20] --> [50] --> [End]
Level 1: [Start] --> [10] --> [20] --> [30] --> [50] --> [End]
Level 0: [Start] --> [10] --> [20] --> [30] --> [40] --> [50] --> [End]- 找到Level 2中
25应该插入的位置：20和50之间。更新20的forward指针指向25，25的forward指针指向50。 - 找到Level 1中
25应该插入的位置：20和30之间。更新20的forward指针指向25，25的forward指针指向30。 - 找到Level 0中
25应该插入的位置：20和30之间。更新20的forward指针指向25，25的forward指针指向30。
插入后的跳跃表：
Level 3: [Start] --> [50] --> [End]
Level 2: [Start] --> [20] --> [25] --> [50] --> [End]
Level 1: [Start] --> [10] --> [20] --> [25] --> [30] --> [50] --> [End]
Level 0: [Start] --> [10] --> [20] --> [25] --> [30] --> [40] --> [50] --> [End]1.4 跳跃表删除过程
删除一个元素时，需要找到该元素在所有层级上的位置，并更新相应的forward指针，将该元素从跳跃表中移除。
2. ConcurrentSkipListMap/Set的实现
ConcurrentSkipListMap和ConcurrentSkipListSet是Java并发包提供的基于跳跃表的并发容器。它们使用了CAS（Compare and Swap）操作来实现无锁并发控制，从而保证线程安全。
2.1 ConcurrentSkipListMap的节点结构
ConcurrentSkipListMap的节点结构比普通的跳跃表节点更复杂，需要考虑并发修改的情况。
static final class Node<K,V> {
final K key;
volatile Object value;
volatile Node<K,V> next;
Node(K key, Object value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
// ... 其他方法
}
static final class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
this.node = node;
this.down = down;
this.right = right;
}
// ... 其他方法
}Node：表示链表中的一个节点，存储键值对。value和next使用volatile修饰，保证可见性。Index：表示跳跃表中的一个索引节点，存储指向Node的指针。right使用volatile修饰，保证可见性。down指向下一层级的索引节点。
2.2 并发控制机制
ConcurrentSkipListMap使用CAS操作来实现并发控制，避免了锁的使用，提高了并发性能.
- CAS操作：用于原子性地更新
Node的value和next字段，以及Index的right字段。 - 标记删除：删除节点时，并不是立即从跳跃表中移除，而是先将节点的
value标记为null，表示该节点已被删除。然后在后续的操作中，再物理地移除该节点。 - retry机制：如果CAS操作失败，则重试，直到成功或者达到最大重试次数。
2.3 查找操作
查找操作与普通的跳跃表类似，但是需要考虑并发修改的情况。
private V doGet(Object key) {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = comparable(key);
Node<K,V> n = findNode(k);
if (n != null) {
Object v = n.value;
if (v != null)
return (V)v;
}
return null;
}
private Node<K,V> findNode(Comparable<? super K> key) {
Node<K,V> b = head;
Node<K,V> n = b.next;
for (;;) {
if (n != null) {
Object v = n.value;
if (v == null) {
Node<K,V> nn = n.next;
if (nn == null)
continue search; // restart from top
casNext(b, n, nn); // unlink deleted node
n = nn;
continue;
}
Comparable<? super K> k = n.key;
int cmp = key.compareTo((K)k);
if (cmp > 0) {
b = n;
n = n.next;
continue;
}
if (cmp == 0)
return n;
else
break;
}
if (b.next == n) // unlinked before casNext
return null;
b = findPredecessor(key, b); // search from predecessor
n = b.next;
}
}
- 从
head节点开始，逐层查找，直到找到目标节点或者到达底层链表。 - 如果遇到
value为null的节点，表示该节点已被删除，需要将其从链表中移除，并重新开始查找。 findPredecessor方法用于寻找当前节点的合适的前驱节点，防止其他线程并发修改
2.4 插入操作
插入操作需要先找到插入位置，然后创建新的节点，并将其插入到跳跃表中。
private V doPut(K key, V value, boolean onlyIfAbsent) {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = comparable(key);
for (;;) {
Node<K,V> b = findNode(k);
if (b != null) {
Object v = b.value;
if (v == null) {
// help delete
continue;
} else if (onlyIfAbsent || b.casValue(v, value)) {
return (V)v;
} else {
// retry due to lost race to replace value
continue;
}
}
Node<K,V> z = new Node<K,V>(key, value, null);
if (!b.casNext(null, z)) {
continue;
}
int level = randomLevel();
if (level > 0) {
insertIndex(z, level);
}
return null;
}
}
private void insertIndex(Node<K,V> z, int level) {
HeadIndex<K,V> h = head;
int max = h.level;
if (level <= max) {
for (int i = 1; i <= level; i++) {
findPredecessor(z.key, h, i); // Find correct insertion point
}
} else {
// Create new levels
for (int i = max + 1; i <= level; i++) {
HeadIndex<K,V> newh = new HeadIndex<K,V>(new Node<K,V>(z.key, null, null), h, null, i);
if (casHead(h, newh)) {
h = newh;
} else {
h = head; // Re-read head
}
}
}
// Insert indices
for (int i = 1; i <= level; i++) {
Index<K,V> idx = new Index<K,V>(z, null, null);
Index<K,V> q = findPredecessor(z.key, h, i);
idx.right = q.right;
q.casRight(q.right, idx);
}
}- 使用CAS操作原子性地将新节点插入到链表中。
- 如果插入成功，则需要根据随机生成的层级数，将新节点添加到上层索引中。
- 如果需要创建新的层级，则使用CAS操作原子性地更新
head节点。 randomLevel()方法用于随机生成新节点的层级数。
2.5 删除操作
删除操作需要先找到要删除的节点，然后将其value标记为null，并从跳跃表中移除。
private V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = comparable(key);
for (;;) {
Node<K,V> b = findNode(k);
if (b == null) {
return null;
}
Object v = b.value;
if (v == null || (value != null && !value.equals(v))) {
return null;
}
if (b.casValue(v, null)) {
findPredecessor(k, head); // Clean up indices
return (V)v;
} else {
continue;
}
}
}- 使用CAS操作原子性地将节点的
value标记为null。 findPredecessor方法用于从跳跃表中移除该节点。
2.6 ConcurrentSkipListSet
ConcurrentSkipListSet是基于ConcurrentSkipListMap实现的，它将元素作为key存储在ConcurrentSkipListMap中，value则使用一个哑对象（PRESENT）。
public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
private final ConcurrentNavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
public ConcurrentSkipListSet() {
m = new ConcurrentSkipListMap<E,Object>();
}
// ... 其他方法
}3. 性能分析
ConcurrentSkipListMap和ConcurrentSkipListSet的平均时间复杂度如下：
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(log n) |
| 插入 | O(log n) |
| 删除 | O(log n) |
由于使用了CAS操作来实现并发控制，避免了锁的竞争，因此具有较高的并发性能。但是，CAS操作也存在一定的开销，例如重试的开销。
3.1 适用场景
ConcurrentSkipListMap和ConcurrentSkipListSet适用于以下场景：
- 需要并发访问的有序集合或映射。
- 读多写少的场景。
- 对性能要求较高的场景。
3.2 不适用场景
ConcurrentSkipListMap和ConcurrentSkipListSet不适用于以下场景：
- 数据量非常小的场景，此时使用简单的锁可能更高效。
- 写操作非常频繁的场景，此时CAS操作的开销可能会比较大。
4. 代码示例
以下代码示例演示了如何使用ConcurrentSkipListMap：
import java.util.concurrent.ConcurrentSkipListMap;
public class ConcurrentSkipListMapExample {
public static void main(String[] args) {
ConcurrentSkipListMap<String, Integer> map = new ConcurrentSkipListMap<>();
// 插入元素
map.put("A", 1);
map.put("C", 3);
map.put("B", 2);
// 查找元素
System.out.println("Value of A: " + map.get("A"));
// 遍历元素
map.forEach((key, value) -> System.out.println(key + ": " + value));
// 删除元素
map.remove("B");
// 再次遍历元素
System.out.println("After removing B:");
map.forEach((key, value) -> System.out.println(key + ": " + value));
}
}以下代码示例演示了如何使用ConcurrentSkipListSet：
import java.util.concurrent.ConcurrentSkipListSet;
public class ConcurrentSkipListSetExample {
public static void main(String[] args) {
ConcurrentSkipListSet<String> set = new ConcurrentSkipListSet<>();
// 插入元素
set.add("A");
set.add("C");
set.add("B");
// 遍历元素
set.forEach(System.out::println);
// 删除元素
set.remove("B");
// 再次遍历元素
System.out.println("After removing B:");
set.forEach(System.out::println);
}
}5. 总结
ConcurrentSkipListMap和ConcurrentSkipListSet是基于跳跃表的并发容器，通过CAS操作实现无锁并发控制，具有较高的并发性能。适用于需要并发访问的有序集合或映射，以及读多写少的场景。
6. 深入理解跳跃表和并发控制机制
ConcurrentSkipListMap和ConcurrentSkipListSet的强大之处在于它结合了跳跃表的高效查找性能和无锁并发控制的优势。理解跳跃表的结构和操作，以及CAS操作的原理，对于深入理解这两个并发容器至关重要。
7. 性能调优和选择合适的并发容器
在实际应用中，需要根据具体的场景选择合适的并发容器。ConcurrentSkipListMap和ConcurrentSkipListSet虽然具有较高的并发性能，但并不是所有场景的最佳选择。例如，如果数据量非常小，或者写操作非常频繁，则可能需要考虑其他的并发容器，例如ConcurrentHashMap或CopyOnWriteArrayList。此外，还可以通过调整跳跃表的参数，例如最大层级数，来优化性能。
8. 未来发展方向：更高效的并发数据结构
随着硬件和软件技术的不断发展，未来可能会出现更高效的并发数据结构，例如基于新型内存架构的数据结构，或者基于硬件加速的并发数据结构。这些新的数据结构将能够更好地满足高并发、低延迟的应用需求。