跳表是一種神奇的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閹缀跛邪姹镜拇髮W(xué)本科教材上都沒(méi)有跳表這種數(shù)據(jù)結(jié)構(gòu)凛篙，而且神書(shū)《算法導(dǎo)論》、《算法第四版》這兩本書(shū)中也沒(méi)有介紹跳表栏渺。但是跳表插入呛梆、刪除、查找元素的時(shí)間復(fù)雜度跟紅黑樹(shù)都是一樣量級(jí)的迈嘹，時(shí)間復(fù)雜度都是O(logn)削彬，而且跳表有一個(gè)特性是紅黑樹(shù)無(wú)法匹敵的（具體什么特性后面會(huì)提到）全庸。所以在工業(yè)中秀仲，跳表也會(huì)經(jīng)常被用到融痛。廢話不多說(shuō)了，開(kāi)始今天的跳表學(xué)習(xí)神僵。
通過(guò)本文雁刷，你能 get 到以下知識(shí)：
- 什么是跳表？
- 跳表的查找保礼、插入沛励、刪除元素的流程
- 跳表查找、插入炮障、刪除元素的時(shí)間復(fù)雜度
- 跳表插入元素時(shí)目派，如何動(dòng)態(tài)維護(hù)索引？
- 為什么Redis選擇使用跳表而不是紅黑樹(shù)來(lái)實(shí)現(xiàn)有序集合胁赢？
- 工業(yè)上其他使用跳表的場(chǎng)景
友情提示：下文在跳表插入數(shù)據(jù)時(shí)企蹭，會(huì)講述如何動(dòng)態(tài)維護(hù)索引，實(shí)現(xiàn)比較簡(jiǎn)單智末，邏輯比較繞谅摄，不要放棄，加油Ｏ倒荨Ｋ湍！如果一遍看不懂沒(méi)關(guān)系由蘑，可以選擇暫時(shí)性的跳過(guò)闽寡，畢竟這塊偏向于源碼。但是讀者必須知道跳表的查找尼酿、插入下隧、刪除的時(shí)間復(fù)雜度都是 O(logn)，而且可以按照范圍區(qū)間查找元素谓媒，當(dāng)工作中遇到某些場(chǎng)景時(shí)淆院，需要想到可以使用跳表解決問(wèn)題即可。畢竟平時(shí)的工作都是直接使用封裝好的跳表句惯，例如：java.util.concurrent 下的 ConcurrentSkipListMap()土辩。
理解跳表，從單鏈表開(kāi)始說(shuō)起
下圖是一個(gè)簡(jiǎn)單的有序單鏈表抢野，單鏈表的特性就是每個(gè)元素存放下一個(gè)元素的引用拷淘。即：通過(guò)第一個(gè)元素可以找到第二個(gè)元素，通過(guò)第二個(gè)元素可以找到第三個(gè)元素指孤，依次類推启涯，直到找到最后一個(gè)元素贬堵。
現(xiàn)在我們有個(gè)場(chǎng)景，想快速找到上圖鏈表中的 10 這個(gè)元素结洼，只能從頭開(kāi)始遍歷鏈表黎做，直到找到我們需要找的元素。查找路徑：1松忍、3蒸殿、4、5鸣峭、7宏所、8、9摊溶、10爬骤。這樣的查找效率很低，平均時(shí)間復(fù)雜度很高O(n)莫换。那有沒(méi)有辦法提高鏈表的查找速度呢霞玄？如下圖所示，我們從鏈表中每?jī)蓚€(gè)元素抽出來(lái)浓镜，加一級(jí)索引溃列，一級(jí)索引指向了原始鏈表，即：通過(guò)一級(jí)索引 7 的down指針可以找到原始鏈表的 7 膛薛。那現(xiàn)在怎么查找 10 這個(gè)元素呢听隐？
先在索引找 1、4哄啄、7雅任、9，遍歷到一級(jí)索引的 9 時(shí)咨跌，發(fā)現(xiàn) 9 的后繼節(jié)點(diǎn)是 13沪么，比 10 大，于是不往后找了锌半，而是通過(guò) 9 找到原始鏈表的 9禽车，然后再往后遍歷找到了我們要找的 10，遍歷結(jié)束刊殉。有沒(méi)有發(fā)現(xiàn)殉摔，加了一級(jí)索引后，查找路徑：1记焊、4逸月、7、9遍膜、10碗硬，查找節(jié)點(diǎn)需要遍歷的元素相對(duì)少了瓤湘，我們不需要對(duì) 10 之前的所有數(shù)據(jù)都遍歷，查找的效率提升了恩尾。
那如果加二級(jí)索引呢弛说？如下圖所示，查找路徑：1特笋、7剃浇、9巾兆、10猎物。是不是找 10 的效率更高了？這就是跳表的思想角塑，用“空間換時(shí)間”蔫磨，通過(guò)給鏈表建立索引，提高了查找的效率圃伶。
可能同學(xué)們會(huì)想堤如，從上面案例來(lái)看，提升的效率并不明顯窒朋，本來(lái)需要遍歷8個(gè)元素搀罢，優(yōu)化了半天，還需要遍歷 4 個(gè)元素侥猩，其實(shí)是因?yàn)槲覀兊臄?shù)據(jù)量太少了榔至，當(dāng)數(shù)據(jù)量足夠大時(shí)，效率提升會(huì)很大欺劳。如下圖所示唧取，假如有序單鏈表現(xiàn)在有1萬(wàn)個(gè)元素，分別是 0~9999』幔現(xiàn)在我們建了很多級(jí)索引枫弟，最高級(jí)的索引，就兩個(gè)元素 0鹏往、5000淡诗，次高級(jí)索引四個(gè)元素 0、2500伊履、5000韩容、7500，依次類推湾碎，當(dāng)我們查找 7890 這個(gè)元素時(shí)宙攻，查找路徑為 0、5000介褥、7500 ... 7890座掘，通過(guò)最高級(jí)索引直接跳過(guò)了5000個(gè)元素递惋，次高層索引直接跳過(guò)了2500個(gè)元素，從而使得鏈表能夠?qū)崿F(xiàn)二分查找溢陪。由此可以看出萍虽，當(dāng)元素?cái)?shù)量較多時(shí)，索引提高的效率比較大形真，近似于二分查找杉编。
到這里大家應(yīng)該已經(jīng)明白了什么是跳表咆霜。跳表是可以實(shí)現(xiàn)二分查找的有序鏈表邓馒。
查找的時(shí)間復(fù)雜度
既然跳表可以提升鏈表查找元素的效率，那查找一個(gè)元素的時(shí)間復(fù)雜度到底是多少呢蛾坯？查找元素的過(guò)程是從最高級(jí)索引開(kāi)始光酣，一層一層遍歷最后下沉到原始鏈表。所以脉课，時(shí)間復(fù)雜度 = 索引的高度 * 每層索引遍歷元素的個(gè)數(shù)救军。
先來(lái)求跳表的索引高度。如下圖所示倘零，假設(shè)每?jī)蓚€(gè)結(jié)點(diǎn)會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)唱遭，原始的鏈表有n個(gè)元素，則一級(jí)索引有n/2 個(gè)元素呈驶、二級(jí)索引有 n/4 個(gè)元素拷泽、k級(jí)索引就有 n/2k個(gè)元素。最高級(jí)索引一般有2個(gè)元素俐东，即：最高級(jí)索引 h 滿足 2 = n/2h跌穗，即 h = log2n - 1，最高級(jí)索引 h 為索引層的高度加上原始數(shù)據(jù)一層虏辫，跳表的總高度 h = log2n蚌吸。
我們看上圖中加粗的箭頭，表示查找元素 x 的路徑砌庄，那查找過(guò)程中每一層索引最多遍歷幾個(gè)元素呢羹唠？
圖中所示，現(xiàn)在到達(dá)第 k 級(jí)索引娄昆，我們發(fā)現(xiàn)要查找的元素 x 比 y 大比 z 小佩微，所以，我們需要從 y 處下降到 k-1 級(jí)索引繼續(xù)查找萌焰，k-1級(jí)索引中比 y 大比 z 小的只有一個(gè) w哺眯，所以在 k-1 級(jí)索引中，我們遍歷的元素最多就是 y扒俯、w奶卓、z一疯，發(fā)現(xiàn) x 比 w大比 z 小之后，再下降到 k-2 級(jí)索引夺姑。所以墩邀，k-2 級(jí)索引最多遍歷的元素為 w、u盏浙、z眉睹。其實(shí)每級(jí)索引都是類似的道理，每級(jí)索引中都是兩個(gè)結(jié)點(diǎn)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)废膘。 現(xiàn)在我們得出結(jié)論：當(dāng)每級(jí)索引都是兩個(gè)結(jié)點(diǎn)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)時(shí)竹海，每一層最多遍歷3個(gè)結(jié)點(diǎn)。
跳表的索引高度 h = log2n殖卑，且每層索引最多遍歷 3 個(gè)元素站削。所以跳表中查找一個(gè)元素的時(shí)間復(fù)雜度為 O(3*logn)坊萝，省略常數(shù)即：O(logn)孵稽。
空間復(fù)雜度
跳表通過(guò)建立索引，來(lái)提高查找元素的效率十偶，就是典型的“空間換時(shí)間”的思想菩鲜，所以在空間上做了一些犧牲，那空間復(fù)雜度到底是多少呢惦积？
假如原始鏈表包含 n 個(gè)元素接校，則一級(jí)索引元素個(gè)數(shù)為 n/2、二級(jí)索引元素個(gè)數(shù)為 n/4狮崩、三級(jí)索引元素個(gè)數(shù)為 n/8 以此類推蛛勉。所以，索引節(jié)點(diǎn)的總和是：n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n-2睦柴，空間復(fù)雜度是 O(n)诽凌。
如下圖所示：如果每三個(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)做為索引，索引總和數(shù)就是 n/3 + n/9 + n/27 + … + 9 + 3 + 1= n/2坦敌，減少了一半侣诵。所以我們可以通過(guò)較少索引數(shù)來(lái)減少空間復(fù)雜度，但是相應(yīng)的肯定會(huì)造成查找效率有一定下降狱窘，我們可以根據(jù)我們的應(yīng)用場(chǎng)景來(lái)控制這個(gè)閾值杜顺，看我們更注重時(shí)間還是空間。
But蘸炸，索引結(jié)點(diǎn)往往只需要存儲(chǔ) key 和幾個(gè)指針躬络，并不需要存儲(chǔ)完整的對(duì)象，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)搭儒，索引占用的額外空間就可以忽略了穷当。舉個(gè)例子：我們現(xiàn)在需要用跳表來(lái)給所有學(xué)生建索引越锈，學(xué)生有很多屬性：學(xué)號(hào)、姓名膘滨、性別甘凭、身份證號(hào)、年齡火邓、家庭住址丹弱、身高、體重等铲咨。學(xué)生的各種屬性只需要在原始鏈表中存儲(chǔ)一份即可躲胳，我們只需要用學(xué)生的學(xué)號(hào)（int 類型的數(shù)據(jù)）建立索引，所以索引相對(duì)原始數(shù)據(jù)而言纤勒，占用的空間可以忽略坯苹。
插入數(shù)據(jù)
插入數(shù)據(jù)看起來(lái)也很簡(jiǎn)單，跳表的原始鏈表需要保持有序摇天，所以我們會(huì)向查找元素一樣粹湃，找到元素應(yīng)該插入的位置。如下圖所示泉坐，要插入數(shù)據(jù)6为鳄，整個(gè)過(guò)程類似于查找6，整個(gè)的查找路徑為 1腕让、1孤钦、1、4纯丸、4偏形、5。查找到第底層原始鏈表的元素 5 時(shí)觉鼻，發(fā)現(xiàn) 5 小于 6 但是后繼節(jié)點(diǎn) 7 大于 6俊扭，所以應(yīng)該把 6 插入到 5 之后 7 之前。整個(gè)時(shí)間復(fù)雜度為查找元素的時(shí)間復(fù)雜度 O(logn)滑凉。
如下圖所示统扳，假如一直往原始列表中添加數(shù)據(jù)，但是不更新索引畅姊，就可能出現(xiàn)兩個(gè)索引節(jié)點(diǎn)之間數(shù)據(jù)非常多的情況咒钟，極端情況，跳表退化為單鏈表若未，從而使得查找效率從 O(logn) 退化為 O(n)朱嘴。那這種問(wèn)題該怎么解決呢？我們需要在插入數(shù)據(jù)的時(shí)候，索引節(jié)點(diǎn)也需要相應(yīng)的增加萍嬉、或者重建索引乌昔，來(lái)避免查找效率的退化。那我們?cè)撊绾稳ゾS護(hù)這個(gè)索引呢壤追？
比較容易理解的做法就是完全重建索引，我們每次插入數(shù)據(jù)后行冰，都把這個(gè)跳表的索引刪掉全部重建溺蕉，重建索引的時(shí)間復(fù)雜度是多少呢？因?yàn)樗饕目臻g復(fù)雜度是 O(n)悼做，即：索引節(jié)點(diǎn)的個(gè)數(shù)是 O(n) 級(jí)別疯特，每次完全重新建一個(gè) O(n) 級(jí)別的索引，時(shí)間復(fù)雜度也是 O(n) 肛走。造成的后果是：為了維護(hù)索引漓雅，導(dǎo)致每次插入數(shù)據(jù)的時(shí)間復(fù)雜度變成了 O(n)。
那有沒(méi)有其他效率比較高的方式來(lái)維護(hù)索引呢朽色？假如跳表每一層的晉升概率是 1/2邻吞，最理想的索引就是在原始鏈表中每隔一個(gè)元素抽取一個(gè)元素做為一級(jí)索引。換種說(shuō)法纵搁，我們?cè)谠兼湵碇须S機(jī)的選 n/2 個(gè)元素做為一級(jí)索引是不是也能通過(guò)索引提高查找的效率呢吃衅？ 當(dāng)然可以了，因?yàn)橐话汶S機(jī)選的元素相對(duì)來(lái)說(shuō)都是比較均勻的腾誉。如下圖所示，隨機(jī)選擇了n/2 個(gè)元素做為一級(jí)索引峻呕，雖然不是每隔一個(gè)元素抽取一個(gè)利职，但是對(duì)于查找效率來(lái)講，影響不大瘦癌，比如我們想找元素 16猪贪，仍然可以通過(guò)一級(jí)索引，使得遍歷路徑較少了將近一半讯私。如果抽取的一級(jí)索引的元素恰好是前一半的元素 1热押、3、4斤寇、5桶癣、7、8娘锁，那么查找效率確實(shí)沒(méi)有提升牙寞，但是這樣的概率太小了。我們可以認(rèn)為：當(dāng)原始鏈表中元素?cái)?shù)量足夠大，且抽取足夠隨機(jī)的話间雀，我們得到的索引是均勻的悔详。我們要清楚設(shè)計(jì)良好的數(shù)據(jù)結(jié)構(gòu)都是為了應(yīng)對(duì)大數(shù)據(jù)量的場(chǎng)景，如果原始鏈表只有 5 個(gè)元素惹挟，那么依次遍歷 5 個(gè)元素也沒(méi)有關(guān)系茄螃，因?yàn)閿?shù)據(jù)量太少了。所以连锯，我們可以維護(hù)一個(gè)這樣的索引：隨機(jī)選 n/2 個(gè)元素做為一級(jí)索引责蝠、隨機(jī)選 n/4 個(gè)元素做為二級(jí)索引、隨機(jī)選 n/8 個(gè)元素做為三級(jí)索引萎庭，依次類推霜医，一直到最頂層索引。這里每層索引的元素個(gè)數(shù)已經(jīng)確定驳规，且每層索引元素選取的足夠隨機(jī)肴敛，所以可以通過(guò)索引來(lái)提升跳表的查找效率。
那代碼該如何實(shí)現(xiàn)吗购，才能使跳表滿足上述這個(gè)樣子呢医男？可以在每次新插入元素的時(shí)候，盡量讓該元素有 1/2 的幾率建立一級(jí)索引捻勉、1/4 的幾率建立二級(jí)索引镀梭、1/8 的幾率建立三級(jí)索引，以此類推踱启，就能滿足我們上面的條件”ㄕ耍現(xiàn)在我們就需要一個(gè)概率算法幫我們把控這個(gè) 1/2、1/4埠偿、1/8 ... 透罢，當(dāng)每次有數(shù)據(jù)要插入時(shí)，先通過(guò)概率算法告訴我們這個(gè)元素需要插入到幾級(jí)索引中冠蒋，然后開(kāi)始維護(hù)索引并把數(shù)據(jù)插入到原始鏈表中羽圃。下面開(kāi)始講解這個(gè)概率算法代碼如何實(shí)現(xiàn)。
我們可以實(shí)現(xiàn)一個(gè) randomLevel() 方法抖剿，該方法會(huì)隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)（MAX_LEVEL表示索引的最高層數(shù)）朽寞，且該方法有 1/2 的概率返回 1、1/4 的概率返回 2斩郎、1/8的概率返回 3脑融，以此類推。
- randomLevel() 方法返回 1 表示當(dāng)前插入的該元素不需要建索引孽拷，只需要存儲(chǔ)數(shù)據(jù)到原始鏈表即可（概率 1/2）
- randomLevel() 方法返回 2 表示當(dāng)前插入的該元素需要建一級(jí)索引（概率 1/4）
- randomLevel() 方法返回 3 表示當(dāng)前插入的該元素需要建二級(jí)索引（概率 1/8）
- randomLevel() 方法返回 4 表示當(dāng)前插入的該元素需要建三級(jí)索引（概率 1/16）
- 吨掌。。。以此類推
所以膜宋，通過(guò) randomLevel() 方法窿侈，我們可以控制整個(gè)跳表各級(jí)索引中元素的個(gè)數(shù)。重點(diǎn)來(lái)了：randomLevel() 方法返回 2 的時(shí)候會(huì)建立一級(jí)索引秋茫，我們想要一級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/2史简，但是 randomLevel() 方法返回 2 的概率為 1/4，那是不是有矛盾呢肛著？明明說(shuō)好的 1/2圆兵，結(jié)果一級(jí)索引元素個(gè)數(shù)怎么變成了原始鏈表的 1/4？我們先看下圖枢贿，應(yīng)該就明白了殉农。
假設(shè)我們?cè)诓迦朐?6 的時(shí)候，randomLevel() 方法返回 1局荚，則我們不會(huì)為 6 建立索引超凳。插入 7 的時(shí)候，randomLevel() 方法返回3 耀态，所以我們需要為元素 7 建立二級(jí)索引轮傍。這里我們發(fā)現(xiàn)了一個(gè)特點(diǎn)：當(dāng)建立二級(jí)索引的時(shí)候，同時(shí)也會(huì)建立一級(jí)索引首装；當(dāng)建立三級(jí)索引時(shí)蕾总，同時(shí)也會(huì)建立一級(jí)师抄、二級(jí)索引鼻忠。所以混蔼，一級(jí)索引中元素的個(gè)數(shù)等于 [ 原始鏈表元素個(gè)數(shù) ] * [ randomLevel() 方法返回值 > 1 的概率 ]。因?yàn)?randomLevel() 方法返回值 > 1就會(huì)建索引桨醋，凡是建索引棚瘟，無(wú)論幾級(jí)索引必然有一級(jí)索引，所以一級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)個(gè)數(shù)的比率為 randomLevel() 方法返回值 > 1 的概率喜最。那 randomLevel() 方法返回值 > 1 的概率是多少呢？因?yàn)?randomLevel() 方法隨機(jī)生成 1~MAX_LEVEL 的數(shù)字庄蹋，且 randomLevel() 方法返回值 1 的概率為 1/2瞬内，則 randomLevel() 方法返回值 > 1 的概率為 1 - 1/2 = 1/2。即通過(guò)上述流程實(shí)現(xiàn)了一級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)個(gè)數(shù)的 1/2限书。
同理虫蝶，當(dāng) randomLevel() 方法返回值 > 2 時(shí)，會(huì)建立二級(jí)或二級(jí)以上索引倦西，都會(huì)在二級(jí)索引中增加元素能真，因此二級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的比率為 randomLevel() 方法返回值 > 2 的概率。 randomLevel() 方法返回值 > 2 的概率為 1 減去 randomLevel() = 1 或 =2 的概率，即 1 - 1/2 - 1/4 = 1/4粉铐。OK疼约，達(dá)到了我們?cè)O(shè)計(jì)的目標(biāo)：二級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/4。
以此類推蝙泼，可以得出程剥，遵守以下兩個(gè)條件：
- randomLevel() 方法，隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)（MAX_LEVEL表示索引的最高層數(shù)）汤踏，且有 1/2的概率返回 1织鲸、1/4的概率返回 2、1/8的概率返回 3 ...
- randomLevel() 方法返回 1 不建索引溪胶、返回2建一級(jí)索引搂擦、返回 3 建二級(jí)索引、返回 4 建三級(jí)索引 ...
就可以滿足我們想要的結(jié)果哗脖，即：一級(jí)索引中元素個(gè)數(shù)應(yīng)該占原始數(shù)據(jù)的 1/2瀑踢，二級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/4，三級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/8 懒熙，依次類推丘损，一直到最頂層索引。
但是問(wèn)題又來(lái)了工扎，怎么設(shè)計(jì)這么一個(gè) randomLevel() 方法呢徘钥？直接擼代碼：
// 該 randomLevel 方法會(huì)隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)，且 ：
// 1/2 的概率返回 1
// 1/4 的概率返回 2
// 1/8 的概率返回 3 以此類推
private int randomLevel() {
int level = 1;
// 當(dāng) level < MAX_LEVEL肢娘，且隨機(jī)數(shù)小于設(shè)定的晉升概率時(shí)呈础，level + 1
while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
level += 1;
return level;
}
上述代碼可以實(shí)現(xiàn)我們的功能，而且橱健，我們的案例中晉升概率 SKIPLIST_P 設(shè)置的 1/2而钞，即：每?jī)蓚€(gè)結(jié)點(diǎn)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)。如果我們想節(jié)省空間利用率拘荡，可以適當(dāng)?shù)慕档痛a中的 SKIPLIST_P臼节，從而減少索引元素個(gè)數(shù)，Redis 的 zset 中 SKIPLIST_P 設(shè)定的 0.25珊皿。下圖所示网缝，是Redis t_zset.c 中 zslRandomLevel 函數(shù)的實(shí)現(xiàn)：
Redis 源碼中 (random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF) 在功能上等價(jià)于我代碼中的 Math.random() < SKIPLIST_P ，只不過(guò) Redis 作者 antirez 使用位運(yùn)算來(lái)提高浮點(diǎn)數(shù)比較的效率蟋定。
整體思路大家應(yīng)該明白了粉臊，那插入數(shù)據(jù)時(shí)維護(hù)索引的時(shí)間復(fù)雜度是多少呢？元素插入到單鏈表的時(shí)間復(fù)雜度為 O(1)驶兜，我們索引的高度最多為 logn扼仲，當(dāng)插入一個(gè)元素 x 時(shí)远寸，最壞的情況就是元素 x 需要插入到每層索引中，所以插入數(shù)據(jù)到各層索引中屠凶，最壞時(shí)間復(fù)雜度是 O(logn)驰后。
過(guò)程大概理解了，再通過(guò)一個(gè)例子描述一下跳表插入數(shù)據(jù)的全流程≡某耄現(xiàn)在我們要插入數(shù)據(jù) 6 到跳表中倡怎，首先 randomLevel() 返回 3，表示需要建二級(jí)索引贱枣，即：一級(jí)索引和二級(jí)索引需要增加元素 6监署。該跳表目前最高三級(jí)索引，首先找到三級(jí)索引的 1纽哥，發(fā)現(xiàn) 6 比 1大比 13小钠乏，所以，從 1 下沉到二級(jí)索引春塌。
下沉到二級(jí)索引后晓避，發(fā)現(xiàn) 6 比 1 大比 7 小，此時(shí)需要在二級(jí)索引中 1 和 7 之間加一個(gè)元素6 只壳，并從元素 1 繼續(xù)下沉到一級(jí)索引俏拱。
下沉到一級(jí)索引后，發(fā)現(xiàn) 6 比 1 大比 4 大吼句，所以往后查找锅必，發(fā)現(xiàn) 6 比 4 大比 7 小，此時(shí)需要在一級(jí)索引中 4 和 7 之間加一個(gè)元素 6 惕艳，并把二級(jí)索引的 6 指向 一級(jí)索引的 6搞隐，最后，從元素 4 繼續(xù)下沉到原始鏈表远搪。
下沉到原始鏈表后劣纲，就比較簡(jiǎn)單了，發(fā)現(xiàn) 4谁鳍、5 比 6小癞季，7比6大，所以將6插入到 5 和 7 之間即可倘潜，整個(gè)插入過(guò)程結(jié)束余佛。
整個(gè)插入過(guò)程的路徑與查找元素路徑類似， 每層索引中插入元素的時(shí)間復(fù)雜度 O(1)窍荧，所以整個(gè)插入的時(shí)間復(fù)雜度是 O(logn)。
刪除數(shù)據(jù)
跳表刪除數(shù)據(jù)時(shí)恨憎，要把索引中對(duì)應(yīng)節(jié)點(diǎn)也要?jiǎng)h掉蕊退。如下圖所示郊楣，如果要?jiǎng)h除元素 9，需要把原始鏈表中的 9 和第一級(jí)索引的 9 都刪除掉瓤荔。
跳表中净蚤，刪除元素的時(shí)間復(fù)雜度是多少呢？
刪除元素的過(guò)程跟查找元素的過(guò)程類似输硝，只不過(guò)在查找的路徑上如果發(fā)現(xiàn)了要?jiǎng)h除的元素 x今瀑，則執(zhí)行刪除操作。跳表中点把，每一層索引其實(shí)都是一個(gè)有序的單鏈表橘荠，單鏈表刪除元素的時(shí)間復(fù)雜度為 O(1)，索引層數(shù)為 logn 表示最多需要?jiǎng)h除 logn 個(gè)元素郎逃，所以刪除元素的總時(shí)間包含 查找元素的時(shí)間 加 刪除 logn個(gè)元素的時(shí)間 為 O(logn) + O(logn) = 2 O(logn)哥童，忽略常數(shù)部分，刪除元素的時(shí)間復(fù)雜度為 O(logn)褒翰。
總結(jié)
跳表是可以實(shí)現(xiàn)二分查找的有序鏈表贮懈；
每個(gè)元素插入時(shí)隨機(jī)生成它的level；
最底層包含所有的元素优训；
如果一個(gè)元素出現(xiàn)在level(x)朵你，那么它肯定出現(xiàn)在x以下的level中；
每個(gè)索引節(jié)點(diǎn)包含兩個(gè)指針揣非，一個(gè)向下抡医，一個(gè)向右；（筆記目前看過(guò)的各種跳表源碼實(shí)現(xiàn)包括Redis 的zset 都沒(méi)有向下的指針妆兑，那怎么從二級(jí)索引跳到一級(jí)索引呢魂拦？留個(gè)懸念，看源碼吧搁嗓，文末有跳表實(shí)現(xiàn)源碼）
跳表查詢芯勘、插入、刪除的時(shí)間復(fù)雜度為O(log n)腺逛，與平衡二叉樹(shù)接近荷愕；
為什么Redis選擇使用跳表而不是紅黑樹(shù)來(lái)實(shí)現(xiàn)有序集合？
Redis 中的有序集合(zset) 支持的操作：
插入一個(gè)元素
刪除一個(gè)元素
查找一個(gè)元素
有序輸出所有元素
按照范圍區(qū)間查找元素（比如查找值在 [100, 356] 之間的數(shù)據(jù)）
其中棍矛，前四個(gè)操作紅黑樹(shù)也可以完成安疗，且時(shí)間復(fù)雜度跟跳表是一樣的。但是够委，按照區(qū)間來(lái)查找數(shù)據(jù)這個(gè)操作荐类，紅黑樹(shù)的效率沒(méi)有跳表高。按照區(qū)間查找數(shù)據(jù)時(shí)茁帽，跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)玉罐，然后在原始鏈表中順序往后遍歷就可以了屈嗤，非常高效。
工業(yè)上其他使用跳表的場(chǎng)景
在博客上從來(lái)沒(méi)有見(jiàn)過(guò)有同學(xué)講述 HBase MemStore 的數(shù)據(jù)結(jié)構(gòu)吊输，其實(shí) HBase MemStore 內(nèi)部存儲(chǔ)數(shù)據(jù)就使用的跳表饶号。為什么呢？HBase 屬于 LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫(kù)季蚂，LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫(kù)有個(gè)特點(diǎn)茫船，實(shí)時(shí)寫(xiě)入的數(shù)據(jù)先寫(xiě)入到內(nèi)存，內(nèi)存達(dá)到閾值往磁盤(pán) flush 的時(shí)候扭屁，會(huì)生成類似于 StoreFile 的有序文件算谈，而跳表恰好就是天然有序的，所以在 flush 的時(shí)候效率很高疯搅，而且跳表查找濒生、插入、刪除性能都很高幔欧，這應(yīng)該是 HBase MemStore 內(nèi)部存儲(chǔ)數(shù)據(jù)使用跳表的原因之一罪治。HBase 使用的是 java.util.concurrent 下的 ConcurrentSkipListMap()。
Google 開(kāi)源的 key/value 存儲(chǔ)引擎 LevelDB 以及 Facebook 基于 LevelDB 優(yōu)化的 RocksDB 都是 LSM Tree 結(jié)構(gòu)的數(shù)據(jù)庫(kù)礁蔗，他們內(nèi)部的 MemTable 都是使用了跳表這種數(shù)據(jù)結(jié)構(gòu)觉义。
后期筆者還會(huì)輸出一篇深入剖析 LSM Tree 的博客，到時(shí)候再結(jié)合場(chǎng)景分析為什么使用跳表浴井。
參考：
極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法之美課程
- 王爭(zhēng)老師的整套課程都很棒晒骇，對(duì)數(shù)據(jù)結(jié)構(gòu)與算法想整體提高的同學(xué)可以訂閱
王爭(zhēng)老師SkipList 實(shí)現(xiàn)
- 這個(gè)跳表實(shí)現(xiàn)相對(duì)簡(jiǎn)單，建議初學(xué)者參考磺浙，整個(gè)項(xiàng)目是王爭(zhēng)老師極客時(shí)間課程配套的代碼洪囤，其他數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)也可以參考
- 筆記在寫(xiě)本博客期間，向該項(xiàng)目提交了 pr撕氧，已被merge瘤缩，模仿 redis 源碼重新實(shí)現(xiàn)了 randomLevel() 方法，不過(guò)為了容易理解沒(méi)有使用redis的位運(yùn)算伦泥，之前的 randomLevel() 方法會(huì)導(dǎo)致索引冗余特別嚴(yán)重剥啤，5 級(jí)以下的索引中元素個(gè)數(shù)接近于所有元素的個(gè)數(shù)，有興趣的同學(xué)可以繼續(xù)深入研究
源碼 5：凌波微步 —— 探索「跳躍列表」內(nèi)部結(jié)構(gòu)
- 老錢(qián)的《Redis 深度歷險(xiǎn)》系列非常推薦
- 彤哥讀源碼系列，把 Java java.util.concurrent 包下的大多數(shù)集合類從源碼層次深入分析了一遍防楷，非常推薦
歡迎關(guān)注筆者的博客牺丙，后續(xù)持續(xù)更新數(shù)據(jù)結(jié)構(gòu)與算法、大數(shù)據(jù)复局、Flink實(shí)戰(zhàn)以及原理性的文章
