ConcurrentSkipListMap
底層實作是”跳躍表“ ，Redis當中Zset同樣采用的是該資料結構
跳躍表的結構圖：
![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-9xzCLDbJ-1640785263458)(JUC并發編程.assets/image-20211229180148601.png)]](https://img.uj5u.com/2021/12/30/293135300951013.png)
特點：
- 其根本思想是 二分查找 的思想，
- 跳表的前提條件是 針對 有序的單鏈表 ，實作高效地查找，插入，洗掉，
- Redis中的 有序集合 sorted set 就是用跳表實作的，
1、跳表的原理
種基于單鏈表的高級資料結構， 跳表 將單鏈表先進行排序，然后針對 有序鏈表 為了實作高效的查找，可以使用跳表這種資料結構，
對于單鏈表，即使是 存盤的有序資料（即 有序鏈表），想在其中查找某個資料，也只能從頭到尾遍歷，查找效率低，時間復雜度是O(n)，如下圖所示：
![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-i2DomITg-1640785263460)(JUC并發編程.assets/image-20211229212652406.png)]](https://img.uj5u.com/2021/12/30/293135300951011.png)
怎么才能提高查找效率呢？
為了提高查找效率，使用二分查找的思想，對有序鏈表建立一級“索引”， 每兩個節點提取一個節點到索引層， 索引層中的每個節點 都包
含兩個指標，一個指向下一個節點，一個down指標，指向下一級節點
![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-W3ngZkja-1640785263461)(JUC并發編程.assets/image-20211229212725503.png)]](https://img.uj5u.com/2021/12/30/293135300951012.png)
首先在一級索引層遍歷，當遍歷到14這個節點的時候，發現其下一個節點是23，則要查找的18就在14和23之間， 然后，通過14節點的
down 指標，下降到原始鏈表這一層，繼續在原始鏈表中遍歷， 此時，只需要在原始鏈表中，遍歷兩個節點，14和18,就找到18這個節點
了， 查找18這個節點，在原始鏈表需要遍歷10個節點，現在只需要遍歷7個節點（一級索引層遍歷5個節點，原始鏈表遍歷2個節點），
如果再增加一級索引，那么效率會不會更高呢？
建立二級索引
![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-9h5nXN3c-1640785263462)(JUC并發編程.assets/image-20211229212926138.png)]](https://img.uj5u.com/2021/12/30/293135300951014.png)
現在如果要查找18節點，只需要遍歷6個節點（二級索引層遍歷3個節點，一級索引層1個節點，原始鏈表2個節點），
通過建立索引的方式，對于資料量越大的有序鏈表，通過建立多級索引，查找效率提升會非常明顯，
這種鏈表加多級索引的結構 就是 跳表，
2、跳表中查詢一個節點
通過Key去查詢，從Head節點開始進入，由最高層索引開始查詢，主鍵向下層索引縮小范圍，知道找到我們BaseHeader這一層后會將Node節點進行逐個equals比較
3、跳表中插入一個節點
跳表作為一個動態資料結構，不僅支持查找操作，還支持資料的插入和洗掉操作，并且 插入和洗掉的操作的時間復雜度都是O(logn).
我們先去查詢我們這個節點在我們的調表中是否存在，也就是通過key執行上述的查詢的程序，如果發現節點存在，那么就會覆寫我們的已存在的節點，如果不存在則新建一個Node節點進行插入操作，但是我們插入之后就會出現一個新的問題，就是我們的節點變了那么對應的索引也應該做相應的修改，那么為新插入的Node節點創建的索引步驟如下 ：
1、首先是生成一個亂數
int rnd = ThreadLocalRandom.nextSecondarySeed();
2、然后通過讓我們的亂數與0x80000001進行一個&操作，去判斷是否滿足建立索引的條件
if ((rnd & 0x80000001) == 0) // 0x80000001這個16進制轉換為2進制則是 10000000 00000000 00000000 00000001
// rnd這個亂數，最高位和最低為同時為0的時候條件成立，概率是1/4
3、當滿足建立索引的條件后，我們還需要通過對這個亂數進行計算得出我們建立的索引層數level
//首先rnd滿足索引建立條件初始為1，之后檢查從第二位到第31位間1的個數，相加即為索引層數
rnd = 00000000 00000000 00000000 00011110 ===> 得出level為4 + 1 = 5 ；
rnd = 00000000 00000000 00010100 01011110 ===> 得出level為8 + 1 = 9 ；
4、我們講理論上應該建立的索引層數再次進行判斷，得到我們的實索引際高度！
//拿到步驟3得出的理論索引層數，與我們當前調表中的索引層數比較，例：上圖跳表的層數是3，我們為新插入的節點建立索引的理論高度是9，那么我們就會得出我們實際的索引高度是3 + 1 = 4 ; 也就是超過實際索引高度，我們為新插入節點建立的索引高度就是我們實際的高度 + 1
5、創建層次索引，完結！
4、調表洗掉節點
洗掉原鏈表中的節點，如果節點存在于索引中，也要洗掉索引中的節點， 因為單鏈表中的洗掉需要用到 要洗掉節點 的 前驅動節點， 可以像插入操作一樣，通過索引逐層向下遍歷到原始鏈表中，要洗掉的節點，并記錄其 前驅節點，從而實作洗掉操作，
5、面試題
為什么Redis中的有序集合用跳表而非紅黑樹來實作呢？
- 對于插入，洗掉，查找 以及 輸出有序序列 這幾個操作，紅黑樹也可以完成，時間復雜度 與 用跳表實作是相同的， 但是，對于按照區間查找資料這個操作（比如 [20,300]）,紅黑樹的效率沒有跳表高，跳表可以做到 O(logn)的時間復雜度定位區間的起點，然后在原始鏈表中順序向后遍歷輸出，直到遇到值大于區間終點的節點為止，
- 跳表更加靈活，它可以通過改變節點的抽取間隔，靈活地平衡空間復雜度和時間復雜度
- 相比紅黑樹，跳表更容易實作，代碼更簡單
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/397347.html
標籤：其他
上一篇：Python判斷回文鏈表