跳跃表
自我感觉跳跃表就是分层的链表,为了达到二分查找的时间效率,跳跃表提出了层的概念,每一层也是一个链表。
如果能达到第一层的个数是0层的一半,2层的个数是1层的一半,n层的个数是n-1层的一半,并且n层的元素是n-1层的中间数。。即层数最好是lgn(n是元素个数)
为了模拟以上效果,跳跃表采用每个节点随机产生,对于每一层,每两个节点就随机产生多一个层。
对于第一层,每两个节点随机产生多一层的概率是1/2,此时第二层存在的概率是1/2,第二层随机多产生一层的概率是1/2,所以第一层随机多产生两层的概率是1/2*1/2=1/4,以此类推,第一层随机多产生三层的概率是1/8,第一层随机多产生n层的概率是1/2^n...(个人推断,不知是否正确)
所以每次新加入一个节点以1/2^j的概率产生j层,代码如下:
参考随机生成层数
int random_level()
{
K = 1;
while(random(0,1))
{
K++;
}
return K;
}
另一个算法,参考《算法:C语言实现(第1-4部分)》13.5节:
int randX()
{
int i, j, t = rand();
for(i = 1, j = 2; i < lgNmax; i++,j += j)
if(t > RAND_MAX / j) break;
if (i > lgN) lgN = i;
return i;
}
查找:
每次从最高层向右向下查找
比较的时候的三种情况,以targetNode->next[i]->element和theElement为例:
1.小于:令targetNode = targetNode->next[i]; //第i级链表的下一个
2.大于:向下降级,i- - //不改变targetNode
3.等于:向下降级,i- - //不改变targetNode
参考:跳表
插入
插入的时候需要先查找插入的位置,并且保存数组last[],last[i]表示插入的节点第i层的前一个节点,(保存last数组的目的是要修改层列表,单层列表只需要修改一层,多层列表需要修改多层)
删除
类似插入,也需要保存last[]数组,修改与删除节点相关联的层
redis的跳表每一层多了一个span记录跨度(即我到本层的下一个节点所经历的结点数)
还多了一个后退指针,指向前一个结点