skiplist原理深入浅出

redis的hash实现没有使用红黑数， 而是采用了skiplist, 将学习中的理解整理出来备忘，如果能帮助到其他人就更好了。
这个主题最好的文档还是William Pugh 博士的论文，直接baidu "skip list pdf"就能搜索到，当然也可以从我分享的链接中下载
skipList的基本原理就是每个节点不仅有指向下一个节点的指针， 还维护了k个额外的指针。第k个指针指向(ahead翻译为后继，希望大家能接受)后继第k个节点，比如当前为第5个节点，那么第3个指针就指向第8个节点（也就是当前节点的第3个后继节点）

skip List的示例：

1、什么是level k节点?
含有key 个ahead（后继）指针的节点
2、每个节点要维护多少个额外后继指针？
采用抛硬币的方式，抛一次硬币指针的个数加1， 重复抛硬币直到某次结果为反面。伪代码见论文中的randomLevel() 函数
3、header指针要维护多少个指针呢?
当前链表的level最大为多少，那么header就维护多少个指针

4、查找如何遍历? ?
先沿最大的ahead 指针向后继查找，如果ahead[k] <searchKey， 将ahead[k]作为当前节点继续查找，否则检查ahead[k-1]，直到k=1或者当前节点的key==查找的key
比如为了查找key=25, 那么遍历的路径为6->25

5、新增时额外的向前指针如何维护?
调用随机数产生器产生level ，根据key, 查找到待插入的位置，同时update[]记录链表中其他节点需要指向当前节点指针，修改指针时，当前节点的ahead[i]=update[i]，update[i]指向当前节点
比如上图中? ?为了插入17，先遍历链表找到待插入的位置为12之后， 那么update[2]=节点9的ahead[2], update[1]=节点12的ahead[1], 将节点17的ahead[2]=update[2], ahead[1]=update[1];? ?upate[2]=节点17, upate[1]=节点17

6、删除节点时额外指针维护?
先根据key，查找到对应节点的位置，同时update[]数组记录链表的其他节点指向当前节点的情况， 当前节点删除后需要将update[i]更新为当前节点的ahead[i]
针对上图? ?为了删除key=17的节点，先遍历链表找到key=17节点位置， 并记录update[2]=节点key=9的ahead[2], update[1]=节点key=12的ahead[1]； 修改指针时，节点9的ahead[2]=节点17的ahead[2], 节点12的ahead[1]=节点17的ahead[1];

Posted in: 面试加油站