【高阶数据结构】跳表

红太狼 2023-10-13 22:36 110阅读 0赞

#### 文章目录 ####

*  一、什么是跳表
 *  二、跳表的效率如何保证？
 *  三、skiplist的实现
 *  四、skiplist跟平衡搜索树和哈希表的对比

--------------------

## 一、什么是跳表 ##

skiplist本质上也是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是  
一样的，可以作为key或者key/value的查找模型。那么相比而言它的优势是什么的呢？这么等我  
们学习完它的细节实现，我们再来对比。

**`skiplist`** 是由 *`William Pugh`* 发明的，最早出现于他在1990年发表的论文 **《Skip Lists: AProbabilistic Alternative to Balanced Trees》**

**`skiplist`，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。如果是一  
个有序的链表，查找数据的时间复杂度是`O(N)`。**

William Pugh开始的优化思路：

> 1.  假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图b所示。这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半。由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了，需要比较的节点数大概只有原来的一半。
> 2.  以此类推，我们可以在第二层新产生的链表上，继续为每相邻的两个节点升高一层，增加一个指针，从而产生第三层链表。如下图c，这样搜索效率就进一步提高了。
> 3.  skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。  
>     ![在这里插入图片描述][38a7fb1547134f999b0d3879b0e6f515.png]  
>     查找的过程：假如要查找的值是key，那么需要看下一个节点的值是否比key大，如果比key大， 就向下走。如果比key小，就向右走。如果没有找到，就会走到第-1层。  
>     skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，这样就好处理多了。细节过程入下图：  
>     ![在这里插入图片描述][74df4240f9214540bb73735550f61c9d.png]

--------------------

## 二、跳表的效率如何保证？ ##

> 上面我们说到，skiplist插入一个节点时随机出一个层数，听起来怎么这么随意，如何保证搜索时的效率呢？  
> 这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限制，其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图：  
> ![在这里插入图片描述][1b07394f99e84f84996f8e963e9d3852.png]
> 
> 在 Redis 的 skiplist 实现中，这两个参数的取值为：`p = 1/4` 和 `maxLevel = 32`。注：谷歌的开源项目 LevelDB（小型的 KV 型数据库）也采用了 skiplist，有兴趣的大佬可以了解一下！

根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。定量的分析  
如下：

*  节点层数至少为1。而大于1的节点层数，满足一个概率分布。
 *  节点层数恰好等于1的概率为1-p。
 *  节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
 *  节点层数大于等于3的概率为p2，而节点层数恰好等于3的概率为p2\*(1-p)。
 *  节点层数大于等于4的概率为p3，而节点层数恰好等于4的概率为p3\*(1-p)
 *  …

因此，一个节点的平均层数（也包含的平均指针数目）计算如下：

![在这里插入图片描述][5d9a9b8cdaed4b31a826c47b9013582d.png]  
现在很容易计算出：

*  当p=1/2时，每个节点所包含的平均指针数目为2；
 *  当p=1/4时，每个节点所包含的平均指针数目为1.33。

![在这里插入图片描述][d86627133ece49fc9d0409ac4ee8c8fa.png]

跳表的平均时间复杂度为O(logN)，这个推导的过程比较复杂，这里我们稍微提一下。

--------------------

## 三、skiplist的实现 ##

![在这里插入图片描述][10f37c874bc949759d0f7f11574353ce.png]

**结点的设计**

struct SkiplistNode
    {
        
    	int _val;
    	vector<SkiplistNode*> _nextV;
    
    	SkiplistNode(int val, int level)
    		:_val(val)
    		, _nextV(level, nullptr)
    	{
        }
    };

因为每个结点的层数是随机的，所以申请一个新节点需要知道其层数和存储的值，通过vector的下标可以表示层数。

**整体设计**

class Skiplist {
        
    	typedef SkiplistNode Node;
    public:
    	Skiplist() {
        
    		srand(time(0));
    
    		// 头节点，层数是1
    		_head = new SkiplistNode(-1, 1);
    	}
    
    private:
    	Node* _head; // 哨兵位头节点
    	size_t _maxLevel = 32; // 最高的层数
    	double _p = 0.25; // 增加一层的概率
    };

哨兵位头节点的层数是该跳表中最高的，初始时让哨兵位的层数为1.增加一层的概率是0.25，理论而言，概率越大，效率越高。

**节点的随机层数**

计算这个随机层数的伪代码如下图：

