skiplist插入一個節(jié)點時隨機出一個層數(shù)，聽起來這么隨意，如何保證搜索時的效率。?這里首先要細(xì)節(jié)分析的是這個隨機層數(shù)是怎么來的。一般跳表會設(shè)計一個最大層數(shù)maxLevel的限 制，其次會設(shè)置一個多增加一層的概率p。

實現(xiàn)中

p = 1/4

maxLevel = 32

很容易看出，產(chǎn)生越高的節(jié)點層數(shù)，概率越低。定量的分析 如下： 節(jié)點層數(shù)至少為1。而大于1的節(jié)點層數(shù)，滿足一個概率分布。 節(jié)點層數(shù)恰好等于1的概率為1-p。 節(jié)點層數(shù)大于等于2的概率為p，而節(jié)點層數(shù)恰好等于2的概率為p(1-p)。 節(jié)點層數(shù)大于等于3的概率為p^2，而節(jié)點層數(shù)恰好等于3的概率為p^2*(1-p)。 節(jié)點層數(shù)大于等于4的概率為p^3，而節(jié)點層數(shù)恰好等于4的概率為p^3*(1-p)。 ?因此，一個節(jié)點的平均層數(shù)（也即包含的平均指針數(shù)目），計算如下：

則

?當(dāng)p=1/2時，每個節(jié)點所包含的平均指針數(shù)目為2；

當(dāng)p=1/4時，每個節(jié)點所包含的平均指針數(shù)目為1.33。

跳表本質(zhì)上也是一種查找結(jié)構(gòu)，用于算法中的查找問題，跟平衡搜索樹和哈希表的價值是 一樣的，但

1.相比平衡搜索樹(AVL樹和紅黑樹)對比，都可以做到遍歷數(shù)據(jù)有序，時間復(fù)雜度也差 不多。skiplist的優(yōu)勢是：

a、skiplist實現(xiàn)簡單，容易控制。平衡樹增刪查改遍歷都更復(fù)雜。

b、skiplist的額外空間消耗更低。平衡樹節(jié)點存儲每個值有三叉鏈，平衡因子/顏色等消耗。 skiplist中p=1/2時，每個節(jié)點所包含的平均指針數(shù)目為2；skiplist中p=1/4時，每個節(jié)點所包含的平均指針數(shù)目為1.33.

2.相比哈希表而言，就沒有那么大的優(yōu)勢了。相比而言

a、哈希表平均時間復(fù)雜度是O(1)，比skiplist快。

b、哈希表空間消耗略多一點。

skiplist優(yōu)勢如下：

a、遍歷數(shù)據(jù)有序?

b、skiplist空間消耗略小一點，哈希表存在鏈接指針和表空間消耗。

c、哈希表擴容有性能損耗。

d、哈希表再極端場景下哈希沖突高，效率下降厲害，需要紅黑樹補足接力。