1、跳躍表(skiplist)是一種有序數(shù)據(jù)結(jié)構(gòu),它通過每個節(jié)點(diǎn)中維持多個指向其他節(jié)點(diǎn)的指針,從而達(dá)到快速訪問節(jié)點(diǎn)的目的
2、跳躍表支持平均O(logN) 最壞o(N)復(fù)雜度的節(jié)點(diǎn)查找,還可以通過順序操作來批量處理節(jié)點(diǎn),大部分情況下效率媲美平衡樹,實(shí)現(xiàn)比平衡樹簡單,所以不少程序員用跳躍表來代替平衡樹
3、使用場景,有序集合包含元素數(shù)量比較多,或者成員member是比較長的字符串時。
4、跳躍表實(shí)現(xiàn),包含zskiplistnode zskiplist
4.1、zskiplist

header:指向跳躍表的表頭節(jié)點(diǎn) tail:指向跳躍表的表尾節(jié)點(diǎn),level:跳躍表內(nèi),層數(shù)最大的那個節(jié)點(diǎn)的層數(shù)(表頭節(jié)點(diǎn)層數(shù)不計算在內(nèi)) length:跳躍表長度,,,?包含的節(jié)點(diǎn)數(shù)量,表頭不計在內(nèi)
4.2、zskiplistnode

level:層 每個跳躍表節(jié)點(diǎn)層高都是1到32之間的隨機(jī)數(shù)
每個層有兩個屬性,前進(jìn)指針和跨度,前進(jìn)指針用戶訪問位于表尾方向的其他節(jié)點(diǎn),跨度則記錄前進(jìn)指針?biāo)赶蚬?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的距離 后退(backward)指針:bw字樣標(biāo)記節(jié)點(diǎn)后退指針,后退指針從表尾向頭遍歷時使用
分值,各個節(jié)點(diǎn)按照各自保存的分值從小到大排列
成員對象obj
得分相同,則按照字典順序排序
5、僅通過多個跳躍表節(jié)點(diǎn)就能組成一個跳躍表,但是通過zskiplist結(jié)構(gòu)來持有這些節(jié)點(diǎn),程序可以更方便的對整個跳躍表進(jìn)行處理
5.1、查找表頭表尾復(fù)雜度為o(1) 計算長度length復(fù)雜度為o(1)