![在这里插入图片描述][d580d4a0e1384b29900aa7af72412538.png]

**C语言产生随机数**

int RandomLevel()
    {
        
    	size_t level = 1;
    	// rand() ->[0, RAND_MAX]之间
    	// rand() 《= RAND_MAX*_p 可以保证增加一层的概率是_p
    	// level <= maxLevel 保证随机层数不超过最高层数maxLevel
    	while (rand() <= RAND_MAX*_p && level < _maxLevel)
    	{
        
    		++level;
    	}
    	return level;
    }

**C++产生随机数**

int RandomLevel()
    {
        
    	static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
    	static std::uniform_real_distribution<double> distribution(0.0, 1.0);
    
    	size_t level = 1;
    	while (distribution(generator) <= _p && level < _maxLevel)
    	{
        
    		++level;
    	}
    
    	return level;
    }

这里我们需要注意的是：因为C语言产生的随机数范围是0到32767之间的数，范围比较小。不过可以通过加减一些数来扩大随机数的范围。

**skiplist的查找**

查找的过程:查找是要和下一个节点的值相比，并不是和当前节点的值相比一开始cur在哨兵位头节点的最高层 head，开始进行比较。假如要查找的值为target，如果下一个节点为空或者下一个节点的值比target大，那么cur需要向下一层走;如果下一个节点的值比target下，那么cur向右走。重复上述过程，直至找到或者没找到(没找到的话，cur会去到第-1层，注:层数是从第0层开始的)

bool search(int target) {
        
    	Node* cur = _head;
    	int level = _head->_nextV.size() - 1;
    	while (level >= 0)
    	{
        
    		// 目标值比下一个节点值要大，向右走
    		// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
    		if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
    		{
        
    			// 向右走
    			cur = cur->_nextV[level];
    		}
    		else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
    		{
        
    			// 向下走
    			--level;
    		}
    		else
    		{
        
    			return true;
    		}
    	}
    	
    	return false;
    }

**skiplist的插入**

无论是插入值还是删除值，都需要找到该值的前面的节点，这样才能修改指针的指向关系。我们可以将这个保存前一个指针的操作封装成一个函数，提供给插入和删除接口使用。

vector<Node*> FindPrevNode(int num)
    {
        
    	Node* cur = _head;
    	int level = _head->_nextV.size() - 1;
    
    	// 插入位置每一层前一个节点指针
    	vector<Node*> prevV(level + 1, _head);
    
    	while (level >= 0)
    	{
        
    		// 目标值比下一个节点值要大，向右走
    		// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
    		if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
    		{
        
    			// 向右走
    			cur = cur->_nextV[level];
    		}
    		else if (cur->_nextV[level] == nullptr
    			|| cur->_nextV[level]->_val >= num)
    		{
        
    			// 更新level层前一个
    			prevV[level] = cur;
    
    			// 向下走
    			--level;
    		}
    	}
    
    	return prevV;
    }

![在这里插入图片描述][eea76e88898544bb9337352a27a66322.png]

void add(int num) {
        
    	vector<Node*> prevV = FindPrevNode(num);
    	
    	int n = RandomLevel();
    	Node* newnode = new Node(num, n);
    	
    	// 如果n超过当前最大的层数，那就升高一下_head的层数
    	if (n > _head->_nextV.size())
    	{
        
    		_head->_nextV.resize(n, nullptr);
    		prevV.resize(n, _head);
    	}
    	
    	// 链接前后节点
    	for (size_t i = 0; i < n; ++i)
    	{
        
    		newnode->_nextV[i] = prevV[i]->_nextV[i];
    		prevV[i]->_nextV[i] = newnode;
    	}
    }

**删除节点**  
![在这里插入图片描述][d13b6ac5a0f742b8a89e427e65f58c67.png]

