誰說有序鏈表不能進行二分查找？！
關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識！
前言
本文收錄于專輯：http://dwz.win/HjK，點擊解鎖更多數(shù)據(jù)結(jié)構(gòu)與算法的知識。
你好，我是彤哥。
上一節(jié)，我們一起學(xué)習(xí)了關(guān)于哈希的一切，特別是哈希表的進化過程，相信通過上一節(jié)的學(xué)習(xí)，你一定可以從頭到尾完整地給面試官講講哈希表是如何發(fā)展到如今這一步的。
但是，難道HashMap的終極形態(tài)只能通過“數(shù)組+鏈表+紅黑樹”的形式實現(xiàn)嗎？有沒有可替代方案？為什么Java沒有使用你說的這種替代方案呢？
本節(jié)，我們就來學(xué)習(xí)另外一種數(shù)據(jù)結(jié)構(gòu)——跳表，關(guān)于跳表的內(nèi)容，我將分成兩節(jié)完成，第一節(jié)介紹跳表的演進過程，第二節(jié)代碼實現(xiàn)跳表，并改寫HashMap。
好了，讓我們先進入跳表第一小節(jié)的學(xué)習(xí)。
有序數(shù)組
大家都知道數(shù)組是可以支持隨機訪問的，也就是通過下標(biāo)可以快速地定位到元素，時間復(fù)雜度是O(1)。
那么，這個隨機訪問的特性除了根據(jù)下標(biāo)查找元素，還具有哪些用處呢？
試想，如果一個數(shù)組是有序的，我要查找某個指定的元素，如何才能做到最快速地查找出來呢？
簡單的方法，從頭開始遍歷整個數(shù)組，遇到了要查找的元素就返回，比如，查找8這個元素，要走6次才能查找到，要查找10這個元素更夸張，需要8次。
所以，這種方式的查找元素的時間復(fù)雜度為O(n)。
快速的方法，因為數(shù)組本身是有序的，所以，我們可以使用二分查找，先從中間開始查找，如果指定元素比中間的元素小，再在左半邊查找，如果指定元素比中間元素大，則在右半邊查找，依次進行，直到找到指定元素。比如，查找8這個元素，先定位到中間（7/2=3）的位置，下一次查找讓左指針加1，把4號位置作為左指針，中間的位置變?yōu)?4+(7-4)/2=5)的位置，查找到8這個元素，一共只需要2次。
使用二分查找，效率提升了不止一星半點，即使最壞的情況也只需要log(n)的時間復(fù)雜度。
有序鏈表
上面我們介紹了有序數(shù)組的快速查找，下面我們再來看看有序鏈表的情況。
上面是一個有序鏈表，此時，我要查找8這個元素，只能從鏈表頭開始查找，直到遇到8為止，時間復(fù)雜為O(n)，似乎沒有什么更好的辦法了。
讓我們考慮有序數(shù)組和有序鏈表的不同之處，有序數(shù)組之所以能夠?qū)崿F(xiàn)可以直接定位到中間元素，得意于其可以通過索引（下標(biāo)）快速訪問的特性，那么，我們給有序鏈表加上索引是不是就可以實現(xiàn)類似的功能了呢？
答案是肯定的，這種具有索引的有序鏈表就是跳表，下面有請?zhí)淼菆觥?/p>
跳表
第一個問題：怎么給有序鏈表加索引呢？
這里，需要增加一個“層”的概念，假設(shè)原始鏈表的層級為0，那么，在其中選擇一些元素向上延伸，形成第1層索引，同樣地，在第1層索引的基礎(chǔ)上，再選擇一些元素向上延伸，形成第2層索引，直到你覺得索引的層數(shù)差不多了為止，沒錯，跳表就是這么隨意，你滿意就好^^
假設(shè)，針對上面的有序鏈表，我加了這么一些索引：
第二個問題：從哪開始訪問這個跳表呢？6？3？1？9？
好像都不行，所以，還要增加一個特殊的節(jié)點——頭節(jié)點，放在0號元素的前面，比如，上面的跳表增加頭節(jié)點之后的樣子如下：
此時，只要從h2這個節(jié)點開始，就能很快速地查找到跳表中的任意一個元素。
比如，要查找8這個元素，h2先向右看一下，咦，是6，比8小，跳到6這個位置，再向右看一下，啊，是9了，比8大了，所以，不能跳過去，向下跳一步，跳到第1層6的位置，向右看一下，又是9，不能跳過去，再向下跳一步，到第0層的6，既然，到第0層，那只能按照鏈表依次往后遍歷了，直到遇到8為止，整個過程如下：
可以看到，整個過程就是跳呀跳呀跳，所以得名——跳表。
這里的元素個數(shù)比較少，可能還看不出太大的優(yōu)勢，試想，如果元素非常多，每兩個元素向上形成一個索引，每兩個索引再向上形成一個索引，最后，就類似于一顆平衡二叉樹了：
可以看到，每次查找可以減少一半的搜索范圍，所以，跳表的查詢時間復(fù)雜度為O(log n)。
但是，實際情況是不可能使用這種完全平衡的跳表的，因為，如果要保持平衡的特性，在插入元素或刪除元素的時候勢必需要做再平衡的操作，這樣就大大地降低了效率，所以，一般地，我們使用隨機來決定一個元素或者索引要不要產(chǎn)生索引。
第三個問題：索引何時產(chǎn)生呢？
最好的時機莫過于插入元素的時候，因為在插入元素之后的下一步就要立馬使用索引了，為什么這樣說呢？因為不管是插入、刪除還是查詢，其實，都要先走查詢找到那個元素才能進行下一步操作。說白了，就是不管什么操作，都要查詢，是查詢就要走索引，要走索引就要先建索引，要建索引那就在插入元素的時候。
OK，下面我將使用一步一圖的方式，帶你領(lǐng)略跳表創(chuàng)建的完整過程：
初始狀態(tài)，只有一個頭節(jié)點h0（不，還有一個彤哥讀源碼的水印，調(diào)皮^^）。
插入一個元素4，放在h0后面，并隨機決定要不要向上形成索引，結(jié)果是不形成索引。
插入一個元素3，從h0開始查找，h0的下一個元素是4，比3大，所以，3放在h0和4之間，然后詢問要不要形成索引，隨機決定說要形成索引，此時，3向上形成索引，同時，h0也要向上形成索引h1，結(jié)果如下：
插入一個元素9，從h1開始查找，依次經(jīng)過h1->3->3->4，都沒有找到位置，最后插入到4后面，并詢問要不要形成索引，隨機決定說我要形成索引，而且我要形成2層索引（最多比當(dāng)前層數(shù)多1），然后就變成了這個樣子：
接著，插入了元素1和7，它們都無驚無喜，沒有形成索引：
插入元素6，根據(jù)索引，查找路線為，h2->h1->3->3->4，咦，發(fā)現(xiàn)4下一個是7了，所以，6放在4和7之間，然后，決定要不要形成索引，隨機決定說我要形成索引，而且我也要形成2層索引，這時候就很麻煩了，在形成6這個元素索引的時候，需要修改3->9這條線，還要修改h2->9這條線，生成的結(jié)果如下：
后面，插入了元素8和10，都是無驚無險，沒有產(chǎn)生任何索引，所以，最后的結(jié)果如下：
可以看到，跳表是一個非常隨意的數(shù)據(jù)結(jié)構(gòu)，即使按照同樣的順序重新插入一遍元素，生成的跳表也可能完全不一樣，任性，所以，我很喜歡跳表這種數(shù)據(jù)結(jié)構(gòu)。
第四個問題：上面描述了插入元素的過程，刪除過程是怎么樣的呢？
刪除過程，首先也要查找到元素，但是，有一點點小區(qū)別，非常小的區(qū)別，很難描述，比如，要刪除6這個元素，我能不能從h2->6->6->6這個路徑過來呢？
不能，因為從這條路徑過來，刪除第1層的索引6后，無法修復(fù)3->9這條線，所以，刪除元素的時候只能走h2->h1->3->3->4->6這條路徑，且把途中每一層最后經(jīng)過的索引記住，才能在刪除了6這個元素之后正確地修復(fù)各層的索引。
刪除6之后的樣子如下：
咦，講到這里，我不經(jīng)想起了Java跳表ConcurrentSkipListMap中的一個小優(yōu)化項，在ConcurrentSkipListMap中，不管是查找、插入，還是刪除，都是走的跟刪除相同的查找路徑，其實，可以簡單地優(yōu)化一下，插入和查找的時候完全可以走另一條路徑。
有興趣的同學(xué)可以扒一下我的源碼分析：死磕 java集合之ConcurrentSkipListMap源碼分析
好了，關(guān)于跳表的理論知識我們就講解到這里。
后記
本節(jié)，我們通過一步一圖的方式完整清晰地展示了跳表查找、插入、刪除元素的全過程，你有沒有Get到呢？能吊打面試官了么？
然而，很多同學(xué)可能會說“Talk is cheap, Show me the code”，OK，下一節(jié)，我就將用代碼的方式給你展現(xiàn)跳表實現(xiàn)的細(xì)節(jié)，并使用跳表改寫HashMap，Next Part 見。
關(guān)注公眾號“彤哥讀源碼”，解鎖更多源碼、基礎(chǔ)、架構(gòu)知識。