文章目錄

• 簡介
• SkipList
• ConcurrentSkipListMap
• • SkipList的實現
  • concurrent的實現
• 總結

SkipList和java中ConcurrentSkipListMap的實現

簡介

一開始聽說SkipList我是一臉懵逼的，啥？還有SkipList？這個是什么玩意。

后面經過我的不斷搜索和學習，終于明白了SkipList原來是一種數據結構，而java中的ConcurrentSkipListMap和ConcurrentSkipListSet就是這種結構的實現。

接下來就讓我們一步一步的揭開SkipList和ConcurrentSkipListMap的面紗吧。

SkipList

先看下維基百科中SkipList的定義：

SkipList是一種層級結構。最底層的是排序過的最原始的linked list。

往上是一層一層的層級結構，每個底層節點按照一定的概率出現在上一層list中。這個概率叫做p，通常p取1/2或者1/4。

先設定一個函數f，可以隨機產生0和1這兩個數，并且這兩個數出現的幾率是一樣的，那么這時候的p就是1/2。

對每個節點，我們這樣操作：

我們運行一次f，當f=1時，我們將該節點插入到上層layer的list中去。當f=0時，不插入。

舉個例子，上圖中的list中有10個排序過的節點，第一個節點默認每層都有。對于第二個節點，運行f=0，不插入。對于第三個節點，運行f=1,將第三個節點插入layer 1，以此類推，最后得到的layer 1 list中的節點有：1，3，4，6，9。

然后我們再繼續往上構建layer。 最終得到上圖的SkipList。

通過使用SkipList，我們構建了多個List，包含不同的排序過的節點，從而提升List的查找效率。

我們通過下圖能有一個更清晰的認識：

每次的查找都是從最頂層開始，因為最頂層的節點數最少，如果要查找的節點在list中的兩個節點中間，則向下移一層繼續查找，最終找到最底層要插入的位置，插入節點，然后再次調用概率函數f，決定是否向上復制節點。

其本質上相當于二分法查找，其查找的時間復雜度是O(logn)。

ConcurrentSkipListMap

ConcurrentSkipListMap是一個并發的SkipList，那么它具有兩個特點，SkipList和concurrent。我們分別來講解。

SkipList的實現

上面講解了SkipList的數據結構，接下來看下ConcurrentSkipListMap是怎么實現這個skipList的：

ConcurrentSkipListMap中有三種結構，base nodes,Head nodes和index nodes。

base nodes組成了有序的鏈表結構，是ConcurrentSkipListMap的最底層實現。

static final class Node<K,V> {final K key;volatile Object value;volatile Node<K,V> next;/*** Creates a new regular node.*/Node(K key, Object value, Node<K,V> next) {this.key = key;this.value = value;this.next = next;}}

上面可以看到每個Node都是一個k，v的entry，并且其有一個next指向下一個節點。

index nodes是構建SkipList上層結構的基本節點：

static class Index<K,V> {final Node<K,V> node;final Index<K,V> down;volatile Index<K,V> right;/*** Creates index node with given values.*/Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {this.node = node;this.down = down;this.right = right;}}

從上面的構造我們可以看到，Index節點包含了Node節點，除此之外，Index還有兩個指針，一個指向同一個layer的下一個節點，一個指向下一層layer的節點。

這樣的結構可以方便遍歷的實現。

最后看一下HeadIndex，HeadIndex代表的是Head節點：

static final class HeadIndex<K,V> extends Index<K,V> {final int level;HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {super(node, down, right);this.level = level;}}

HeadIndex和Index很類似，只不過多了一個level字段，表示所在的層級。

在ConcurrentSkipListMap初始化的時候，會初始化HeadIndex：

head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),null, null, 1);

我們可以看到HeadIndex中的Node是key=null，value=BASE_HEADER的虛擬節點。初始的level=1。

concurrent的實現

接下來，我們再看一下并發是怎么實現的：

基本上并發類都是通過UNSAFE.compareAndSwapObject來實現的，ConcurrentSkipListMap也不例外。

假如我們有三個節點，b-n-f。現在需要刪除節點n。

第一步，使用CAS將n的valu的值從non-null設置為null。這個時候，任何外部的操作都會認為這個節點是不存在的。但是那些內部的插入或者刪除操作還是會繼續修改n的next指針。

第二步，使用CAS將n的next指針指向一個新的marker節點，從這個時候開始，n的next指針將不會指向任何其他的節點。

我們看下marker節點的定義：

Node(Node<K,V> next) {this.key = null;this.value = this;this.next = next;}

我們可以看到marker節點實際上是一個key為null，value是自己的節點。

第三步，使用CAS將b的next指針指向f。從這一步起，n節點不會再被其他的程序訪問，這意味著n可以被垃圾回收了。

我們思考一下為什么要插入一個marker節點，這是因為我們在刪除的時候，需要告訴所有的線程，節點n準備被刪除了，因為n本來就指向f節點，這個時候需要一個中間節點來表示這個準備刪除的狀態。

總結

本文從SkipList數據結構開始，講解了ConcurrentSkipListMap的實現。希望大家能夠喜歡。

更多精彩內容且看：

• 區塊鏈從入門到放棄系列教程-涵蓋密碼學,超級賬本,以太坊,Libra,比特幣等持續更新
• Spring Boot 2.X系列教程:七天從無到有掌握Spring Boot-持續更新
• Spring 5.X系列教程:滿足你對Spring5的一切想象-持續更新
• java程序員從小工到專家成神之路（2020版）-持續更新中,附詳細文章教程

歡迎關注我的公眾號:程序那些事，更多精彩等著您！
更多內容請訪問:flydean的博客

總結

以上是生活随笔為你收集整理的SkipList和java中ConcurrentSkipListMap的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。