SkipList跳表介绍

2019-04-22 本文已影响0人夏天的风风风

【文章仅供非商业用途或交流学习使用】

最近研究Redis的相关内容，发现SkipList跳表多次用到，在这里记录一下。

一、跳表简介

SkipList（后面简称SL）是一种支持快速查找的随机化数据结构，是一种可以进行二分查找的有序链表。跳表在原有的有序链表上增加了多级索引，通过索引可以实现快速查找，不仅提高了搜索性能，同时也可以提高插入和删除操作的性能。

二、数据结构

SL的主要设计思想是将链表与二分查找相结合，它维护了一个多层级的链表结构，这是一个用空间换时间的思路。可以把SL看做是一个含有多个行的链表结合，并具有如下性质：

1 SL由很多层组成；

2 每一层都是一个有序的链表；

3 最底层包含的连接包含所有元素；

4 如果一个额元素出现在Level i 层的链表中，则它在level i 之下所有层的链表中都会出现；

5 每个节点包含两个指针，一个指向同一个链表中的下一个元素，一个指向下面一层的元素。

跳表结构示例

三、搜索方式

对一个目标元素的搜索会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点：

1 如果当前元素正好等于目标，那么就直接返回它；

2 如果当前元素小于目标元素，那么就跳到下一层继续搜索；

3 如果当前元素大于目标或到达链表尾部，则先移动到前一个节点的位置，然后跳到下一层。

四、随机产生的层

SL具体产生多少层，是完全随机的，业界最恰当的比喻是丢硬币，正面则将节点复制到上层，反面则停止。

参考文献：