跳表的实现

简介

skiplist本质也是一种查找结构，和搜索树、哈希表一样可以作为key或者key/value模型的查找结构，从命名可以看出它也是一个链表结构，链表的查找效率是O(n),作为在链表基础上优化的一种查找结构，跳表的查找的平均时间复杂度是O(logn)，跳表是在有序链表的基础上发展起来的。优化的思路如下：

1. 假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图b所示。这 样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半。由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了，需要比较的节点数大概只有原来的一半。

2. 以此类推，我们可以在第二层新产生的链表上，继续为每相邻的两个节点升高一层，增加一
   个指针，从而产生第三层链表。如下图c，这样搜索效率就进一步提高了。

3. skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方
   式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似
   二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时
   候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格
   的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也
   包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。

4. skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是
   插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，
   这样就好处理多了。细节过程入下图：

插入一个节点，这个节点随机一个层数的方式受两个参数的影响，p增加一层的概率，maxlenvel最大层数限制，伪代码如下

C++实现如下

int randomlevel(){int level = 1;while (rand() <= RAND_MAX * p && level < maxlevel)  //RAND_MAX是能随机生成的最大值++level;return level;}

Redis的跳表实现中p是取1/4 maxlevel取32。
根据伪代码可以看出，产生越高的节点层数概率越低
节点层数等于1的概率为1-p
层数大于等于2的概率为p,恰好等于2的概率为p(1-p)
层数大于等于3的概率为p^2,恰好等于3的概率为p²(1-p)
层数大于等于4的概率为p³, 恰好等于4的概率为p³(1-p)
…
一个节点的平均层数计算公式为

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

跳表的实现

struct skiplistnode
{int _val;vector<skiplistnode*>_nextV;skiplistnode(int val,int level):_val(val),_nextV(level,nullptr){}
};
class Skiplist
{typedef skiplistnode node;
public:Skiplist(){_head = new node(-1, 1);srand((unsigned int)time(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;}elsereturn true;	}return false;}vector<node*> findprevnode(int num){node* cur = _head;int level = _head->_nextV.size() - 1;vector<node*>prev(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){prev[level] = cur;--level;}}return prev;}void add(int num){vector<node*>prev = findprevnode(num);int n = randomlevel();node* newnode = new node(num, n);if (n > prev.size()){prev.resize(n, _head);_head->_nextV.resize(n);}for (int i = 0; i < n; ++i){newnode->_nextV[i] = prev[i]->_nextV[i];prev[i]->_nextV[i] = newnode;}}bool erase(int num){vector<node*>prev = findprevnode(num);if (prev[0]->_nextV[0] == nullptr || prev[0]->_nextV[0]->_val != num) //说明不存在numreturn false;else{node* del = prev[0]->_nextV[0];for (int i = 0; i < del->_nextV.size(); ++i){prev[i]->_nextV[i] = del->_nextV[i];}delete del;int level = _head->_nextV.size() - 1;while (level>0&&_head->_nextV[level] == nullptr){--level;}_head->_nextV.resize(level + 1); //删除一个节点后可能导致最顶上有些层数指针指向空，把这些没意义的层数减一下来return true;}}int randomlevel(){int level = 1;while (rand() <= RAND_MAX * p && level < maxlevel)++level;return level;}void print(){node* cur = _head;while (cur){printf("%2d\\n", cur->_val);for (auto& e : cur->_nextV){printf("%2s", "↓");}printf("\\n");cur = cur->_nextV[0];}}
private:node* _head;double p = 0.4;int maxlevel = 32;
};