php - SHA1等哈希函数的随机性

Question

我正在尝试根据用户 ID 生成均匀分布的随机数。也就是说，我希望每个用户都有一个随机数，该随机数在用户请求随机数的任何时候都保持不变(但用户不需要存储该数字)。对于给定的大量用户 ID $arr，我当前计算分布的算法(在 PHP 中)是:

$range = 100;
$results = array_fill(0, $range, 0);

foreach ($arr as $userID) {
    $hash = sha1($userID,TRUE);
    $data = unpack('L*', $hash);
    $seed = 0;
    foreach ($data as $integer) {
        $seed ^= $integer;
    }
    srand($seed);
    ++$results[rand(0, $range-1)];
}

人们希望这会产生近似均匀的分布。但事实并非如此!我已经检查以确保 $arr 中的每个值都是唯一的，但是列表中的一个条目总是比其他所有条目获得更多的事件。有没有更好的方法来生成一个字符串的哈希值，该哈希值将给出一个近似均匀的分布？显然 SHA 不能胜任这项工作。我也试过 MD5 和一个简单的 crc32，结果都一样!？

我疯了吗？事实上，唯一的解释是我没有验证 $arr 中的每个条目都是唯一的吗？

Answer 1

sha1 哈希值分布非常均匀。执行此操作后:

<?php

$n = '';
$salt = 'this is the salt';

for ($i=0; $i<100000; $i++) {
    $n .= implode('', unpack('L*', sha1($i . $salt)));
}   

$count = count_chars($n, 1);
$sum = array_sum($count);

foreach ($count as $k => $v) {
    echo chr($k)." => ".($v/$sum)."\n";
} 

?>

你得到这个结果。每个数字的概率:

0 => 0.083696057956298
1 => 0.12138983759522
2 => 0.094558704004335
3 => 0.07301783188663
4 => 0.092124978934097
5 => 0.088623772577848
6 => 0.11390989553446
7 => 0.092570936094051
8 => 0.12348330833868
9 => 0.11662467707838

您可以将 sha1 用作基于用户 ID 的简单随机数生成器。

在十六进制中，分布接近完美:

//  $n .= sha1($i . $salt, false);

0 => 0.06245515
1 => 0.06245665
2 => 0.06258855
3 => 0.0624244
4 => 0.06247255
5 => 0.0625422
6 => 0.0625246
7 => 0.0624716
8 => 0.06257355
9 => 0.0625005
a => 0.0625068
b => 0.0625086
c => 0.0624463
d => 0.06250535
e => 0.06250895
f => 0.06251425