为什么JDK用跳表实现ConcurrentNavigableMap接口

为什么JDK用跳表实现ConcurrentNavigableMap接口

• 狗屁不通
• 乱中有序
• 釜底抽薪
• 并发仙人

狗屁不通

在回答这个问题之前，不妨先回答：用于实现实现ConcurrentNavigableMap的结构应该满足什么条件？为什么JDK不用其他满足条件结构实现ConcurrentNavigableMap接口？ConcurrentNavigableMap直接和间接继承自NavigableMap和SortedMap，ConcurrentNavigableMap的父接口定义了键值对之间的全序关系，而二叉搜索树（BST）是组织全序关系的有效结构。实际工程中往往使用的是BST的子集 —— 平衡二叉搜索树（BBST）。各种BBST的自平衡机制避免了BST近似退化成链，使得树高不超过 $O(\log n)$，从而能够在 $O(\log n)$ 的时间成本内完成基本的CRUD操作。

几乎所有的国内外教材也是如上所述，把BST近似退化成链的的极端情况当做使用平衡BST的唯一原因。虽然工程中使用BBST是不争的事实，但是这种论证其实并不充分，或有些鲁莽。甚至有的更离谱的垃圾教材或培训班（某谷某马）又臭又长的视频教程里的那些社会闲散人员冒充的业余IT讲师甚至还直接断言“平衡二叉搜索树比二叉搜索树快”。TTBOMK，虽然结论正确，但这些论证过程有的没说到根本，有的纯属打胡乱说，而且至少有三点站不住脚：

1. 随机BST的期望高度就是 $\log n$。
2. 随机BST并不比平衡二叉树慢。
3. 以极端情况作为反例并不能解释为什么工程中常用红黑树和跳表，却从来不用 AVL树，伸展树，树堆等其他BBST。

首先，《算法导论》在练习12-3中指出了随机BST的期望高度就是 $O(\log n)$。这时候就有人会跳出来说：期望的意思就是平均情况，既然是平均情况才是 $O(\log n)$，那岂不是就更说明会出现极端情况了。你说的对，但是原神有 $n$ 节点可以组成不同构二叉树有 ( 2 n ) ! ( n + 1 ) ! n ! \frac {(2n)!} {(n+1)!n!} (n+1)!n!(2n)!​个，即Catalan数，所以退化成链的极端情况是所有二叉树总量的 2 ( n + 1 ) ! n ! ( 2 n ) ! \frac {2(n+1)!n!} {(2n)! } (2n)!2(n+1)!n!​。如果一棵二叉树有 $20$ 个节点组成，那么所有节点可以组成不同构的二叉树就有 $1767263190$ 种，退化成链的情况只是其中的 2 1767263190 ≈ 0.000000001 \frac {2} {1767263190} \approx 0.000000001 17672631902​≈0.000000001。同时Raimund Seidel的论文《Randomized Search Trees》中更进一步指出了随机BST不平衡的概率 Pr ⁡ [ H > 2 c ln ⁡ n ] < ( n e ) − c ln ⁡ c e \Pr[H>2c\ln n]<(\frac n e)^{-c\ln \frac c e} Pr[H>2clnn]<(en​)−clnec​其中 $c$ 是大于 $1$ 的任意常数。如果 $n=10000$，取 c = 25 2 ln ⁡ 10 c=\frac {25} {2\ln10} c=2ln1025​，可以得到$$\mathrm{Pr}[H>100]<0.0000000004$$可以发现光是 $10000$ 个节点随机构建的二叉树光是高度大于 $100$ 的概率就已经极低了，完全退化的情况的概率只会低到可以忽略不计。无论如何，不要见到期望复杂度或者平均情况复杂度就往概率极低的最坏的情况设想，快速排序也是期望复杂度 $O(n\log n)$，怎么就光把BST批判一番，然后说快速排序Excited！BST怎么你了BST怎么你了BST怎么你了？

以上的数理分析已经能够说明“平衡二叉搜索树比二叉搜索树快”纯属暴论了，但光是数理分析还远远不够，数据结构归根结底还是要看工程中好不好用。于是我测试了BST，树堆，跳表在不同规模的随机数据下search，insert，delete的实际运行时。BST的实现方式参考了《算法》3.2，树堆的实现方式基于BST，重写了insert和delete方法，跳表的实现方式参考了Willian Pugh的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。从实验结果可以看出显然BST是最快的结构，并且实现越复杂，运行时越慢！所以把那些断言“平衡二叉搜索树比二叉搜索树快”的叉出去。如果非要说可能有最坏情况 $O(n)$所以不能用，那怎么就没见人说快速排序有最坏情况 O ( n 2 ) O(n^2) O(n2) 所以不能用的呢？

