文章 212
评论 0
浏览 119901
golang实现跳表(SkipList)

golang实现跳表(SkipList)

跳表的理解

如果要维护一组有序的整数序列,支持高效的插入删除和搜索,并且能维护序列的有序性。可以选择的数据结构是有限的,哈希表虽然支持常数时间复杂度的增删查,但是hashmap不能维护有序性。红黑树可以维持有序性,并且增加删除修改的性能也很好,但是红黑树不能支持范围搜索。跳表这种数据结构利用空间换时间,性能和红黑树比肩,还能支持区间搜索,在redisleveldb等开源项目中都用被应用。

跳表的结构如图所示:
skiplist

在最底层包含了所有的数据节点,每一层链表都有一个指向下一层和自己相同的节点,向后的指针指向随机的同一层比自己大的数据。

时间复杂度分析

不难理解,对于一个有n个节点的链表,如果每两个节点会提取出一个节点作为索引节点,那么第一层的节点个数为n/2,再往上一层,节点数变成n/4,以此类推,第k层的索引个数为n/(2^k),假设层数有x层,并且第x层的节点个数为2,也就是n/(2^x) = 2,所以x = (logn - 1),而第0层是链表本身,所以整个跳表的高度就是logn,如果每一层都需要遍历m个节点,那么在跳表中查询某个数的时间复杂度就是O(m * log(n))

简单的单向跳表实现: skiplist


标题:golang实现跳表(SkipList)
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/11/12/1573563696154.html

Nothing just happens, it's all part of a plan.

取消