hi,all最近在看redis的代码(huangz注释过的),是2.6版本的。在看到t_zset.c这个文件的时候,了解到跳跃表的概念,大概原理是懂的,但是不太了解这个生成随机层数的算法原理。不知道有没童鞋能介绍下这段代码其实是怎么做到模拟幂次定律的?/*Returnsarandomlevelforthenewskiplistnodewearegoingtocreate.*Thereturnvalueofthisfunctionisbetween1andZSKIPLIST_MAXLEVEL*(bothinclusive),withapowerlaw-alikedistributionwherehigher*levelsarelesslikelytobereturned.**返回一个介于1和ZSKIPLIST_MAXLEVEL之间的随机值,作为节点的层数。**根据幂次定律(powerlaw),数值越大,函数生成它的几率就越小**T=O(N)*/intzslRandomLevel(void){intlevel=1;//TODO了解这个公式背后的数学原理while((random()&0xFFFF)<(ZSKIPLIST_P*0xFFFF))level+=1;return(level}
相关分类