稍作总结，至此已经讨论了用于实现ConcurrentNavigableMap的结构首先至少应该能够组织元素之间的全序关系，BST刚好是一种暂时满足需求的结构，并且论证了使用BBST的理由不是什么，但是暂未发现使用更高级的结构的理由。更重要的是，在论证的过程中顺便羞辱了一些自己没搞懂还到处传播 $k$ 流程序员，其中 $k$ 为大于 $1$ 的整数。

显然目前的结论和实际是不相符的，但是数理分析和随机模拟的过程也雀食是没问题的，那是什么导致了错误的结论呢？试图通过数理分析和随机模拟来回答工程中应该使用哪种结构本身就是有问题的，我之所以这么做无非只是在反（讥）驳（讽）一些谬误而已。数理分析和随机模拟都是在捣鼓固定的 $n$ 个节点：比如讨论 $n$ 个节点的树高是多少？导致单次操作的复杂度或运行时是多少？如果只是固定的 $n$ 个节点一次性全部输入，为什么不就简单组织成一个完全二叉搜索树？这不比那些花里胡哨的BBST简单又快速吗？你说的对，但是原神工程中并不是在捣鼓固定的 $n$ 个节点，而是在处理数据流，归根结底还是论证的方向有偏差导致了错误的结论。

乱中有序

对BST的分析应该是在线的，首先来看一下《算法导论》对在线算法的定义：

Algorithms that receive their input over time, rather than having all the input present at the start, are online algorithms.

简单来说就是来一个输入就处理一个输入，而且还不知道后面会来些什么牛马输入。这种模式其实很常见，就拿游戏来说，玩俄罗斯方块就是典型的在线算法，掉下来的方块放置完一个才会有下一个，并且不知道后面的方块序列。除此之外，Web服务其实也是在线算法，因为要不断去处理请求，并且不知道未来的请求。与之相反的自然是离线算法，不同之处在于所有的输入一次性输完，然后就开始一顿算。还是拿游戏来说，玩纪念碑谷就是离线算法，因为每一个图的结构都告诉你了，只需要想怎么解就可以了。然后排序是典型的离线算法，待排序序列必须是定长的。上文对BST的分析都是离线的。

现在不妨就把BST当做一个服务。如果一个带有恶意的client知道了这个服务的底层不过是一棵简单的BST，并且他知道普通的BST怕的是源源不断的有序输入，但凡这个坏B想攻击向这个服务中按顺序insert一系列元素，那就会导致BST出现一条长链，从而导致效率降低。现实中这种坏B雀食存在，而且不可忽略。

但是如果我硬要忽略掉这种情况，就把这个服务放在自己的机子上自己用，还需要考虑这种会有坏B的情况吗？我的评价是还是需要，如果输入序列雀食是像上文分析的一样是等可能出现的，BST期望高度就应该是 $\log n$。然而就算排除了恶意的输入，也并不能保证输入没有秩序，因为：

1. 不存在完全的混沌（参考Ramsey理论），也就是说再乱的输入多少也有点秩序，
2. 人类普遍有“对规律的渴望”，这不是什么定理，但确实又是事实。不管是对于数据库里的数据，API获得的数据，或是文件系统，人类普遍都有整理的习惯，也就是说会按照一组关键码进行一个序的排。比如使用SQL时UPDATE或者SELECT时候很多人喜欢加一个ORDER BY，调用API也偏好排好序的数据，文件系统也会默认对文件进行排序。

综上，看似混沌的现实数据流其实并没有想象中那么混沌，既然如此，那上文所分析的随机构建的BST的期望高度就是 $\log n$ 也不一定对了，因为分析的前提已经不成立了。至此，已经得出了一个使用BBST的理由：工程中数据流普遍存在一些潜在或人为的秩序，这种秩序是BST难以有效掌控的。

釜底抽薪

