zmm'blog

重点

randLevel算法

/**
 * Redis实现
 * 初始层数为1，每次随机生成一个随机数，取低16位
 * 当取的这个值小于0.25倍的0xFFFF时，level++，否则退出。
 * 返回level和maxLevel的最小值
 *
 * 这里的ZSKIPLIST_P是晋升的概率。对应的期望层高是E=1/(1-p)。
 */
#define ZSKIPLIST_MAXLEVEL 64
#define ZSKIPLIST_P 0.25
private int randLevel() {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}