C++：跳表

跳表跳表介绍skiplist本质上是一种查找结构由William Pugh发明用于解决算法中的查找问题跟平衡搜索树和哈希表的价值是一样的可以作为key或者key/value的查找模型。skiplist顾名思义首先它是一个list。实际上它是在有序链表的基础上发展起来的。如果是一个有序的链表查找数据的时间复杂度是O(N)。skiplist思路假如我们每相邻两个节点升高一层增加一个指针让指针指向下下个节点如下图b所示。这样所有新增加的指针连成了一个新的链表。第二层比第一层少了一半的节点由于新增加的指针我们不再需要与链表中每个节点逐个进行比较了需要比较的节点数大概只有原来的一半。例如查找1212比6大到6这个节点比9大到9这个节点比17小到9节点的下一层指针查找到12。以此类推我们可以在第二层新产生的链表上继续为每相邻的两个节点升高一层增加一个指针从而产生第三层链表。如下图c这样搜索效率就进一步提高了。skiplist正是受这种多层链表的想法的启发而设计出来的。实际上按照上面生成链表的方式上面每一层链表的节点个数是下面一层的节点个数的一半这样查找过程就非常类似二分查找使得查找的时间复杂度可以降低到O(log N)。但是这个结构在插入删除数据的时候有很大的问题插入或者删除一个节点之后就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系就必须把新插入的节点后面的所有节点也包括新插入的节点重新进行调整这会让时间复杂度重新蜕化成O(N)。skiplist的设计为了避免这种问题做了一个大胆的处理不再严格要求对应比例关系而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数这样就好处理多了。跳表的效率首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限制其次会设置一个多增加一层的概率 p。那么计算这个随机层数的伪代码如下图初始层数lvl为1random()返回一个[ 01 )的随机数当随机数小于p并且当前层数小于最大层数时层数1最后返回层数。在Redis的skiplist实现中p0.25maxlevel32。根据前面randomLevel()的伪码我们很容易看出产生越高的节点层数概率越低。要让层数恰好是 1意味着第一次循环的random() p就不成立直接退出。所以节点层数恰好等于1的概率为1-p。要让层数恰好是 2需要第一次random() p成立概率p层数升到 2第二次random() p不成立概率1 - p循环终止。所以节点层数恰好等于2的概率为p(1-p)。同理节点层数恰好等于3的概率为p2(1-p)节点层数恰好等于4的概率为p3(1-p)。因此一个节点的平均层数也即包含的平均指针数目计算如下当p0.5时每个节点所包含的平均指针数目为2当p0.25时每个节点所包含的平均指针数目为1.33。根据复杂的推导跳表的平均时间复杂度为O(log N)。跳表的实现#define_CRT_SECURE_NO_WARNINGS#includeiostream#includevector#includetime.h#includerandom#includechronousingnamespacestd;structSkiplistNode{int_val;vectorSkiplistNode*_nextV;SkiplistNode(intval,intlevel):_val(val),_nextV(level,nullptr){}};classSkiplist{typedefSkiplistNode Node;public:Skiplist(){srand(time(0));_headnewNode(-1,1);}boolsearch(inttarget){intlevel_head-_nextV.size()-1;Node*cur_head;while(level0){//当前层中目标值比cur的下一个节点值大cur走到当前层的下一个节点if(cur-_nextV[level]cur-_nextV[level]-_valtarget)curcur-_nextV[level];//当前层中cur的下一个节点为空或cur的下一个节点值比目标值大往下走一层elseif(cur-_nextV[level]nullptr||cur-_nextV[level]-_valtarget)level--;elsereturntrue;}returnfalse;}intRandomLevel()//C生成随机数{intlevel1;while(rand()RAND_MAX*_plevel_maxlevel)level;returnlevel;}//int RandomLevel()//C生成随机数//{// static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());// static std::uniform_real_distributiondouble distribution(0.0, 1.0);// int level 1;// while (distribution(generator) _p level _maxlevel)// level;// return level;//}vectorNode*FindPrev(intnum){intlevel_head-_nextV.size()-1;Node*cur_head;vectorNode*prevV(level1,_head);//prevV存储num节点每一层的前驱节点while(level0){if(cur-_nextV[level]cur-_nextV[level]-_valnum)curcur-_nextV[level];elseif(cur-_nextV[level]nullptr||cur-_nextV[level]-_valnum){prevV[level]cur;level--;}}returnprevV;}voidadd(intnum){vectorNode*prevVFindPrev(num);intnRandomLevel();//随机生成待插入节点层数Node*newnodenewNode(num,n);if(n_head-_nextV.size())//待插入节点层数大于头节点的层数修改{_head-_nextV.resize(n,nullptr);prevV.resize(n,_head);}for(inti0;in;i)//连接{newnode-_nextV[i]prevV[i]-_nextV[i];prevV[i]-_nextV[i]newnode;}}boolerase(intnum){vectorNode*prevVFindPrev(num);if(prevV[0]-_nextV[0]nullptr||prevV[0]-_nextV[0]-_val!num)//没有找到numreturnfalse;else{Node*delprevV[0]-_nextV[0];//获得待删除的num节点for(inti0;idel-_nextV.size();i){prevV[i]-_nextV[i]del-_nextV[i];}deletedel;inti_head-_nextV.size()-1;//如果num节点是最高节点删除num后_head也要降低层数while(i0){if(_head-_nextV[i]nullptr)i--;elsebreak;}_head-_nextV.resize(i1);returntrue;}}voidPrint(){Node*cur_head;while(cur){printf(%2d\n,cur-_val);for(autoe:cur-_nextV){printf(%2s,↓);}coutendl;curcur-_nextV[0];}}private:Node*_head;int_maxlevel32;double_p0.5;};intmain(){Skiplist sl;intarr[]{5,2,3,8,9,6};for(autoe:arr){sl.add(e);}sl.Print();return0;}对于search(int target)寻找19。对于add函数插入节点17。因为待插入节点有多层每一层都需要对应的前驱节点。以头节点的层数开一个prevV用来存储每一层的前驱节点。随机生成2层调用resize(n_head)n为待插入节点的层数如果prevV的元素个数n就会用 _head来补足到n如果prevV的元素个数n则会减少prevV的元素。接下来根据prevV保存的前驱节点先让待插入节点的 _next指向其下一节点再连接前驱节点与待插入节点。对于erase函数先通过FindPrev(int num)找到要删除的num节点并保存其前驱节点每一层连接前驱节点和下一个节点最后delete完成删除。如果num节点为层数最高的节点_head节点层数也是最高的此时要降低 _head节点层数使 _head节点层数保持与当前链表层数最高的节点一致。分析C生成随机数staticstd::default_random_enginegenerator(std::chrono::system_clock::now().time_since_epoch().count());staticgenerator是一个静态变量。它在函数首次调用时初始化之后所有调用都复用同一个实例避免了重复播种和初始化的开销保证了随机数序列的连续性。std::default_random_engine这是 C 标准库提供的一个默认随机数引擎它是一个伪随机数生成器PRNG。其具体实现由编译器决定通常是一个高质量的线性同余或其他算法。std::chrono::system_clock::now().time_since_epoch().count()使用系统当前时间从 epoch 开始的微秒 / 纳秒数作为种子。确保每次程序运行时生成的随机数序列都是不同的避免了可预测性。staticstd::uniform_real_distributiondoubledistribution(0.0,1.0);staticdistribution是静态的确保只初始化一次提高效率。std::uniform_real_distributiondouble这是一个均匀实数分布器它将随机数引擎生成的原始整数转换为在指定区间内均匀分布的双精度浮点数。区间左闭右开即生成的随机数x满足0.0 ≤ x 1.0。跳表与平衡搜索树和哈希表的对比skiplist与平衡搜索树(AVL树和红黑树)对比都可以做到遍历数据有序时间复杂度也差不多。skiplist的优势是skiplist实现简单容易控制。平衡树增删查改遍历都更复杂。skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链平衡因子/颜色等消耗。skiplist中p1/2时每个节点所包含的平均指针数目为2skiplist中p1/4时每个节点所包含的平均指针数目为1.33。skiplist相比哈希表而言就没有那么大的优势了。哈希表平均时间复杂度是O(1)比skiplist快。哈希表空间消耗略多一点。skiplist优势如下遍历数据有序。skiplist空间消耗略小哈希表存在链接指针和表空间消耗。哈希表扩容有性能损耗。哈希表在极端场景下哈希冲突高效率下降厉害需要红黑树补足接力。