演算法 - redis的zslRandomLevel函數的實作原理是什麼？

Question

hi,all

最近在看redis的代碼（huangz注釋過的），是2.6版本的。在看到t_zset.c這個文件的時候，了解到跳躍表的概念，大概原理是懂的，但是不太了解這個生成隨機層數的算法原理。不知道有沒童鞋能介紹下這段代碼其實是怎麼做到模擬冪次定律的？

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned.
 *
 * 返回一个介于 1 和 ZSKIPLIST_MAXLEVEL 之间的随机值，作为节点的层数。
 *
 * 根据幂次定律(power law)，数值越大，函数生成它的几率就越小
 *
 * T = O(N)
 */
int zslRandomLevel(void) {
    int level = 1;
    // TODO 了解这个公式背后的数学原理
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

Answer 1

http://blog.csdn.net/kisimple/article/details/38706729
這個解釋的比較清晰，也可以去參考skiplist論文。