skiplist介绍

skiplist是William Pugh提出的一种基于概率统计链表结构,优化了普通链表的查询性能,是一种典型的空间换时间的算法。skiplist处理的情况是有序链表,里面的节点是排序好的,skiplist能够高效的查找元素,因为他能够跳过大部分的节点,直接定位到要找的节点附近。

操作 | 平均复杂度 | 最差情况
—|—|—-
空间 | O(n) | O(n*logn)
查询 | O(logn) | O(n)
插入 | O(logn) | O(n)
删除 | O(logn) | O(n)

skiplist其实是一个多层的链表结构,最底层其实是一个普通的链表,上面的层就像高速路,上面的链表层能够指向下一层链表,好比是高速通道的出口。

查询

当我们通过skiplist查询一个节点时,我们从最顶层的头结点开始,在当前节点大于等于要找的节点时或者达到当前层的尾部节点,我们就往下一个层搜索。 如此往复,知道访问都最底层节点的尾部节点。当节点匹配到要找的节点的时候,查询过程结束。

假设有如上图的skiplist,我们要查找其中的值为35的节点。如果是直接对普通链表(最底层)操作,我们需要7次操作,但是如果是基于skiplist,我们只需要3次操作,8->29->35(没有考虑链表向下的操作)。

插入

插入一个元素,首先需要定位到在哪里插入,这个过程和查找类似,不同点是结束条件。插入元素的时候首先要定位到他的前序节点,也就是该节点小于要插入的元素,且该节点的后序节点大于等于要插入的元素。
另外一个要注意的是,插入操作有一个随机选层的操作。这个操作的目的是决定新插入的节点是否要用来构建“高速公路”,如果用来构建,最高是第几层。这个过程是一个随机抛硬币的过程,每次抛硬币跑到正面的概率是50%,那么连续抛硬币,直到抛到反面,那么抛到正面的次数就是层数。

参考资料

Skip Lists: A Probabilistic Alternative to Balanced Trees, William Pugh

从LRU原理与实现到Redis的LRU策略 Redis基本数据结构

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×