最终得出的结论是，火男建议 p 值取 1/4。如果你主要关心的是执行时间的变化，那么 p 就取值 1/2。

说一下我的理解。首先跳表这个是一个典型的空间换时间的例子。

一个有序的二维数组，查找指定元素，理论上是二分查找最快。而跳表就是在基础的链表上不断的抽节点（或者叫索引），形成新的链表。

所以，当 p=1/2 的时候，就近似于二分查找，查询速度快，但是层数比较高，占的空间就大。

当 p=1/4 的时候，元素升级层数的概率就低，总体层高就低，虽然查询速度慢一点，但是占的空间就小一点。

在 Redis 中 p 的取值就是 0.25，即 1/4，MaxLevel 的取值是 32（视版本而定：有的版本是64）。

论文里面还花了大量的篇幅去推理时间复杂度，有兴趣的可以去看着论文一起推理一下：

跳表在 Java 中的应用

跳表，虽然是一个接触比较少的数据结构。

其实在 java 中也有对应的实现。

先问个问题：Map 家族中大多都是无序的，那么请问你知道有什么 Map 是有序的呢？

TreeMap，LinkedHashMap 是有序的，对吧。

但是它们不是线程安全的。

那么既是线程安全的，又是有序的 Map 是什么？

那就是它，一个存在感也是低的不行的 ConcurrentSkipListMap。

你看它这个名字多吊，又有 list 又有 Map。

看一个测试用例：

public class MainTest {
    public static void main(String[] args) {
        ConcurrentSkipListMap<Integer, String> skipListMap = new ConcurrentSkipListMap<>();
        skipListMap.put(3,"3");
        skipListMap.put(6,"6");
        skipListMap.put(7,"7");
        skipListMap.put(9,"9");
        skipListMap.put(12,"12");
        skipListMap.put(17,"17");
        skipListMap.put(19,"19");
        skipListMap.put(21,"21");
        skipListMap.put(25,"25");
        skipListMap.put(26,"26");
        System.out.println("skipListMap = " + skipListMap);
    }
}

输出结果是这样的，确实是有序的：

稍微的剖析一下。首先看看它的三个关键结构。

第一个是 index：

index 里面包含了一个节点 node、一个右指针（right）、一个下指针（down）。

第二个是 HeadIndex:

它是继承自 index 的，只是多了一个 level 属性，记录是位于第几层的索引。

第三个是 node：

这个 node 没啥说的，一看就是个链表。

这三者之间的关系就是示意图这样的：

我们就用前面的示例代码，先 debug 一下，把上面的示意图，用真实的值填充上。

debug 跑起来之后，可以看到当前是有两个层级的：

所以第二层的链表是这样的

第二层的 HeadIndex 节点除了我们刚刚分析的 right 属性外，还有一个 down，指向的是下一层，也就是第一层的 HeadIndex：

可以看到第一层的 HeadIndex 的 down 属性是 null。但是它的 right 属性是有值的：

可以画出第一层的链表结构是这样的：

所以，整个跳表结构是这样的：

但是当你拿着同样的程序，自己去调试的时候，你会发现，你的跳表不长这样啊？

当然不一样了，一样了才是撞了鬼了。

别忘了，索引的层级是随机产生的。

ConcurrentSkipListMap 是怎样随机的呢？

带大家看看 put 部分的源码。

标号为 ① 的地方代码很多，但是核心思想是把指定元素维护进最底层的有序链表中。就不进行解读了，所以我把这块代码折叠起来了。

标号为 ② 的地方是 (rnd & 0x80000001) == 0。

这个 rnd 是上一行代码随机出来的值。

而 0x80000001 对应的二进制是这样的：

一头一尾都是1，其他位都是 0。

那么只有 rnd 的一头一尾都是 0 的时候，才会满足 if 条件，(rnd & 0x80000001) == 0。

二进制的一头一尾都是 0，说明是一个正偶数。

随机出来一个正偶数的时候，表明需要对其进行索引的维护。

标号为 ③ 的地方是判断当前元素要维护到第几层索引中。

((rnd >>>= 1) & 1) != 0 ，已知 rnd 是一个正偶数，那么从其二进制的低位的第二位（第一位肯定是0嘛）开始，有几个连续的 1，就维护到第几层。

不明白？没关系，我举个例子。

假设随机出来的正偶数是 110，其二进制是 01101110。因为有 3 个连续的 1，那么 level 就是从 1 连续自增 3 次，最终的 level 就是 4。

那么问题就来了，如果我们当前最多只有 2 层索引呢？直接就把索引干到第 4 层吗？

这个时候标号为 ④ 的代码的作用就出来了。

如果新增的层数大于现有的层数，那么只是在现有的层数上进行加一。

这个时候我们再回过头去看看火男论文里面的随机算法：

所以，你现在知道了，由于有随机数的出现，所以即使是相同的参数，每次都可以构建出不一样的跳表结构。

比如还是前面演示的代码，我 debug 截图的时候有两层索引。

但是，其实有的时候我也会碰到 3 层索引的情况。

另外，开篇用 redis 做为了切入点，其实 redis 的跳表整体思想是大同的，但是也是有小异的。

比如 Redis 在 skiplist 的 forward 指针（相当于 index）上，每个 forward 指针都增加了 span 属性。

在《Redis深度历险》一书里面对该属性进行了描述：

最后说一句（求关注）

好了，那么这次的文章就到这里啦。

才疏学浅，难免会有纰漏，如果你发现了错误的地方，可以提出来，我对其加以修改。 感谢您的阅读，我坚持原创，十分欢迎并感谢您的关注。

我是 why，一个被代码耽误的文学创作者，不是大佬，但是喜欢分享，是一个又暖又有料的四川好男人。

欢迎关注我呀。