? ? 有關(guān)SkipList的定義拯辙，請參考跳躍表（可能需要科學(xué)上網(wǎng)）郭变。我們知道，有序鏈表涯保，無論是單向還是雙向诉濒，增刪改查時間復(fù)雜度都是O(n)。跳躍表的存在就是為了解決這個問題夕春，解決思路為空間換時間未荒，不過空間復(fù)雜度沒有提升，仍然為O(n)（理論上使用的空間變?yōu)樵瓉淼?-2倍及志，數(shù)學(xué)期望為n+log(n)倍）片排，但是增刪改查的時間復(fù)雜度降低為O(log(n))，其性能可以媲美二叉樹家族（AVL樹速侈，紅黑樹）率寡，但在并發(fā)情況下，二叉樹在增刪操作后進(jìn)行重新平衡需要加鎖的節(jié)點(diǎn)要比跳躍表多倚搬，所以整體性能表現(xiàn)上冶共，跳躍表要優(yōu)于二叉樹。
? ? 本文將使用go語言實(shí)現(xiàn)跳躍表的增每界、刪捅僵、改、查操作眨层，考慮到業(yè)務(wù)上的使用場景庙楚，該實(shí)現(xiàn)將支持協(xié)程安全。
? ? 一個典型的單向四層跳躍表如圖1：
????由圖1可以看到谐岁，跳躍表具有以下特性：
? ? 1醋奠、層數(shù)（LEVEL）越高榛臼，鏈上的節(jié)點(diǎn)越少，大致呈P=0.5的幾何分布窜司。
? ? 2沛善、每一層的節(jié)點(diǎn)均有序且不重復(fù)。
? ? 跳躍表層數(shù)（LEVEL）的設(shè)置塞祈，應(yīng)當(dāng)與數(shù)據(jù)量息息相關(guān)金刁，合理的取值應(yīng)該為log(n)，對數(shù)底數(shù)為2议薪，當(dāng)然尤蛮，考慮到數(shù)據(jù)量增長，大于log(n)也是可以的斯议。比如产捞，數(shù)據(jù)量為30億條，則合理的層數(shù)取值應(yīng)該為31<log(3000000000)<32哼御，故LEVEL應(yīng)取32坯临。
? ? 首先，定義節(jié)點(diǎn)結(jié)構(gòu)體：
type SkipListNode struct {
????key int
????data interface{}
????next []*SkipListNode
}
? ? 其中恋昼，key為排序使用的字段看靠，對應(yīng)圖1中的數(shù)字1~9；data為實(shí)際存儲的數(shù)據(jù)液肌，可以為任何類型挟炬，圖1中并沒有體現(xiàn)；next為節(jié)點(diǎn)指針切片嗦哆，比如圖1中的"HEAD"節(jié)點(diǎn)的next應(yīng)該為[&5, &3, &1, &1]谤祖，“3”節(jié)點(diǎn)的next應(yīng)該為[&5, &5, &4]，其中&n表示key為n節(jié)點(diǎn)的地址吝秕。
? ? 定義跳躍表結(jié)構(gòu)體：
type SkipList struct {
????head????*SkipListNode
????tail????????*SkipListNode
????length????int
? ? level? ? ? int
????mut? ? ? ?*sync.RWMutex
????rand ???? *rand.Rand
}
? ? head：頭節(jié)點(diǎn)
? ? tail：尾節(jié)點(diǎn)
? ? length： 數(shù)據(jù)總量
? ? level：層數(shù)
? ? mut：互斥鎖泊脐，用于保證協(xié)程安全
? ? rand：隨機(jī)數(shù)生成器，用于生成隨機(jī)層數(shù)烁峭，隨機(jī)生成的層數(shù)要滿足P=0.5的幾何分布容客，大致可以理解為：擲硬幣連續(xù)出現(xiàn)正面的次數(shù)，就是我們要的層數(shù)约郁。所以隨機(jī)生成層數(shù)的方法可以定義如下：
func (list *SkipList) randomLevel() int {
????level := 1
????for ; level < list.level && list.rand.Uint32() & 0x1 == 1; level ++{}
????return level
}
? ? 補(bǔ)上一個工廠構(gòu)造方法：
func NewSkipList(level????int) *SkipList {
????list := &SkipList{}
????if level <=0 {
????????level =32
????}
????list.level = level
????list.head = &SkipListNode{next:make([]*SkipListNode, level, level)}
????list.tail = &SkipListNode{}
????list.mut = &sync.RWMutex{}
????list.rand = rand.New(rand.NewSource(time.Now().UnixNano()))
????for index :=range list.head.next {
????????list.head.next[index] = list.tail
????}
????return list
}
? ? 接下來實(shí)現(xiàn)數(shù)據(jù)插入方法缩挑。假設(shè)我們目前的跳躍表已經(jīng)有如下數(shù)據(jù)：
? ? 我們需要插入一個3，并且調(diào)用randomLevel得到的層數(shù)為3鬓梅，那么插入3需要如下幾部：
? ? 1供置、沿著LEVEL3的鏈查找第一個比3大的節(jié)點(diǎn)或者TAIL節(jié)點(diǎn)，記錄下該節(jié)點(diǎn)的前一個節(jié)點(diǎn)——HEAD和層數(shù)——3绽快。
? ? 2芥丧、沿著LEVEL2的鏈查找第一個比3大的節(jié)點(diǎn)或者TAIL節(jié)點(diǎn)紧阔，記錄下該節(jié)點(diǎn)的前一個節(jié)點(diǎn)——&1和層數(shù)——2。
? ? 3续担、沿著LEVEL1的鏈查找第一個比3大的節(jié)點(diǎn)或者TAIL節(jié)點(diǎn)擅耽，記錄下該節(jié)點(diǎn)的前一個節(jié)點(diǎn)——&2和層數(shù)——1。
? ? 4物遇、生成一個新的節(jié)點(diǎn)newNode乖仇，key賦值為3，將newNode插入HEAD询兴、&1乃沙、&2之后，即HEAD.next[3]=&3诗舰，&1.next[2]=&3警儒，&2.next[1]=&3。
? ? 5始衅、給newNode的next賦值冷蚂，即步驟4中HEAD.next[3]缭保、&1.next[2]汛闸、2.next[1]原本的值。
? ? 注意：為了易于理解艺骂，上述步驟中所有索引均從1開始诸老，而代碼中則從0開始，所以代碼中均有索引=層數(shù)-1的關(guān)系钳恕。
? ? 那么别伏，插入的代碼可以寫成這樣：
func (list *SkipList) Add(key int, data interface{}) {
????list.mut.Lock()
????defer list.mut.Unlock()
????//1.確定插入深度
????level := list.randomLevel()
????//2.查找插入部位
????update :=make([]*SkipListNode, level, level)
????node := list.head
????for index := level -1; index >=0; index -- {
????????for {
????????????node1 := node.next[index]
????????????if node1 == list.tail || node1.key > key {
????????????????update[index] = node//找到一個插入部位
? ? ? ? ? ? ????break
? ? ? ? ???? }else if node1.key == key{
? ? ? ? ? ? ? ? node1.data = data
????????????????return
? ? ? ? ???? }else {
????????????????node = node1
????????????}
????????}
????}
????//3.執(zhí)行插入
????newNode := &SkipListNode{key, data, make([]*SkipListNode, level, level)}
????for index, node :=range update {
????????node.next[index],newNode.next[index] = newNode,node.next[index]
????}
????list.length ++
}
? ? 實(shí)際上，刪除忧额、查找的方法與插入變化不大厘肮。
? ? 刪除方法：
func (list *SkipList) Remove(key int) bool {
????list.mut.Lock()
????defer list.mut.Unlock()
//1.查找刪除節(jié)點(diǎn)
????node := list.head
????remove :=make([]*SkipListNode, list.level, list.level)
????var target *SkipListNode
????for index :=len(node.next) -1; index >=0; index -- {
????????for {
????????????node1 := node.next[index]
????????????if node1 == list.tail ||? node1.key >? key{
????????????????break
? ? ? ? ???? }else if node1.key == key {
????????????????remove[index] = node//找到啦
? ? ? ? ? ? ????target = node1
????????????????break
? ? ? ? ???? }else {
????????????????node = node1
????????????}
????????}
????}
//2.執(zhí)行刪除
????if target != nil {
????????for index, node1 :=range remove {
????????????if node1 != nil {
????????????????node1.next[index] = target.next[index]
????????????}
????????}
????????list.length --
????????return true
? ???? }
????return false
}
? ? 查找方法：
func (list *SkipList)Find(key int) interface{} {
????list.mut.RLock()
????defer list.mut.RUnlock()
????node := list.head
????for index :=len(node.next) -1; index >=0; index -- {
????????for {
????????????node1 := node.next[index]
????????????if node1 == list.tail ||? node1.key >? key? ?{
????????????????break
? ? ? ? ???? }else if node1.key == key {
????????????????return node1.data
????????????}else {
????????????????node = node1
????????????}
????????}
????}
return nil
}
? ? 最后，是獲取數(shù)據(jù)總量方法：
func (list *SkipList) Length() int {
????list.mut.RLock()
????defer list.mut.RUnlock()
????return list.length
}
? ? 就這樣睦番，一個單向的跳躍表就實(shí)現(xiàn)了类茂，是不是很簡單呢？
