使用模数将散列转换为整数会导致整数均匀（均匀）分布吗？

Question

假设我有这段代码可以将哈希字符串转换为 int：

const crypto = require('crypto');

function uuidToInteger(uuid) {
    // - Create a hash object using SHA-1 algorithm
    const hash = crypto.createHash('sha1');

    // - Update the hash object with the UUID
    hash.update(uuid, 'utf-8');

    // - Get the digest (hash value) as a hexadecimal string
    const hashValueHex = hash.digest('hex');

    // - Convert the hexadecimal string to an integer
    const hashValueInt = parseInt(hashValueHex, 16);

    const mappedValue = 1 + (hashValueInt % 20); 

    return mappedValue;
}

使用示例

const uuid = '550e8400-e29b-41d4-a716-446655440000';
const result = uuidToInteger(uuid);
console.log(result);`

（理论上）整数 1-20 的均匀/均匀分布结果会是这样吗？作为 n （随着转换的哈希值变大）？如果是为什么，如果不是，为什么？

最终我尝试使用哈希通过负载均衡器路由请求，LB 可以使用 int 路由到 20 个子服务（在内存映射中，与需要 redis 等的一些更复杂的映射相反）

Answer 1

假设您有一个随机数生成器函数 RAND()，它返回区间 [0,RAND_MAX] 内的整数，但您想使用它生成区间 [0,MAX] 内的随机整数。那么一种简单的方法是使用模运算符

return RAND() % (MAX+1);

假设调用 RAND() 时 [0, RAND_MAX] 中每个结果出现的概率相等，那么如果 MAX+1 除 RAND_MAX+1，则 [0,MAX] 中每个结果出现的概率相等，并且否则不等于。

以 MAX = 5，RAND_MAX = 16 为例。那么 00 到 04 出现了 3 次，而 05 只出现了 2 次。因此，与其余的相比，05 出现的概率只有 2/3。

RAND()           = 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
RAND() % (MAX+1) = 00 01 02 03 04 05 00 01 02 03 04 05 00 01 02 03 04  

更一般地说，

Let S = (RAND_MAX+1) % (MAX+1)
Let Q = floor((RAND_MAX+1) / (MAX+1))

则 (RAND_MAX+1) = Q(MAX+1) + S。

Probability of [0, S-1] occurring = (Q+1)/(RAND_MAX+1)
Probability of [S, MAX] occurring = Q/(RAND_MAX+1)

检查全部加起来...

((MAX-S+1)Q + S(Q+1))/(RAND_MAX+1) = (Q(MAX+1) + S)/(RAND_MAX+1) = 1

这表明如果 S > 0，所得概率并不全部相等。然而，如果 Q 很大，那么概率差异可能会很小，可以接受。

假设 Q > 0，使用模运算符从 RAND() 中以相同概率生成 [0, MAX] 范围内的随机结果的一种方法是拒绝从 RAND() 返回的最高 S 值。例如，假设 S 和 Q 已知，

if (S == 0) return RAND() % (MAX+1);
ret = RAND_MAX;
while (ret >= Q(MAX+1)) ret = RAND();
return ret % (MAX+1);

由于 RAND() 的结果只有不到一半被拒绝，因此在迭代的每个循环中找到可以使用的结果的概率超过一半，因此不存在无限循环的现实可能性。在实践中，如果有的话，它不需要循环太多就能找到可用的结果。

就OP的问题而言，Q = Floor(2^160 / 20) 是巨大的，因此上述概率差异仅具有密码学意义。