因?yàn)檫@個(gè)周末加班，一直沒有更新，實(shí)屬抱歉，今天，我們來聊一聊一個(gè)數(shù)據(jù)結(jié)構(gòu)，跳表。跳表是redis的一個(gè)核心組件，也同時(shí)被廣泛地運(yùn)用到了各種緩存地實(shí)現(xiàn)當(dāng)中，它的主要優(yōu)點(diǎn)，就是可以跟紅黑樹、AVL等平衡樹一樣，做到比較穩(wěn)定地插入、查詢與刪除。理論插入查詢刪除的算法時(shí)間復(fù)雜度為O(logN)。
什么是跳表
鏈表，相信大家都不陌生，維護(hù)一個(gè)有序的鏈表是一件非常簡單的事情，我們都知道，在一個(gè)有序的鏈表里面，查詢跟插入的算法復(fù)雜度都是O(n)。
我們能不能進(jìn)行優(yōu)化呢，比如我們一次比較兩個(gè)呢？那樣不就可以把時(shí)間縮小一半？
同理，如果我們4個(gè)4個(gè)比，那不就更快了？
跳表就是這樣的一種數(shù)據(jù)結(jié)構(gòu)，結(jié)點(diǎn)是跳過一部分的，從而加快了查詢的速度。跳表跟紅黑樹又有什么差別呢？既然兩者的算法復(fù)雜度差不多，為什么Redis要使用跳表而不使用紅黑樹呢？跳表相對于紅黑樹，主要有這幾個(gè)優(yōu)點(diǎn)：
1.代碼相對簡單，手寫個(gè)跳表還有可能，手寫個(gè)紅黑樹試試？
2.如果我們要查詢一個(gè)區(qū)間里面的值，用平衡樹可能會(huì)麻煩。這里的麻煩指的是實(shí)現(xiàn)和理解上，平衡二叉樹查詢一段區(qū)間也是可以做到的。
3.刪除一段區(qū)間，這個(gè)如果是平衡二叉樹，就會(huì)相當(dāng)困難，畢竟設(shè)計(jì)到樹的平衡問題，而跳表則沒有這種煩惱。
好了，相信你對跳表已經(jīng)有一些認(rèn)識(shí)了，我們來簡單介紹平衡二叉樹的幾個(gè)基本操作。
查詢
假如我們要查詢11，那么我們從最上層出發(fā)，發(fā)現(xiàn)下一個(gè)是5，再下一個(gè)是13，已經(jīng)大于11，所以進(jìn)入下一層，下一層的一個(gè)是9，查找下一個(gè)，下一個(gè)又是13，再次進(jìn)入下一層。最終找到11。
是不是非常的簡單？我們可以把查找的過程總結(jié)為一條二元表達(dá)式（下一個(gè)是否大于結(jié)果？下一個(gè)：下一層）。理解跳表的查詢過程非常重要，試試看查詢其他數(shù)字，只要你理解了查詢，后面兩種都非常簡單。
插入
插入的時(shí)候，首先要進(jìn)行查詢，然后從最底層開始，插入被插入的元素。然后看看從下而上，是否需要逐層插入?？墒堑降滓灰迦肷弦粚幽?？我們都知道，我們想每層的跳躍都非常高效，越是平衡就越好（第一層1級(jí)跳，第二層2級(jí)跳，第3層4級(jí)跳，第4層8級(jí)跳）。但是用算法實(shí)現(xiàn)起來，確實(shí)非常地復(fù)雜的，并且要嚴(yán)格地按照2地指數(shù)次冪，我們還要對原有地結(jié)構(gòu)進(jìn)行調(diào)整。所以跳表的思路是拋硬幣，聽天由命，產(chǎn)生一個(gè)隨機(jī)數(shù)，50%概率再向上擴(kuò)展，否則就結(jié)束。這樣子，每一個(gè)元素能夠有X層的概率為0.5^(X-1)次方。反過來，第X層有多少個(gè)元素的數(shù)學(xué)期望大家也可以算一下。
刪除
同插入一樣，刪除也是先查找，查找到了之后，再從下往上逐個(gè)刪除。比較簡單，就不再贅敘。
總結(jié)
跳表，用了計(jì)算機(jī)中一場非常用的解決問題的思路，隨機(jī)。隨機(jī)在深度學(xué)習(xí)與人工只能領(lǐng)域運(yùn)用得非常的廣泛。（不僅人會(huì)蒙，計(jì)算機(jī)也是很會(huì)蒙的）今天的介紹我們就講到這里，如果你有興趣，歡迎關(guān)注我，最近準(zhǔn)備了一些AI相關(guān)的，苦于時(shí)間有限，整理后后面會(huì)和大家繼續(xù)分享。
