先讓我們看一個(gè)問題：如果要存一組有序的 int 型數(shù)據(jù)集合，我們可以如何實(shí)現(xiàn)？
- 數(shù)組
可能大多數(shù)同學(xué)最先想到的是用數(shù)據(jù)實(shí)現(xiàn)，將有序的數(shù)據(jù)集合存放在數(shù)據(jù)中，可以使用二分法進(jìn)行查找，效率比較高，但是對于新增和刪除的操作并不友好，因?yàn)檫@些操作都需要移動后面位置的元素。
- 鏈表
那么有沒有什么數(shù)據(jù)結(jié)構(gòu)可以讓查詢、新增、刪除操作都變得很快呢？這就是我們今天要介紹的跳躍表了，讓我們看幾張圖，很容易理解。
跳躍表
如上圖，一個(gè)有序的鏈表，如果要找值為 50 的節(jié)點(diǎn)，需要從第一個(gè)節(jié)點(diǎn)開始遍歷，查詢最后才能找到值為 50 的節(jié)點(diǎn)。
我們給這個(gè)鏈表加一層索引，如圖：
我們按照一級索引來查詢（橙色查詢路線），可以發(fā)現(xiàn)我們至少可以少遍歷一半的節(jié)點(diǎn)。
還覺得有些慢？，那么再增加一層，再加一層，如圖：
是不是更快地找到我們需要的節(jié)點(diǎn)了，當(dāng)然這里的節(jié)點(diǎn)數(shù)量不夠多，如果節(jié)點(diǎn)數(shù)量非常多，查找效率提升會更加明顯。
如果需要找中間的某個(gè)節(jié)點(diǎn)，比如尋找 42 ，過程大概是這樣的：
插入節(jié)點(diǎn)
看懂了跳躍表的數(shù)據(jù)結(jié)構(gòu)，那么就很容易理解節(jié)點(diǎn)的插入操作了，基本上兩步操作就可以實(shí)現(xiàn)：在最底層的數(shù)據(jù)鏈表中插入數(shù)據(jù)，然后調(diào)整索引；
其中每一層的索引鏈表中是否需要增加新增的節(jié)點(diǎn)，其實(shí)并沒有什么標(biāo)準(zhǔn)答案，我們盡量做到索引的平均分布即可，常用的就是【隨機(jī)判斷】決定是否需要新增或調(diào)整索引，當(dāng)有新節(jié)點(diǎn)插入的時(shí)候，通過概率算法判斷這個(gè)節(jié)點(diǎn)需要插入到幾級節(jié)點(diǎn)中。
比如：
底層數(shù)據(jù)鏈表有 N 個(gè)元素，隨機(jī)選擇 N/2 個(gè)元素作為 1 級索引，隨機(jī)選擇 N/4 個(gè)元素作為 2 級索引...一直到頂層索引；
新插入數(shù)據(jù)節(jié)點(diǎn)，1/2 概率不插入任何一級索引，1/4 概率返回需要插入 1 級索引，1/8 概率返回需要插入到 2 級索引，以此類推；
這里要注意一點(diǎn)，插入 2 級索引的時(shí)候，同時(shí)也需要插入 1 級索引；也就是插入 n 級索引的時(shí)候，同時(shí)也要插入 1~( n-1 ) 級索引。
刪除節(jié)點(diǎn)
跳躍表刪除節(jié)點(diǎn)就更簡單了，刪除數(shù)據(jù)節(jié)點(diǎn)，并刪除每一層的索引節(jié)點(diǎn)（如果有的話）。
總結(jié)來說：
可以把跳躍表看成多個(gè)有序鏈表（最底層的數(shù)據(jù)鏈表+多層索引鏈表）；
查找的過程中，從最長層開始查找，找到對應(yīng)的區(qū)間再到下一層查找 ；
每個(gè)節(jié)點(diǎn)都有兩個(gè)指針，分別指向右邊和下邊；
插入新節(jié)點(diǎn)時(shí)，隨機(jī)判斷該節(jié)點(diǎn)是否要插入索引，最高插入幾級索引；
插入 n 級索引的時(shí)候，同時(shí)也要插入 1~(n-1) 級索引；
跳躍表和紅黑樹等平衡樹相比，更容易實(shí)現(xiàn)，并且不需要維護(hù)平衡性；
Redis 中的 ZSet 的一種實(shí)現(xiàn)方式是 skipList 與 hashTable 的結(jié)合；
Google 的 LevelDB 、Facebook 的 RocksDB ，它們都是使用了跳躍表這種數(shù)據(jù)結(jié)構(gòu)。
會點(diǎn)代碼的大叔 | 文【原創(chuàng)】
