关于跳表

skiplist插入一个节点时随机出一个层数，听起来这么随意，如何保证搜索时的效率。 这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限 制，其次会设置一个多增加一层的概率p。

实现中

p = 1/4

maxLevel = 32

很容易看出，产生越高的节点层数，概率越低。定量的分析 如下： 节点层数至少为1。而大于1的节点层数，满足一个概率分布。 节点层数恰好等于1的概率为1-p。 节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。 节点层数大于等于3的概率为p^2，而节点层数恰好等于3的概率为p^2*(1-p)。 节点层数大于等于4的概率为p^3，而节点层数恰好等于4的概率为p^3*(1-p)。  因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：

则

 当p=1/2时，每个节点所包含的平均指针数目为2；

当p=1/4时，每个节点所包含的平均指针数目为1.33。

跳表本质上也是一种查找结构，用于算法中的查找问题，跟平衡搜索树和哈希表的价值是 一样的，但

1.相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差 不多。skiplist的优势是：

a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。

b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。 skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包含的平均指针数目为1.33.

2.相比哈希表而言，就没有那么大的优势了。相比而言

a、哈希表平均时间复杂度是O(1)，比skiplist快。

b、哈希表空间消耗略多一点。

skiplist优势如下：

a、遍历数据有序 

b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。

c、哈希表扩容有性能损耗。

d、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。