- 前言
- 跳表是什么
- 随即层数的理解
- 设计一个跳表
- 复杂度考量
前言
skiplist本质上也是一种查找结构,用于解决算法中的查找问题,跟平衡搜索树和哈希表的价值是一样的,可以作为key或者key/value的查找模型。
跳表是什么其实光从概念来说,跳表可能并不难理解,跳表相当于是单链表的基础上,向上增加索引的方式,让我们查找数据的时候能够类似用一个二分查找的方式查找,但实际上建立上面的索引过后,新插入和删除节点会破坏上下两层1:2的关系,也就是说,倘若你在第一层的索引:第二层的索引是1:2,并且后面的n:n+1也都保持这样的关系,那么查找的时候是能够保持logN的效率,但是插入和删除就会破坏这里的结构。
怎么解决上述问题呢?
skiplist的设计为了避免这种问题,做了一个大胆的处理,不再严格要求对应比例关系,而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数。即不需要调节其他节点的层数。
换句话讲,就是一个节点最多有多少层,上层的索引最高多少,在一开始就已经确定好了。当我们需要插入删除操作的时候,只需要找到插入位置前后节点,改变链接关系即可。
这是一种大胆的处理,是因为每次插入的时候跳表里的数据存储的位置,层数都可能发生变化,并且他也有可能出现前面部分都是低矮层数,后面都是高层次的节点,从而降低了效率。
随即层数的理解其中节点随机层数,其实随即层数也是有讲究的,随即过后每一层的节点数其实是相对固定的,随即层数的函数会保证上一层的节点数:下一层的节点数是1:2。
当p设置的小,层数就会低一点,像redis通常设置为0.25。
跳表通常需要有一个最大层数maxLevel,以及一个概率p,即新增加一层的概率。通常数据量够大,就会呈现出一定的比率。
当p是0.25,那么只有产生一层的概率就是1-p(0.75),产生第二层的概率就是(1-p) * p。三层(1-p)pp…
因此,一个节点的平均层数(也即包含的平均指针数目),计算如下
1206. 设计跳表
#pragma once #include复杂度考量using namespace std; #include #include #include #include class Skiplist { public: struct Node { vector _skiplist; int _level; int _val; Node(int level, int val) :_skiplist(level, nullptr) , _level(level) , _val(val) {} }; Skiplist() { srand(0); //头节点默认只有0层,即最底层 _root = new Node(1, -1); } bool search(int target) { //查找一个元素的时候 //指针指向的比key值小的话,往右,其他情况往下 Node* cur = _root; int level = cur->_level - 1; //从最上层开始往下遍历 while (level >= 0) { if (cur->_skiplist[level] && cur->_skiplist[level]->_val < target) { //往右边走 cur = cur->_skiplist[level]; } else if (cur->_skiplist[level] && cur->_skiplist[level]->_val == target) { //此时查找的值就在右边 return true; } else { //其他情况都是往下走,最终会从下面越界 level--; } } return false; } //由于前后链接的时是需要整个Node占一个数组的位置 vector Find(int target, int level) { if (_root->_level < level) { //超过level的置成nullptr _root->_skiplist.resize(level, nullptr); _root->_level = level; } //level层,并且每一个插入元素的前一个位置的指针 vector preNode(level, nullptr); level--;//从索引处开始 Node* cur = _root;//实际上cur是工具人 while (level >= 0) { if (cur->_skiplist[level] && cur->_skiplist[level]->_val < target) { //往右边走 cur = cur->_skiplist[level]; } else { //往下走之前实际上右边就是我们要插入的点 preNode[level] = cur; level--; } } return preNode; } void add(int num) { //先会创建num的节点 //Random函数创建这个随机的层数 int level = Random(); //if(num == 0) //{ // level = 1; //} //else //{ // level = 5; //} Node* newNode = new Node(level, num); vector preNode = Find(num, level); //此时将节点的前节点和后节点分别连接起来. //注意:先链接newNode的_skiplist节点 for (int i = 0; i < level; ++i) { newNode->_skiplist[i] = preNode[i]->_skiplist[i]; preNode[i]->_skiplist[i] = newNode; } } int Random() { int level = 1;//最低从第一层开始 if (rand() < _p * RAND_MAX && level < _maxLevel) { level++; } return level; } bool erase(int num) { int level = _root->_level; vector preNode = Find(num, level); //若找不到,就是删除失败 Node* del = preNode[0]->_skiplist[0]; if (del == nullptr || del->_val != num) return false; int delLevel = del->_level; delLevel--;//索引处开始删 while (delLevel >= 0) { preNode[delLevel]->_skiplist[delLevel] = del->_skiplist[delLevel]; delLevel--; } delete del; //erase节点的时候还可以优化,删掉头顶若干层 int index = _root->_level - 1; while (index >= 0) { if (!_root->_skiplist[index]) { index--; } else { break; } } if (index != _root->_level - 1) { //说明上面几层可以不要 _root->_skiplist.resize(index+1); _root->_level = index + 1; } return true; } private: int _maxLevel = 32; double _p = 0.7; Node* _root = nullptr; }; void test() { Skiplist skiplist; skiplist.add(0); skiplist.add(5); int x; cin >> x; skiplist.erase(x); }
skiplist跟平衡搜索树和哈希表的对比
- skiplist相比平衡搜索树(AVL树和红黑树)对比,都可以做到遍历数据有序,时间复杂度也差
不多。
- skiplist的优势是:
- a、skiplist实现简单,容易控制。平衡树增删查改遍历都更复杂。
- b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链,平衡因子/颜色等消耗。
- skiplist中p=1/2时,每个节点所包含的平均指针数目为2;skiplist中p=1/4时,每个节点所包
含的平均指针数目为1.33;
- skiplist相比哈希表而言,就没有那么大的优势了。
- 哈希表平均时间复杂度是O(1),比skiplist快。
- 哈希表空间消耗略多一点。
- skiplist优势如下:
- a、遍历数据有序
- b、skiplist空间消耗略小一点,哈希表存在链接指针和表空间消耗。
- c、哈希表扩容有性能损耗。
- d、哈希表再极端场景下哈希冲突高,效率下降厉害,需要红黑树补足接力。