既然秩序是罪魁祸首，自然的想法就是消灭秩序，也就是打乱输入的顺序，如果数据流是乱的，BST不就平衡了吗？但是问题又来了，数据是必须来一个输入就处理一个输入的，而且没有任何办法知道未来的数据流，总不可能数据来了就头铁硬不处理，存到一定量打乱之后再处理吧，那这也太捞了吧。那有没有什么办法把未来的数据也打乱呢？嘿，您猜怎么着，还真有！

树堆就是一种可以掌控未来数据流的结构，树堆的每个节点除了存储键值对，还有一个随机数 —— 优先级，其实这个数叫什么根本不重要，重点在这个数是随机生成的。树堆的定义比起其他BBST也异常简单：

1. 关键码满足单调性：左比右小
2. 优先级满足堆序性：上比下小

第一点是所有BST的固有性质，第二点才是对BST的额外限制，就多加了一个简单的条件，就可以保证树的平衡。依次往一个空的树堆里insert 0到9（假设到目前数据流截止就这么多，后续可能有更多数据），就得到了下面的树堆，每个节点左边的数字表示关键码，右边的数字表示优先级，不难看出关键码满足BST的顺序性，优先级满足小顶堆的堆序性。具体的操作细节可以参考HeartFireY的文章。

设想如果这只是一棵普通的BST（没有各种自平衡机制），要以什么样的顺序insert这些关键码，才能得到一样的BST呢？既然更深一层的优先级必然大于更浅一层的优先级。所以只要按照优先级从小到大的次序insert以上的关键码，就可以得到同样的结构了。容易验证依次insert (3,1)，(1,6)，(0,9)，(5,11)，(4,14)，(9,17)，(7,22)，(6,42)，(8,49)，(2,99)，刚好可以得到同样的结构。所以随机优先级的作用就是对数据流进行洗牌，使得按照优先级调整过后的的BST等价于一个随机BST。就算还有更多的数据涌入，最终呈现的结构也无非等价于一棵更大的随机BST。而上文已经提到过，随机构建的BST的期望高度就是 $\log n$，所以树堆平衡的！基本CRUD的复杂度是 $\log n$。

我个人人为虽然树堆不是最实用的一种BBST，但在设计思想上却是最高明的。首先树堆足够简单，只需要在BST的基础上添加几行代码就可实现。更重要的是，在其他常见的BBST（AVL树，伸展树，红黑树）中，只有树堆是在解决产生问题的原因，而且还解决的很简单，其他的结构更像是个卑微的舔狗，总是任由数据流输入任何数据，却一个劲的调整自己的姿态。

并发仙人

现在已经找到一种别致的BBST，而且经过试验发现树堆性能也就比BST慢一点，看上去还不错。但问题还没有得到解决，为什么工程中没见谁用过呢，反而都用复杂的红黑树，比如Java的TreeMap底层结构就是红黑树，C++的std::map的底层结构也是红黑树，Linux内核还是用到了红黑树。如果一定要问我对用红黑树资瓷不资瓷，我是资瓷！它是JDK我们怎么能不资瓷JDK？。Linux官方给出了使用红黑树的原因：速度快！

Red-black trees are similar to AVL trees, but provide faster real-time bounded worst case performance for insertion and deletion (at most two rotations and three rotations, respectively, to balance the tree), with slightly slower (but still O(log n)) lookup time.

雀食快才是硬道理，工程中没人关心设计有多巧妙，只要能又快又好把货干完就行。那问题又来了，既然红黑树那么好，为什么ConcurrentNavigableMap的实现方式是ConcurrentSkipListMap而不是ConcurrentTreeMap呢？首先明确一点，跳表虽然长得不像一棵树，但是逻辑上却等同于BBST，其基本CRUD操作的复杂度都也是 $\log n$，具体的操作细节可以参考MIT的6.006。既然理论复杂度并不是必须得用跳表的原因。所以非得用跳表原因只能是跳表对多线程的支持比红黑树更快。

Concurrency应该着重考虑结构的动态操作，即insert和delete，光是search并不会对结构有任何影响，但是在insert和delete的时候就要做一些保护措施不同线程操作不同步把结构搞坏掉。ConcurrentNavigableMap作为一种共享资源，一个线程在访问时应该对修改的区域进行保护以防止其他线程的修改，比较常见的一种方式就是上锁，就拿上锁举栗子。不同线程访问的延迟取决于上锁解锁的周期，如果一个上锁解锁的时间长，那其他线程就只有干等着，等这个线程解锁了才能让下一个线程访问，这就是典型的占着茅坑不拉屎（其实说便秘更准确）的情况。

