跳表C语言实现中插入层级概率控制的Rand函数原理解析

Great question! This Rand() function is a clever, compact way to enforce the skip list's core probability rule—let's unpack it step by step.

First, let's restate the goal we need to hit: a new node should have its highest level as i with probability 1/2^i. That translates to:

• 1/2 chance the node only exists on the bottom level (highest level = 1)
• 1/4 chance it extends up to level 2
• 1/8 chance up to level 3, and so on

Breaking Down the Code #

Let's walk through each part of the function line by line:

static int Rand() { 
    int i, j = 0; 
    uint32_t t = rand(); 
    for (i = 1, j = 2; i < lg_n_max; i ++, j += j) 
        if (t > RANDMAX / j) break; 
    if (i > lg_n) lg_n = i; 
    return i; 
}

1. Random Number Base: t = rand() generates a random integer between 0 and RANDMAX (the maximum value rand() can return, like 32767 for standard C implementations).
2. Loop Initialization: We start with i=1 (the lowest possible level for a new node) and j=2—notice j is always 2^i here (starts at 2^1=2, then doubles each loop iteration).
3. Probability Check Loop:
   • For each level i, we split the full random number range into j equal slices (since RANDMAX/j is the size of each slice).
   • If t falls into the upper (j-1)/j portion of the range (i.e., t > RANDMAX/j), we stop the loop and return i as the node's highest level.
   • If t is in the bottom 1/j slice, we keep going: increment i to try the next higher level, and double j (so we split the range into twice as many slices for the next check).

Why This Gives the Exact Probabilities We Need #

Let's map this logic to our target probabilities:

• Returning i=1: This happens when t > RANDMAX/2 (the upper half of the random range). The probability of this is 1/2 = 1/2^1—exactly what we want for nodes limited to the bottom level.
• Returning i=2: This only occurs if t ≤ RANDMAX/2 (probability 1/2) AND t > RANDMAX/4. The interval (RANDMAX/4, RANDMAX/2] makes up 1/4 of the total range, so the combined probability is 1/4 = 1/2^2.
• Returning i=3: We only get here if t ≤ RANDMAX/4 (probability 1/4), then check if t > RANDMAX/8. The interval (RANDMAX/8, RANDMAX/4] is 1/8 of the total range—so probability 1/8 = 1/2^3.
• And so on: For any level i, the probability of returning i is exactly 1/2^i, which matches the skip list's requirement perfectly.

The Final lg_n Update #

The line if (i > lg_n) lg_n = i just tracks the highest level currently present in the skip list. When we generate a level higher than the current maximum, we update lg_n so future insertions can use this higher level, ensuring the skip list scales naturally as more elements are added.

内容的提问来源于stack exchange，提问作者纪老猴子