今天在看redis的基本數(shù)據(jù)悠栓，結(jié)構(gòu)時候色解，看到有一個跳躍表的數(shù)據(jù)結(jié)構(gòu)，這之前我一直沒聽說過這種結(jié)構(gòu)钥勋，于是先把redis的跳躍表結(jié)構(gòu)的實現(xiàn)看了炬转，然后他的名稱是skiplist辆苔，這讓我想起在java8的并發(fā)包下有帶skiplist字樣的2個實現(xiàn)類，我才明白扼劈，原來java也有這種數(shù)據(jù)結(jié)構(gòu)驻啤，于是先百度了一些關(guān)于跳躍表的算法的原理，個人覺得下面這篇文章寫的淺顯易懂荐吵，對于入門可謂非常合適骑冗。先貼鏈接：http://blog.csdn.net/a1259109679/article/details/46442895。然后順便看看java里面的這種數(shù)據(jù)結(jié)構(gòu)是怎么實現(xiàn)的先煎。
jdk8下有2個這種實現(xiàn)類贼涩，一個是本文介紹的ConcurrentSkipListMap，還有一個是ConcurrentSkipListSet薯蝎，二者的區(qū)別在寫本文之時還未閱讀后者的源碼遥倦。
這里需要先明白幾個組成元素：node節(jié)點(diǎn)是真正用來存放我們存入的數(shù)據(jù)的，其中的key和value不必多說占锯，同時還持有一個指向下一個node節(jié)點(diǎn)的指針袒哥。
index，這個對象有3個屬性消略，第一個是一個node節(jié)點(diǎn)堡称，第二個是down是指向下一個層級的index，right就是指向本層級的下一個index的指針疑俭。
頭節(jié)點(diǎn)粮呢，第一個屬性是代表所在的層級，跳躍表的快速定位依賴與此钞艇，然后還有一個指向下一個頭結(jié)點(diǎn)的
下圖是一個擁有12個node的分成2層的示意圖啄寡，從圖中藍(lán)色的線表示一次尋找k7的過程，當(dāng)然本次數(shù)據(jù)少哩照，所以優(yōu)勢并未那么明顯挺物，但是如果數(shù)據(jù)量大的時候，能大大減少尋找次數(shù)飘弧。當(dāng)然這里如果把一排node放在最先會更直觀识藤。
從上圖可以看出，其實整個結(jié)構(gòu)分為2塊次伶，一塊是由我們的node的節(jié)點(diǎn)組成的基礎(chǔ)數(shù)據(jù)痴昧，而另外一塊是由一個多層level2組成的數(shù)據(jù)結(jié)構(gòu)，且尋找過程總是從level最高的開始冠王，然后先找到滿足條件的最后一個index,然后通過index指向下一層對應(yīng)的index,然后繼續(xù)向右向下尋找赶撰，直到找到level1且滿足了右邊的node的key比我們需要查找的key大或者為null，然后進(jìn)入到我們最先的node節(jié)點(diǎn)，然后去遍歷鏈表豪娜。如下圖所示
對整個結(jié)構(gòu)以及尋找過程清楚以后餐胀，我們來看看源碼中怎么樣形成這個結(jié)構(gòu)的。
首先來了解第一個API瘤载，put方法否灾。put方法首先驗證value為不為Null,也就是這不允許value為Null，這與map是不同的鸣奔。真正做加入操作是交給我們的doPut方法操作的墨技。如果度過spring的源碼的同學(xué)知道，spring中很多的對外的API也都是做一個必要性驗證溃蔫，然后真正的操作都交給do**方法操作健提，而這一的方法一般要么是private的要么是protect的。
下面我們看doput方法伟叛。第三個參數(shù)是一個布爾值私痹，從名字可以看到應(yīng)該是一個僅僅在缺席時候加入，這里是不是可以猜測如果已經(jīng)存在當(dāng)前key统刮，有2種操作紊遵，一種是修改，一種是加入侥蒙。進(jìn)來看這里首先驗證了key不能為null暗膜，結(jié)合上一步的驗證可以知道在我們這個跳躍表里是不允許鍵值為null.然后通過一個findPredecessor，傳入當(dāng)前新加入的key鞭衩，和比較的方式來進(jìn)行尋址学搜。真正的尋找應(yīng)該放在那里是在這里實現(xiàn)的。
findpredecessor從名字可以理解為尋找前輩论衍，尋找前任瑞佩。這個尋找過程是從最高level的headIndex開始的，然后先向右開始找坯台，直到右為Null或者炬丸，右邊Index的Node的key大于了當(dāng)前需要加入的key為止，然后再向下尋找蜒蕾，同樣也是直到下為null為止才是出口稠炬。通過一系列向右向下尋找，最后會落到我們的需要加入節(jié)點(diǎn)的前輩或者前任Node上咪啡，然后返回首启。
然后我們來看看找到這個前輩后我們做什么。首先取得這個前輩的next撤摸，如果它的下一個Next節(jié)點(diǎn)不為空的時候毅桃，我們繼續(xù)依著這個next去繼續(xù)向下尋找栽惶，直到下一個節(jié)點(diǎn)為空為止。這里看最后一個if判斷疾嗅，如果c為0（代表找到了一個key一模一樣的node），然后判斷onlyIfAbsent冕象，一般情況下默認(rèn)傳入的是false代承，如果是false，則執(zhí)行第二個CAS替換渐扮，如果為true則不會執(zhí)行论悴。這驗證了我們前面的猜測。這里有多2個判斷墓律，主要是在并發(fā)下的一些判斷吧膀估。能夠完全做到線程安全。
下面看看如果下個節(jié)點(diǎn)以后的做法耻讽，直接把我們新傳入的key和value包裝成node察纯，然后通過cas來完成next指向，然后就加到了我們的鏈中去了针肥。到目前為止饼记，其實整個加入過程最終操作的是我們的第一塊，也就是整個node鏈條慰枕。
下面我們看加入完成后還做了些什么具则？如果讓你想，你認(rèn)為接下來會干什么呢具帮？到目前為止博肋，我們整個數(shù)據(jù)結(jié)構(gòu)是怎么建立的？對蜂厅，應(yīng)該到了拆分層次的過程了匪凡。在原來的跳躍表原理中拆分解釋了隨機(jī)的，也就是擲骰子的方式葛峻，這在常理看來是不是有點(diǎn)不靠譜啊锹雏，在java中呢？通過源碼可以知道术奖，java中也是隨機(jī)的礁遵。不過這個隨機(jī)是由線程生成的唯一一個數(shù)字與一個16禁止數(shù)字做與操作后的結(jié)果來決定的〔杉牵看下圖：如果通過判斷為true后佣耐，首先將level設(shè)置默認(rèn)為1，然后對rnd進(jìn)行一個右位移操作后在與1進(jìn)行與操作后來確定需要分為幾層唧龄。具體為什么用這個算法兼砖，我看的時候也不大明白，等將來搞明白后在補(bǔ)上。然后通過多次對level++后讽挟，就確定了我們需要分成幾層了懒叛。確定最終需要的層次后首先判斷，需要分成的level與當(dāng)前的最大level比較耽梅，如果比后者小的話薛窥，然后對小于level的每層初始化一個index，每層的node都指向新加入的node,down指向下一層的同樣的自己眼姐，右側(cè)全部初始化為null诅迷。其實也就是如果不需要擴(kuò)大層的時候，為每層初始化一個這個index众旗，然后準(zhǔn)備加入到原來的index鏈條中去
如果需要擴(kuò)容的話罢杉，首先確定的是每次是擴(kuò)容一層，然后初始化一個對應(yīng)的indxs的數(shù)組贡歧，然后為每層都創(chuàng)建包含新加入z的node滩租，并且指向下一層的自己的index。然后通過for循環(huán)來進(jìn)行擴(kuò)層操作艘款。擴(kuò)容是從目前最高的那一層開始的持际，先加一層，包裝一個node指向當(dāng)前head的node指向的node哗咆，第二個參數(shù)是down指向當(dāng)前的head蜘欲，index指向剛剛創(chuàng)建的對應(yīng)層次的index，以及最后一個確定層次的編號晌柬。這樣就完成了一層中的headindex的創(chuàng)建姥份。然后通過cas吧當(dāng)前的head與新加入層的head進(jìn)行替換。這里用語言描述的肯定有些頭暈年碘，我們下面用個圖來講述一下
但是我們發(fā)現(xiàn)完成了新加入澈歉，但是對于新加入的Node，只有最頂層建立了指針指向屿衅，其他層并未進(jìn)行加入操作埃难。接下來我們就要完成為每層加入index的操作。由名字可以看到就是插入層次的概念涤久。
此時的h已經(jīng)指向了我們最新的最高的層的headIndex涡尘，然后首先r指向第一個右側(cè)index，如果這個index不為null,則先取出這個index的node响迂，然后與當(dāng)前新加入的key比較考抄，拿到返回值額c，然后判斷node的value不能為null蔗彤，如果為null則先解除二者之間的關(guān)系川梅，解除成功后從新建立right的指向疯兼，最后如果新加入的key比當(dāng)前index的node的key大的話然后順延繼續(xù)找下一個index繼續(xù)比較，下圖1是橫向的找贫途，找到后進(jìn)入第二個圖吧彪。
然后判斷如果當(dāng)前是最頂層，則把最后的r指向新加入的Index丢早。然后對標(biāo)志的插入層進(jìn)行減減操作来氧，然后同時對j(也是當(dāng)前插入層)，進(jìn)行減減操作香拉，且j必須必代表最高層的level小，然后把t指向了下一層(也就是為新加入的key包裝的index中狂，之前為每一層都建立一個且建立了down指向關(guān)系)凫碌。然后同樣把headIndex和right同步下移。用文字描述同樣比較蒼白胃榕，用一張圖來說明
黑色線代表當(dāng)前操作盛险，紅色線代表完成建立關(guān)系后的操作，都開始指向下一層勋又。
通過上面苦掘，就完成了新加入對象的尋址，分層楔壤，新關(guān)系建立的流程鹤啡。
下面看remove方法，也很簡單蹲嚣，是通過doremove完成的递瑰。
從renmove方法可以看出，即可以通過key移除隙畜，也可以通過同時滿足key和value完成抖部。
進(jìn)來首先也是需要尋找到前key，這里一定是返回的是index所指向的node议惰，也就是上一步一定是僅僅找到index慎颗，然后這里通過下面的代碼繼續(xù)向下尋找，找到后首先用CAS把value替換為null,然后判斷是不是這層唯一的一個index言询，如果是的話就把這層給干掉俯萎。然后就完成了刪除，從這里看出倍试，它僅僅是把node的value設(shè)置為null或者刪除掉本層讯屈。
size()方法，全局并沒有維護(hù)一個總數(shù)县习，所以每次都會去遍歷涮母，這里的findFirst也就是直接找到第一個node谆趾，然后利用node的next去統(tǒng)計。最后最多能返回Integer.MAX_VALUE.這里在線程并發(fā)下是安全的
get方法叛本，也是通過doGet方法完成的沪蓬。這里不具體列代碼了，也是很簡單来候，通過findpredecessor方法定位到最近的index跷叉，然后繼續(xù)順延node去尋找定位返回。
replace方法是可以指定key和value來指定替換营搅，也就是必須滿足value是oldvalue云挟。首先通過findNode找到對應(yīng)的node。
讀完這里也就完成了整個代碼解讀转质。但是這里肯定會有疑問园欣，也就是移除操作，其實真正的移除操作都是在其他操作里借用判斷value是不是為null來進(jìn)行操作的休蟹。這里最重要的是helpdelete方法沸枯。其實很簡單，就是一個鏈條解除的關(guān)系赂弓。