bool erase(int num) {
        
    	vector<Node*> prevV = FindPrevNode(num);
    
    	// 第一层下一个不是val，val不在表中
    	if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
    	{
        
    		return false;
    	}
    	else
    	{
        
    		Node* del = prevV[0]->_nextV[0];
    		// del节点每一层的前后指针链接起来
    		for (size_t i = 0; i < del->_nextV.size(); i++)
    		{
        
    			prevV[i]->_nextV[i] = del->_nextV[i];
    		}
    		delete del;
    
    		// 如果删除最高层节点，把头节点的层数也降一下
    		int i = _head->_nextV.size() - 1;
    		while (i >= 0)
    		{
        
    			if (_head->_nextV[i] == nullptr)
    				--i;
    			else
    				break;
    		}
    		_head->_nextV.resize(i + 1);
    
    		return true;
    }

注意：如果删除的节点的层数是最高的，那么可以将哨兵位头结点的层数降一降。如何判断删除的节点层数是不是最高的呢？从哨兵位头结点的最高层其，如果该层的指针指向空，那么就说明删除的节点层数最高。当前层指针指向空，那么就需要看下一层指针是否指向空。以此类推，直至指针不在指向空，那么就可以求出删除最高节点后剩余节点的最高层数了。

![在这里插入图片描述][43e05096aa4f4507a0d369deaa002024.png]

**打印跳表**

void Print()
    {
        
    	Node* cur = _head;
    	while (cur)
    	{
        
    		printf("%2d\n", cur->_val);
    		// 打印每个每个cur节点
    		for (auto e : cur->_nextV)
    		{
        
    			printf("%2s", "↓");
    		}	
    		printf("\n");
    
    		cur = cur->_nextV[0];
    	}
    }

打印跳表函数可以让我们更好的观察跳表的样子。

**完整代码**

#include <iostream>
    #include <vector>
    #include <time.h>
    #include <random>
    #include <chrono>
    using namespace std;
    
    struct SkiplistNode
    {
        
    	int _val;
    	vector<SkiplistNode*> _nextV;
    
    	SkiplistNode(int val, int level)
    		:_val(val)
    		, _nextV(level, nullptr)
    	{
        }
    };
    
    class Skiplist {
        
    	typedef SkiplistNode Node;
    public:
    	Skiplist() {
        
    		srand(time(0));
    
    		// 头节点，层数是1
    		_head = new SkiplistNode(-1, 1);
    	}
    
    	bool search(int target) {
        
    		Node* cur = _head;
    		int level = _head->_nextV.size() - 1;
    		while (level >= 0)
    		{
        
    			// 目标值比下一个节点值要大，向右走
    			// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
    			if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
    			{
        
    				// 向右走
    				cur = cur->_nextV[level];
    			}
    			else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
    			{
        
    				// 向下走
    				--level;
    			}
    			else
    			{
        
    				return true;
    			}
    		}
    
    		return false;
    	}
    
    	vector<Node*> FindPrevNode(int num)
    	{
        
    		Node* cur = _head;
    		int level = _head->_nextV.size() - 1;
    
    		// 插入位置每一层前一个节点指针
    		vector<Node*> prevV(level + 1, _head);
    
    		while (level >= 0)
    		{
        
    			// 目标值比下一个节点值要大，向右走
    			// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走
    			if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
    			{
        
    				// 向右走
    				cur = cur->_nextV[level];
    			}
    			else if (cur->_nextV[level] == nullptr
    				|| cur->_nextV[level]->_val >= num)
    			{
        
    				// 更新level层前一个
    				prevV[level] = cur;
    
    				// 向下走
    				--level;
    			}
    		}
    
    		return prevV;
    	}
    
    	void add(int num) {
        
    		vector<Node*> prevV = FindPrevNode(num);
    
    		int n = RandomLevel();
    		Node* newnode = new Node(num, n);
    
    		// 如果n超过当前最大的层数，那就升高一下_head的层数
    		if (n > _head->_nextV.size())
    		{
        
    			_head->_nextV.resize(n, nullptr);
    			prevV.resize(n, _head);
    		}
    
    		// 链接前后节点
    		for (size_t i = 0; i < n; ++i)
    		{
        
    			newnode->_nextV[i] = prevV[i]->_nextV[i];
    			prevV[i]->_nextV[i] = newnode;
    		}
    	}
    
    	bool erase(int num) {
        
    		vector<Node*> prevV = FindPrevNode(num);
    
    		// 第一层下一个不是val，val不在表中
    		if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
    		{
        
    			return false;
    		}
    		else
    		{
        
    			Node* del = prevV[0]->_nextV[0];
    			// del节点每一层的前后指针链接起来
    			for (size_t i = 0; i < del->_nextV.size(); i++)
    			{
        
    				prevV[i]->_nextV[i] = del->_nextV[i];
    			}
    			delete del;
    
    			// 如果删除最高层节点，把头节点的层数也降一下
    			int i = _head->_nextV.size() - 1;
    			while (i >= 0)
    			{
        
    				if (_head->_nextV[i] == nullptr)
    					--i;
    				else
    					break;
    			}
    			_head->_nextV.resize(i + 1);
    
    			return true;
    		}
    
    		
    	}
    
    	//int RandomLevel()
    	//{
        
    	//	size_t level = 1;
    	//	// rand() ->[0, RAND_MAX]之间
    	//	while (rand() <= RAND_MAX*_p && level < _maxLevel)
    	//	{
        
    	//		++level;
    	//	}
    
    	//	return level;
    	//}
    
    	int RandomLevel()
    	{
        
    		static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
    		static std::uniform_real_distribution<double> distribution(0.0, 1.0);
    
    		size_t level = 1;
    		while (distribution(generator) <= _p && level < _maxLevel)
    		{
        
    			++level;
    		}
    
    		return level;
    	}
    
    	void Print()
    	{
        
    		/*int level = _head->_nextV.size();
    		for (int i = level - 1; i >= 0; --i)
    		{
    			Node* cur = _head;
    			while (cur)
    			{
    				printf("%d->", cur->_val);
    				cur = cur->_nextV[i];
    			}
    			printf("\n");
    		}*/
    
    		Node* cur = _head;
    		while (cur)
    		{
        
    			printf("%2d\n", cur->_val);
    			// 打印每个每个cur节点
    			for (auto e : cur->_nextV)
    			{
        
    				printf("%2s", "↓");
    			}	
    			printf("\n");
    
    			cur = cur->_nextV[0];
    		}
    	}
    	
    private:
    	Node* _head;
    	size_t _maxLevel = 32;
    	double _p = 0.5;
    };

## 四、skiplist跟平衡搜索树和哈希表的对比 ##

>  *  skiplist 相比平衡搜索树(AVL 树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差不多。skiplist 的优势是：a、skiplist 实现简单，容易控制。平衡树增删查改遍历都更复杂。b、skiplist 的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子或者颜色等消耗。skiplist 中 p = 1 / 2 时，每个节点所包含的平均指针数目为 2；skiplist 中 p = 1 / 4 时，每个节点所包含的平均指针数目为 1.33；
>  *  skiplist 相比哈希表而言，就没有那么大的优势了。相比而言，a、哈希表平均时间复杂度是 O(1)，比 skiplist快。b、哈希表空间消耗略多一点。skiplist 优势如下：a、遍历数据有序。b、skiplist 空间消耗略小一点，哈希表存在链接指针和表空间消耗。c、哈希表扩容有性能损耗。d、哈希表在极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。

![在这里插入图片描述][5b9eaec301624928a7ec43ae0172bb87.png]

--------------------

[38a7fb1547134f999b0d3879b0e6f515.png]: https://img-blog.csdnimg.cn/38a7fb1547134f999b0d3879b0e6f515.png
[74df4240f9214540bb73735550f61c9d.png]: https://img-blog.csdnimg.cn/74df4240f9214540bb73735550f61c9d.png
[1b07394f99e84f84996f8e963e9d3852.png]: https://img-blog.csdnimg.cn/1b07394f99e84f84996f8e963e9d3852.png
[5d9a9b8cdaed4b31a826c47b9013582d.png]: https://img-blog.csdnimg.cn/5d9a9b8cdaed4b31a826c47b9013582d.png
[d86627133ece49fc9d0409ac4ee8c8fa.png]: https://img-blog.csdnimg.cn/d86627133ece49fc9d0409ac4ee8c8fa.png
[10f37c874bc949759d0f7f11574353ce.png]: https://img-blog.csdnimg.cn/10f37c874bc949759d0f7f11574353ce.png
[d580d4a0e1384b29900aa7af72412538.png]: https://img-blog.csdnimg.cn/d580d4a0e1384b29900aa7af72412538.png
[eea76e88898544bb9337352a27a66322.png]: https://img-blog.csdnimg.cn/eea76e88898544bb9337352a27a66322.png
[d13b6ac5a0f742b8a89e427e65f58c67.png]: https://img-blog.csdnimg.cn/d13b6ac5a0f742b8a89e427e65f58c67.png
[43e05096aa4f4507a0d369deaa002024.png]: https://img-blog.csdnimg.cn/43e05096aa4f4507a0d369deaa002024.png
[5b9eaec301624928a7ec43ae0172bb87.png]: https://img-blog.csdnimg.cn/5b9eaec301624928a7ec43ae0172bb87.png