跳表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)邮弹，目前開(kāi)源軟件Redis和LevelDB都有用到它累舷，它的效率和紅黑樹以及AVL樹不相上下：
考慮一個(gè)有序表：
從該有序表中搜索元素< 23, 43, 59 >，需要比較的次數(shù)分別為< 2, 4, 6 >，總共比較的次數(shù)為2 + 4 + 6 = 12次。有沒(méi)有優(yōu)化的算法嗎?鏈表是有序的，但不能使用二分查找听怕。類似二叉搜索樹，我們把一些節(jié)點(diǎn)提取出來(lái)虑绵，作為索引尿瞭。得到如下結(jié)構(gòu)：
這里我們把< 14, 34, 50, 72 >提取出來(lái)作為一級(jí)索引，這樣搜索的時(shí)候就可以減少比較次數(shù)了翅睛。
我們還可以再?gòu)囊患?jí)索引提取一些元素出來(lái)声搁，作為二級(jí)索引，變成如下結(jié)構(gòu)：
跳表結(jié)構(gòu)：
-1表示INT_MIN,鏈表的最小值
1表示INT_MAX,鏈表的最大值捕发。
跳表具有如下性質(zhì)：
(1)由很多層結(jié)構(gòu)組成
(2)每一層都是一個(gè)有序的鏈表
(3)最底層(Level 1)的鏈表包含所有元素
(4)如果一個(gè)元素出現(xiàn)在Level(x)的鏈表中酥艳，則它在Level(x-n)的鏈表中也都會(huì)出現(xiàn)。
(5)每個(gè)節(jié)點(diǎn)包含兩個(gè)指針爬骤，一個(gè)指向下一個(gè)元素充石，一個(gè)指向下面一層的元素
跳表的搜索
例子：查找元素117
(1)比較21，比21大霞玄，往后面找
(2)比較37,比37大骤铃，比鏈表最大值小，從37的下面一層開(kāi)始找
(3)比較71,比71大坷剧，比鏈表最大值小惰爬，從71的下面一層開(kāi)始找
(4)比較85，比85大惫企，從后面找
(5)比較117撕瞧，等于117，找到了節(jié)點(diǎn)狞尔。
跳表的插入
先確定該元素要占據(jù)的層數(shù)K（采用丟硬幣的方式丛版，這完全是隨機(jī)的）
然后在Level 1 ...
Level K各個(gè)層的鏈表都插入元素。
例子：插入119偏序，K = 2
如果K大于鏈表的層數(shù)页畦，則要添加新的層。
例子：插入119研儒，K = 4
丟硬幣決定K
插入元素的時(shí)候豫缨，元素所占有的層數(shù)完全是隨機(jī)的独令，通過(guò)一下隨機(jī)算法產(chǎn)生：
相當(dāng)與做一次丟硬幣的實(shí)驗(yàn)，如果遇到正面好芭，繼續(xù)丟燃箭，遇到反面，則停止舍败，
用實(shí)驗(yàn)中丟硬幣的次數(shù)K作為元素占有的層數(shù)遍膜。顯然隨機(jī)變量K滿足參數(shù)為p = 1/2的幾何分布，
K的期望值E[K] = 1/p = 2.就是說(shuō)瓤湘，各個(gè)元素的層數(shù)，期望值是2層恩尾。
跳表的刪除
在各個(gè)層中找到包含x的節(jié)點(diǎn)弛说，使用標(biāo)準(zhǔn)的delete from list方法刪除該節(jié)點(diǎn)。
例子：刪除71
java實(shí)現(xiàn):