对于ConcurrentNavigableMap而言，每次修改过程中，唯数据有变化的区域才需要上锁，所以访问的延迟取决于每次修改过程中变化区域的大小。也就是说如果insert和delete导致的变化区域越小，那么速度也就越快。那现在就挨个审一下常见BBST的insert和delete操作会导致多少数据的变化。首先树堆在insert和delete都可能会至多把节点通过不断地旋转，移动至多$O(\log n)$ 层，也就是说 $O(\log n)$ 的拓扑结构的变化。其次是AVL树这个老东西，控制深度差来达到平衡，每次insert和delete都得更新节点中的depth，而且在delete的时候除了depth数值的变化，局部拓扑结构的变化可能自底向上传播，发生至多 $O(\log n)$ 拓扑结构的变化，这种老东西和多动症患者不配实现ConcurrentNavigableMap。其次，伸展树更是个逆天邪神，就连search都得把刚找到的节点扭来扭去放到root，稍微戳一下就敏感的厉害，再insert和delete更是重量级操作，三种操作都会有至多 $O(\log n)$ 拓扑结构的变化，这种读写敏感肌结构是不可能出现在并发的语境里的。那红黑树呢？红黑树有一个好：那就是不管是insert还是delete，拓扑结构的变化都只发生在局部，也就是 $O(1)$，这就是其他结构不具备的宝贵性质！但是但是但是，这个性质过于优秀，以至于很多人都忽略了一点，红黑树在delete时，双黑缺陷可能会向上传播，直到完成一次局部拓扑结构的改变停止，黑缺陷的传播虽然只是对节点进行重染色，但这种操作的确可能会导致 $O(\log n)$ 的节点发生数据变化。

所以跳表全靠同行衬托，跳表是唯一insert和delete都只在局部发生的结构，修改局部并不会像其他结构一样，影响到其他地方的数据。同时，跳表实现无锁化非常容易，无锁化可进一步提升运行时，ConcurrentSkipListMap底层的跳表就是基于硬件原子指令CompareAndSwap实现的无锁化。

总结一下，为什么JDK用跳表实现ConcurrentNavigableMap接口？因为实现这个接口的结构需要insert和delete只在$O(1)$ 的区域内完成，而跳表是唯一候选人。

对于同类型的数据结构，大多人都只在意各种表面的东西，背一背复杂度，然后看一看写一写insert和delete的代码就草草了事。其实更应该关注的是核心结构特性，比如跳表的核心结构特性就是多层链表，如果这样去理解跳表，理解insert和delete操作只在$O(1)$ 的区域内完成是很自然的事情，因为链表的insert和delete只在$O(1)$ 的区域内完成，多几层链表也是如此。

最后附上BST，树堆，跳表的代码。

public interface OrderedDictionary<K extends Comparable<K>, V> {V search(K key);void insert(K key, V val);void delete(K key);
}

import java.util.Random;public class BinarySearchTree<K extends Comparable<K>, V> implements OrderedDictionary<K, V> {protected static class Node<K, V> {private static final Random random = new Random();protected final K key;protected V value;protected int priority;protected Node<K, V> left;protected Node<K, V> right;protected Node(K key, V value) {this(key, value, random.nextInt(), null, null);}protected Node(K key, V value, int priority, Node<K, V> left, Node<K, V> right) {this.key = key;this.value = value;this.priority = priority;this.left = left;this.right = right;}}protected Node<K, V> root;@Overridepublic V search(K key) {Node<K, V> node = searchNode(root, key);return node == null ? null : node.value;}@Overridepublic void insert(K key, V value) {root = insertNode(root, key, value);}@Overridepublic void delete(K key) {root = deleteNode(root, key);}protected Node<K, V> searchNode(Node<K, V> node, K key) {return node == null ? null :key.compareTo(node.key) < 0 ? searchNode(node.left, key) :key.compareTo(node.key) > 0 ? searchNode(node.right, key) : node;}protected Node<K, V> insertNode(Node<K, V> node, K key, V value) {if (node == null) {return new Node<>(key, value);} else if (key.compareTo(node.key) < 0) {node.left = insertNode(node.left, key, value);} else if (key.compareTo(node.key) > 0) {node.right = insertNode(node.right, key, value);} else {node.value = value;}return node;}protected Node<K, V> deleteNode(Node<K, V> node, K key) {if (node == null) {return null;} else if (key.compareTo(node.key) < 0) {node.left = deleteNode(node.left, key);} else if (key.compareTo(node.key) > 0) {node.right = deleteNode(node.right, key);} else if (node.left == null) {return node.right;} else if (node.right == null) {return node.left;} else {Node<K, V> temp = node;node = successor(node.right);node.right = deleteSuccessor(temp.right);node.left = temp.left;}return node;}private Node<K, V> deleteSuccessor(Node<K, V> node) {if (node.left == null) { return node.right; }node.left = deleteSuccessor(node.left);return node;}private Node<K, V> successor(Node<K, V> node) {return node.left == null ? node : successor(node.left);}
}

public class Treap<K extends Comparable<K>, V> extends BinarySearchTree<K, V> {@Overrideprotected Node<K, V> insertNode(Node<K, V> node, K key, V value) {if (node == null) {return new Node<>(key, value);} else if (key.compareTo(node.key) < 0) {node.left = insertNode(node.left, key, value);if (node.left.priority < node.priority) { node = zig(node); }} else if (key.compareTo(node.key) > 0) {node.right = insertNode(node.right, key, value);if (node.right.priority < node.priority) { node = zag(node); }} else {node.value = value;}return node;}@Overrideprotected Node<K, V> deleteNode(Node<K, V> node, K key) {if (node == null) {return null;} else if (key.compareTo(node.key) < 0) {node.left = deleteNode(node.left, key);} else if (key.compareTo(node.key) > 0) {node.right = deleteNode(node.right, key);} else if (node.left == null) {return node.right;} else if (node.right == null) {return node.left;} else if (node.left.priority < node.right.priority) {node = zig(node);node.right = deleteNode(node.right, key);} else {node = zag(node);node.left = deleteNode(node.left, key);}return node;}private Node<K, V> zig(Node<K, V> node) {Node<K, V> left = node.left;node.left = left.right;left.right = node;return left;}private Node<K, V> zag(Node<K, V> node) {Node<K, V> right = node.right;node.right = right.left;right.left = node;return right;}
}

import java.lang.reflect.Array;
import java.util.Random;public class SkipList<K extends Comparable<K>, V> implements OrderedDictionary<K, V>  {private static class Node<K, V> {private final K key;private V value;private final int level;private final Node<K, V>[] forward;private Node(K key, V value, int level) {this.key = key;this.value = value;this.level = level;forward = (Node<K, V>[]) Array.newInstance(Node.class, level + 1);}}private static final int MAX_LEVEL = 15;private static final Random random = new Random();private int level;private final Node<K, V> header;private final Node<K, V>[] update;public SkipList() {level = 0;header = new Node<>(null, null, MAX_LEVEL);update = (Node<K, V>[]) Array.newInstance(Node.class, MAX_LEVEL + 1);}@Overridepublic V search(K key) {Node<K, V> node = searchNode(key);return node == null || node.key.compareTo(key) > 0 ? null : node.value;}@Overridepublic void insert(K key, V value) {insertNode(key, value);}@Overridepublic void delete(K key) {deleteNode(key);}private Node<K, V> searchNode(K key) {Node<K, V> node = header;for (int i = MAX_LEVEL; i >= 0; i--) {while (node.forward[i] != null && node.forward[i].key.compareTo(key) < 0) { node = node.forward[i]; }update[i] = node;}return node.forward[0];}private Node<K, V> insertNode(K key, V value) {Node<K, V> node = searchNode(key);if (node != null && node.key.compareTo(key) == 0) {node.value = value;} else {node = new Node<>(key, value, Math.min(MAX_LEVEL, Integer.numberOfTrailingZeros(random.nextInt() & (1 << (MAX_LEVEL + 1)) - 1)));if (node.level > level) {for (int i = level + 1; i < node.level + 1; i++) { update[i] = header; }level = node.level;}for (int i = 0; i < node.level + 1; i++) {node.forward[i] = update[i].forward[i];update[i].forward[i] = node;}}return node;}private Node<K, V> deleteNode(K key) {Node<K, V> node = searchNode(key);if (node != null && node.key.compareTo(key) == 0) {for (int i = 0; i < level; i++) {if (update[i].forward[i] != node) { break; }update[i].forward[i] = node.forward[i];}while (level > 0 && header.forward[level] == null) { level--; }}return node;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！